.dsy:it. - [PROGETTO] "Mappe 2"

Pages (17): « First ... « 4 5 6 7 [8] 9 10 11 12 » ... Last »
Show 150 posts per page

.dsy:it. (http://www.dsy.it/forum/)
- Algoritmi e strutture dati (http://www.dsy.it/forum/forumdisplay.php?forumid=207)
-- [PROGETTO] "Mappe 2" (http://www.dsy.it/forum/showthread.php?threadid=23982)

Posted by Polsy on 12-02-2006 18:44:

Originally posted by Simeon
Avanzo un problema che magari per voi sarà scemo ma mi sta mandando in confusione.

Voi QUANDO invocate la funzione che calcola il valore totale di una mappa?

Nell'esempio del prof lui inizia con

c 4 4 primo.txt
m mappa1 4 3 blablabla
s mappa1
...

E stampando mappa1 viene visualizzato:

...
mappa1 4 7 1 EEESSSEENWWWWWWWSSEENNNWSSSSSWW
...

Il valore di mappa1 con quella specifica e' "1", quindi in quelle 3 istruzioni la in alto è gia stato calcolato.

Allora ho pensato :"bene, invoco la funzione di calcolo del valore della mappa quando la inserisco con m mappa1 etc...".

Poi sono andato avanti a leggere l'esempio e ho trovato sto passaggio:

...
s alfa
v -3 3 100
s alfa
...

Che in output produce

...
alfa -6 3 11 NEEEN
alfa -6 3 94 EEENN
...

E questo mi manda in crisi. Quello che facciamo noi tra le due stampe è soltanto inserire un nuovo valore. Com'è possibile che la seconda stampa abbia gia a disposizione il valore nuovo della mappa alfa? E la specifica "NEEEN" cambia in "EEENN"... ma perchè?!?!

Boh se qualcuno riesce a capire qualcosa del mio problema e mi da una risposta lo ringrazio tantissimo, può darsi che mi sfugga qualcosa di molto molto importante.

mumble...
i casi sono 2, o il prof ha sbagliato e si è dimenticato una riduzione nel mezzo, o ha ragione yomo e le mappe vanno ridotte automaticamente...in tal caso non fai altro che richiamare riduci quando vuoi stampare una mappa (le riduci solo quando le vuoi stampare, se no sarebbe inefficientissimo) ma mi sembra strano...l'avrebbe scritto nelle specifiche...provate a mandargli una mail

edit: tra le altre cose, se riduci fosse implicita, a che pro richiamare r alfa prima di s alfa?

p.s Polsy ma la rappresentazione con la matrice non è inefficiente? Almeno a quanto dice il progetto si...

la rappresentazione del piano tramite una matrice è di sicuro inefficiente, dato che il piano è infinito

le matrici che dico io riguardano solo la porzione di piano compresa tra l'inizio e la fine della mappa da ridurre

Posted by Simeon on 12-02-2006 18:52:

Originally posted by Polsy
mumble...
i casi sono 2, o il prof ha sbagliato e si è dimenticato una riduzione nel mezzo, o ha ragione yomo e le mappe vanno ridotte automaticamente...in tal caso non fai altro che richiamare riduci quando vuoi stampare una mappa (le riduci solo quando le vuoi stampare, se no sarebbe inefficientissimo) ma mi sembra strano...l'avrebbe scritto nelle specifiche...provate a mandargli una mail

edit: tra le altre cose, se riduci fosse implicita, a che pro richiamare r alfa prima di s alfa?

Non è per fare lo scarica barili, ma gli ho gia mandato 2 mail in 4 giorni e non vorrei che si alteri , non può pensarci uno di voi?

la rappresentazione del piano tramite una matrice è di sicuro inefficiente, dato che il piano è infinito
le matrici che dico io riguardano solo la porzione di piano compresa tra l'inizio e la fine della mappa da ridurre

No ho capito che non intendevi rappresentare TUTTO il piano, è che mi sa che avevo frainteso la nota del progetto (che parla della minima porzione rettangolare contenente tutti i percorsi specificati da mappe).

Bah intanto mi implemento l'alberello per memorizzare i punti non di default... poi si vedrà.

Non ho ancora la minima idea di come fare riduci(..) e sottopercorso(..)

Posted by tyzer on 12-02-2006 20:29:

Polsy (cioè Paola vero? ), ho provato a seguire il tuo suggerimento, per fare la funzione riduci usando Dijkstra modificandolo perchè trovi il valore massimo , il fatto è che non funziona lo stesso...
anche tenendo conto dei soli spostamenti possibili e che cerco il cammino massimo quindi non va in loop su cicli negativi.

Il problema è che se i valori dei punti fossero tutti positivi allora l'algoritmo greedy insegue quelli piu grossi (cioè ogni volta che devo scegliere il prossimo punto scelgo quello piu grosso spostandomi nelle due uniche direzioni possibili per avvicinarmi al punto destinazione) e arrivo a determinare la soluzione ottimale...

Invece essendo presenti valori negativi, l'algoritmo può inseguire lo stesso i valori più grossi, ma magari poi trova dei valori negativi (nei punti successivi...) e la soluzione non è ottima perchè ci potrebbe essere il caso che scegliendo un percorso in cui ci sono punti negativi, poi magarai ce ne sono altri positivi che mi danno un percorso di valore maggiore che se nn avessi inseguito quelli di valore maggiore...

Non so se sono stato chiaro, in pratica credo che la struttura su cui applichiamo questo algoritmo non sia un matroide e quindi gli algoritmi greedy (compreso il caro Dijkstra...) non vanno...

Posted by Polsy on 12-02-2006 21:49:

Originally posted by tyzer
Polsy (cioè Paola vero? ), ho provato a seguire il tuo suggerimento, per fare la funzione riduci usando Dijkstra modificandolo perchè trovi il valore massimo , il fatto è che non funziona lo stesso...
anche tenendo conto dei soli spostamenti possibili e che cerco il cammino massimo quindi non va in loop su cicli negativi.

Il problema è che se i valori dei punti fossero tutti positivi allora l'algoritmo greedy insegue quelli piu grossi (cioè ogni volta che devo scegliere il prossimo punto scelgo quello piu grosso spostandomi nelle due uniche direzioni possibili per avvicinarmi al punto destinazione) e arrivo a determinare la soluzione ottimale...

Invece essendo presenti valori negativi, l'algoritmo può inseguire lo stesso i valori più grossi, ma magari poi trova dei valori negativi (nei punti successivi...) e la soluzione non è ottima perchè ci potrebbe essere il caso che scegliendo un percorso in cui ci sono punti negativi, poi magarai ce ne sono altri positivi che mi danno un percorso di valore maggiore che se nn avessi inseguito quelli di valore maggiore...

Non so se sono stato chiaro, in pratica credo che la struttura su cui applichiamo questo algoritmo non sia un matroide e quindi gli algoritmi greedy (compreso il caro Dijkstra...) non vanno...

si, Paola

ti conosco?

il fatto è che tu calcoli per ogni punto del rettangolo compreso tra la sorgente e la destinazione qual'è il cammino migliore dalla sorgente e in esso memorizzi il valore dell'intero cammino che ti porta fin lì
poniamo di dover andare da SW a NE
alla cella (i,j) ci puoi arrivare solo dalla cella (i-1,j) o da (i,j-1) e scegli quella col cammino parziale di valore massimo (mettiamo sia i-1,j)
nella cella (i,j) memorizzerò come valore $valore_cella(i-1,j) + $valore_punto(i,j)
in questo modo ogni cella ha il valore dell'intero cammino che lo precede, per cui è come se avesse memoria sia dei punti positivi che di quelli negativi
ad esempio se per arrivare alla cella (i,j-1) ho passato punti con valori inizialmente molto alti come 15, 20, 32 e poi valori negativi come -35, -30 avrò come valore della cella 2
mentre se per arrivare alla cella (i-1,j) avevo valori del tipo -1, 0, 0, 3, 4 avrò come valore della cella 6
di conseguenza l'algoritmo sceglie (i-1,j) come cella predecessore e pone il valore della cella i,j (il cui punto corrispondente facciamo che vale 3) a 6+3=9

praticamente l'idea è che per ogni punto intermedio si è calcolato il percorso ottimo per arrivarci, se esclude un percorso è solo perchè ne ha trovato un altro che lo porta nello stesso punto con un guadagno maggiore
come dire, tu non scegli dove ti conviene andare, ma da dove ti conviene arrivare

Posted by darkAntAreS on 12-02-2006 22:24:

domanda stupida: e se trovo 2 percorsi ottimali con la riduzione? sulla descrizione del progetto dice che la riduzione di una mappa è la mappa stessa con un percorso ridotto, ma quell' "un" è articolo indeterminativo o effettivamente se ci sono più percorsi ottimali ne scelgo uno a caso???

__________________
"Ash nazg durbatulûk, ash nazg gimbatul, ash nazg thrakatulûk agh burzum-ishi krimpatul"

Posted by Polsy on 12-02-2006 22:28:

Originally posted by darkAntAreS
domanda stupida: e se trovo 2 percorsi ottimali con la riduzione? sulla descrizione del progetto dice che la riduzione di una mappa è la mappa stessa con un percorso ridotto, ma quell' "un" è articolo indeterminativo o effettivamente se ci sono più percorsi ottimali ne scelgo uno a caso???

se ne hai più ottimali ne scegli 1 a caso

Posted by Simeon on 13-02-2006 10:32:

Ok ragazzi, sul sito di laboratorio c'è l'errata corrige del problema di ieri, ci voleva una riduzione prima della seconda stampa

Per quanto riguarda i valori settati esplicitamente, il prof ha detto che alla creazione di un nuovo piano devono essere svuotati.

Posted by miles on 13-02-2006 10:38:

mi sto accingendo a realizzare il progetto e pensavo alla rappresentazione del piano. se uso un albero binario di ricerca e (x,y) rappresenta la chiave l'albero non è sbilanciato?

Posted by tyzer on 13-02-2006 11:17:

il fatto è che tu calcoli per ogni punto del rettangolo compreso tra la sorgente e la destinazione qual'è il cammino migliore dalla sorgente e in esso memorizzi il valore dell'intero cammino che ti porta fin lì

Ho capito ciò che dici, ma secondo me ci sono dei problemi:

1) Come fai fare quello che ti ho quotato sopra? Per migliore intendi con peso massimo spero...

2) Anche ammettendo che si riesca a trovare per ogni punto (i,j) nel rettangolo il valore del cammino di peso massimo...potrebbe succedere che poi procedendo a ritroso dalla seconda matrice

il cammino te lo trovi riguardando a ritroso i punti della seconda matrice, tempo di calcolo O(n*m) considerando una matrice nxm

trovi che i punti (i-1,j) ed (i,j-1) hanno come valore del cammino migliore per raggiungerli lo stesso costo ed allora quale dei due scegli? Non puoi sceglierne uno a caso fra i 2 perchè non saprai mai se magari sceglievi quello che decidi scartare quali altri costi incontravi e che non incontrerai scegliendo l'altro punto...

P.S.
Di vista forse mi conosci, ero a fare metodi col Mereghet l'anno scorso...eravamo io e un mio amico tutti e due del primo anno...

Posted by Polsy on 13-02-2006 13:45:

Originally posted by tyzer
Ho capito ciò che dici, ma secondo me ci sono dei problemi:

1) Come fai fare quello che ti ho quotato sopra? Per migliore intendi con peso massimo spero...

si, peso massimo
alla prima iterazione tu non sai niente di nessuna cella, sai solo che il punto di origine vale $valore_punto_00 e che appartiene sicuramente al cammino, per cui nella matrice associ alla cella (0,0) le coordinate (0,0) (all'origine ci arrivi dall'origine

) e $valore_cella_00 = $valore_punto_00

alla seconda iterazione analizzi la diagonale successiva, cioè (0,1) e (1,0)

(0,1) -> ci puoi arrivare solo dall'origine, quindi
$coordinate_punto_precedente_a_01 = (0,0)
$valore_cella_01 = $valore_cella_00 + $valore_punto_01

(1,0) -> ci puoi arrivare solo dall'origine, quindi
$coordinate_punto_precedente_a_10 = (0,0)
$valore_cella_10 = $valore_cella_00 + $valore_punto_10

terza iterazione, terza diagonale: (0,2) , (1,1) , (2,0)

(0,2) -> ci puoi arrivare solo da (0,1), quindi
$coordinate_punto_precedente_a_02 = (0,1)
$valore_cella_02 = $valore_cella_01 + $valore_punto_02

(1,1) -> ci puoi arrivare sia da (0,1) che da (1,0)
$coordinate_punto_precedente_a_11 = $punto_associato_alla_cella_con_valore_max
$valore_cella_11 = $valore_cella_con_valore_max + $valore_punto_11
(NOTA: se (0,1) e (1,0) hanno valori uguali è indifferente quale scegliere, vuol dire che entrambi i percorsi ti portano lo stesso guadagno)

(2,0) -> ci puoi arrivare solo da (1,0), quindi
$coordinate_punto_precedente_a_20 = (1,0)
$valore_cella_20 = $valore_cella_10 + $valore_punto_20

2) Anche ammettendo che si riesca a trovare per ogni punto (i,j) nel rettangolo il valore del cammino di peso massimo...potrebbe succedere che poi procedendo a ritroso dalla seconda matrice

trovi che i punti (i-1,j) ed (i,j-1) hanno come valore del cammino migliore per raggiungerli lo stesso costo ed allora quale dei due scegli? Non puoi sceglierne uno a caso fra i 2 perchè non saprai mai se magari sceglievi quello che decidi scartare quali altri costi incontravi e che non incontrerai scegliendo l'altro punto...

quando vai a ritroso per ritrovare il cammino non devi scegliere, hai già scelto prima, il punto precedente ce l'hai nel campo $coordinate_punto_precedente

P.S.
Di vista forse mi conosci, ero a fare metodi col Mereghet l'anno scorso...eravamo io e un mio amico tutti e due del primo anno...

la mia memoria è terribile... :oops:

Posted by tandrea85 on 14-02-2006 14:23:

ho appena iniziato sto progetto ed ho gia un dubbio..

per associare ad ogni punto val basta seguire la nota 3 e fin qua ci sono.. ma x e y dove li prendo? sono semplicemente fatti scorrere partendo dai parametri m e n?
nel caso di c 4 4 primo.txt abbiamo 16 punti e primo.txt contiene 16 valori.. quindi ogni punto avrà un valore.. io facendo 2 calcoli mi è venuto fuori cosi:

(1,1) -> v5
(1,2) -> v9
(1,3) -> v13
(1,4) -> v1
(2,1) -> v6
(2,2) -> v10
(2,3) -> v14
(2,4) -> v2
(3,1) -> v7
(3,2) -> v11
(3,3) -> v15
(3,4) -> v3
(4,1) -> v4
(4,2) -> v8
(4,3) -> v12
(4,4) -> v0

è corretto?

Posted by MaurizioL on 14-02-2006 15:50:

Originally posted by miles
mi sto accingendo a realizzare il progetto e pensavo alla rappresentazione del piano. se uso un albero binario di ricerca e (x,y) rappresenta la chiave l'albero non è sbilanciato?

Potenzialmente sì,

si suppone che le coordinate dei punti inseriti con il comando v x y siano casuali, in quel caso l'albero è relativamente bilanciato

__________________
Maurizio Lombardi
Linux 2.6.14.2
-----------------------

Posted by maynard80 on 14-02-2006 16:07:

Originally posted by tandrea85
ho appena iniziato sto progetto ed ho gia un dubbio..

per associare ad ogni punto val basta seguire la nota 3 e fin qua ci sono.. ma x e y dove li prendo? sono semplicemente fatti scorrere partendo dai parametri m e n?
nel caso di c 4 4 primo.txt abbiamo 16 punti e primo.txt contiene 16 valori.. quindi ogni punto avrà un valore.. io facendo 2 calcoli mi è venuto fuori cosi:

(1,1) -> v5
(1,2) -> v9
(1,3) -> v13
(1,4) -> v1
(2,1) -> v6
(2,2) -> v10
(2,3) -> v14
(2,4) -> v2
(3,1) -> v7
(3,2) -> v11
(3,3) -> v15
(3,4) -> v3
(4,1) -> v4
(4,2) -> v8
(4,3) -> v12
(4,4) -> v0

è corretto?

veramente con C crei il piano ed il piano è immenso e non è altro che un insieme di quadrati costruiti come il tuo... ma ripetuti all'infinito. il fatto che ti dia m ed n non vuol dire che è un piano mxn, infatti poi potrebbe darti una mappa che inizia in 4,7

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Posted by Simeon on 14-02-2006 16:41:

Originally posted by tandrea85
ho appena iniziato sto progetto ed ho gia un dubbio..

per associare ad ogni punto val basta seguire la nota 3 e fin qua ci sono.. ma x e y dove li prendo? sono semplicemente fatti scorrere partendo dai parametri m e n?
nel caso di c 4 4 primo.txt abbiamo 16 punti e primo.txt contiene 16 valori.. quindi ogni punto avrà un valore.. io facendo 2 calcoli mi è venuto fuori cosi:

(1,1) -> v5
(1,2) -> v9
(1,3) -> v13
(1,4) -> v1
(2,1) -> v6
(2,2) -> v10
(2,3) -> v14
(2,4) -> v2
(3,1) -> v7
(3,2) -> v11
(3,3) -> v15
(3,4) -> v3
(4,1) -> v4
(4,2) -> v8
(4,3) -> v12
(4,4) -> v0

è corretto?

Se ti leggi una delle pagine iniziali di questo thread trovi la spiegazione del prof sulla nota 3

Posted by tandrea85 on 14-02-2006 16:59:

Originally posted by Simeon
Se ti leggi una delle pagine iniziali di questo thread trovi la spiegazione del prof sulla nota 3

ok grazie.. ho piu o meno capito.. quindi piano infinito, valori dei generci punti del piano ricavati o tramite v0, v1.. dal file, o tramite valore(s,y,n) o 0 altrimenti.

mettiamo ke io voglia scegliere l'albero binario di ricerca per il piano.. ma se è infinito cosa ci salvo dentro? quali punti?

All times are GMT. The time now is 22:48.

Pages (17): « First ... « 4 5 6 7 [8] 9 10 11 12 » ... Last »
Show all 246 posts from this thread on one page