[C++] Minor cammino (semplice)

[Qu@ker]

Guarda che il mio e il tuo non sono uguali.
E la differenza (minima) è rilevante.

[Mesh89]

Che idiota -.-" Devo invertire x e y...

[Mesh89]

Grazie mille cmq!

[okay]

per studiare l'algoritmo volevo sapere quale è la cella/stanza finale da raggiungere...

quella di partenza l'ho capita:
4-2 corrispone a:
int castle[5][5] = {{6,7,4,7,8},
{7,6,1,1,4},
{3,5,7,8,2},
{2,6,7,0,2},
{7,3,5*,6,1}};
ho contrassegnata la casella di partenza con lì* ovvero 4-2 corrisponde al peso 5.

mentre 2-3 corrisponde a:
int castle[5][5] = {{6,7,4,7,8},
{7,6,1,1,4},
{3,5,7,8*,2},
{2,6,7,0,2},
{7,3,5,6,1}};
ho contrassegnata la casella di partenza con lì* ovvero 2-3 corrisponde al peso 8.

Ora iniziando la ricerca dalla casella appunto contrassegnata vi domando in che casella deve finire la ricerca per il percorso da a

[cionci]

Credo che debba finire una volta uscito dalla prima riga da qualsiasi casella...almeno così sembra fare l'algoritmo sopra...

[okay]

Originariamente inviato da cionci

Credo che debba finire una volta uscito dalla prima riga da qualsiasi casella...almeno così sembra fare l'algoritmo sopra...

già...
si parte dalla 5 (x=4) si cerca in verticale la stanza con peso minore e ci si ferma alla riga (x=0) nella y con peso minore... okay.

ho letto il 3d e proprio tu cionci hai detto che non è proprio un metodo buono ma si potrebbe fare in altro modo.

Ho letto un pò "googlando" e mi interessa fare algoritmi di questo tipo hai qualche stralcio di code per iniziare.

questo sopra cosa ha che non ti piace in termini di efficienza.. tu passeresti anche nelle stanze accanto?... perchè?

Oppure: come modificarlo per avere un punto di partenza e un punto di arrivo e trovare il miglior percorso?... ecco si allora potrei andare da solo!

[cionci]

Originariamente inviato da okay

questo sopra cosa ha che non ti piace in termini di efficienza.. tu passeresti anche nelle stanze accanto?... perchè?

Qui ho fatto un esempio di un semplice cammino che necessità di passare per orizzontale: http://www.hwupgrade.it/forum/showpo...9&postcount=10

L'algoritmo di Dijkstra si usa per trovare il cammino di costo minimo fra tutti i nodi di un grafo, immaginati che ogni cella della matrice si un nodo del grafo e che ogni cella sia legata alle sue adiacenti tramite una arco del grafo.

http://it.wikipedia.org/wiki/Algoritmo_di_Dijkstra

Sicuramente c'è anche qualche altro algoritmo che permette di trovare il cammino minimo fra due nodi scelti (Dijkstra lo trova fra tutti i nodi del grafo), ma ora non mi viene in mente...

[okay]

Originariamente inviato da cionci

Qui ho fatto un esempio di un semplice cammino che necessità di passare per orizzontale: http://www.hwupgrade.it/forum/showpo...9&postcount=10

L'algoritmo di Dijkstra si usa per trovare il cammino di costo minimo fra tutti i nodi di un grafo, immaginati che ogni cella della matrice si un nodo del grafo e che ogni cella sia legata alle sue adiacenti tramite una arco del grafo.

http://it.wikipedia.org/wiki/Algoritmo_di_Dijkstra

Sicuramente c'è anche qualche altro algoritmo che permette di trovare il cammino minimo fra due nodi scelti (Dijkstra lo trova fra tutti i nodi del grafo), ma ora non mi viene in mente...

ho letto...

In pratica si definisce il punto di partenza e il punto di arrivo.
Poi si và a ritroso passando per il peso minore.

Ho solo un dubbio!
tornando a ritroso nell'esempio del tuo link è tutto ok.
Ma se il disegno/esercizio fosse differente come percorsi. intendo: non è possibile che prendendo la strada + breve puoi incappare in strade con percorso maggiore?

Ho quello che ho letto per risolvere l'esercizio non sbaglia mai?

[cionci]

No, non si va a ritroso. Si va dal nodo di partenza a quello di arrivo...
Funziona sempre perché vengono considerati sempre i percorsi alternativi...

[okay]

Originariamente inviato da cionci

No, non si va a ritroso. Si va dal nodo di partenza a quello di arrivo...
Funziona sempre perché vengono considerati sempre i percorsi alternativi...

ok.

Mi metto a svilupparlo una cosa però (senza che mi ci scervello su come inizializzare):

Scelta del punto di partenza:
for i=0 to 10 diciamo.
posso iniziare dall'i = 0 come punto di partenza aggiornando tutti i punti che vanno da 0 a 9 punto di arrivo e questo va bene oppure se nella rete scelgo come punto di partenza i=5 e devo arrivare a i=1 ??

che faccio aggiorno di nuovo i percorsi da 1 a 5?? tenendo presente solo le strade che contattano questi?

spero che mi hai capito... e niente liste!



Edit: mi servono + matrici da 10 una ponendo a 1 le strade da considerare giusto?

for i=0 10
cons[i]=1// considero tutte le strade

diciamo le strade da considerare
for i 0 10
if(consBool[i])
cons[i]=1:

hai altre matrici da inserire per i controlli che ne sò: per il punto di partenza e di arrivo ecc ecc.

[cionci]

Guarda qui, magari si capisce meglio lo pseudocodice: http://en.wikipedia.org/wiki/Dijkstr..._the_algorithm