Polsy

.arcimaestro.

User info:

Registered: Dec 2003
Posts: 477 (0.06 al dì)
Location:
Corso: Info phd
Anno:
Time Online: 17 Days, 17:11:50 [...]
Status: Offline

Post actions:

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

Last edited by Polsy on 12-02-2006 at 18:47

Simeon

User info:

Registered: Aug 2004
Posts: 984 (0.13 al dì)
Location: Milano
Corso: Informatica
Anno: IT IS OVER!
Time Online: 14 Days, 19:29:42 [...]
Status: Offline

Post actions:

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(..)

tyzer

.illuminato.

User info:

Registered: Sep 2004
Posts: 227 (0.03 al dì)
Location: Novara
Corso: Ticom
Anno: Laureato ^_^
Time Online: 3 Days, 18:31:58 [...]
Status: Offline

Post actions:

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...

Polsy

.arcimaestro.

User info:

Registered: Dec 2003
Posts: 477 (0.06 al dì)
Location:
Corso: Info phd
Anno:
Time Online: 17 Days, 17:11:50 [...]
Status: Offline

Post actions:

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

darkAntAreS

...bloup will rule you...

User info:

Registered: Jun 2004
Posts: 267 (0.04 al dì)
Location: gorgonzola(MI)
Corso: informatica
Anno: x
Time Online: 3 Days, 14:49:45 [...]
Status: Offline

Post actions:

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"

Polsy

.arcimaestro.

User info:

Registered: Dec 2003
Posts: 477 (0.06 al dì)
Location:
Corso: Info phd
Anno:
Time Online: 17 Days, 17:11:50 [...]
Status: Offline

Post actions:

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???

Simeon

User info:

Registered: Aug 2004
Posts: 984 (0.13 al dì)
Location: Milano
Corso: Informatica
Anno: IT IS OVER!
Time Online: 14 Days, 19:29:42 [...]
Status: Offline

Post actions:

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.

miles

User info:

Registered: Aug 2005
Posts: 18 (0.00 al dì)
Location:
Corso:
Anno:
Time Online: 7:36:46 [...]
Status: Offline

Post actions:

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?

tyzer

.illuminato.

User info:

Registered: Sep 2004
Posts: 227 (0.03 al dì)
Location: Novara
Corso: Ticom
Anno: Laureato ^_^
Time Online: 3 Days, 18:31:58 [...]
Status: Offline

Post actions:

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ì

Polsy

.arcimaestro.

User info:

Registered: Dec 2003
Posts: 477 (0.06 al dì)
Location:
Corso: Info phd
Anno:
Time Online: 17 Days, 17:11:50 [...]
Status: Offline

Post actions:

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...

tandrea85

User info:

Registered: Sep 2004
Posts: 95 (0.01 al dì)
Location:
Corso: informatica
Anno: 1
Time Online: 18:21:48 [...]
Status: Offline

Post actions:

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?

MaurizioL

User info:

Registered: Feb 2006
Posts: 17 (0.00 al dì)
Location: Omegna
Corso: Informatica
Anno: 2
Time Online: 3:44:01: [...]
Status: Offline

Post actions:

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?

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

maynard80

.novellino.

User info:

Registered: Jul 2007
Posts: 3 (0.00 al dì)
Location: Milano (e non interland, tendo a precisare)
Corso: informatica
Anno: SESTO
Time Online: 12 Days, 14:28:38 [...]
Status: Offline

Post actions:

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?

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Simeon

User info:

Registered: Aug 2004
Posts: 984 (0.13 al dì)
Location: Milano
Corso: Informatica
Anno: IT IS OVER!
Time Online: 14 Days, 19:29:42 [...]
Status: Offline

Post actions:

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

tandrea85

User info:

Registered: Sep 2004
Posts: 95 (0.01 al dì)
Location:
Corso: informatica
Anno: 1
Time Online: 18:21:48 [...]
Status: Offline

Post actions:

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

Last edited by tandrea85 on 14-02-2006 at 17:16