uovobw
26-06-2006, 14:52
Ciao a tutti,
sto cercando un algortimo che mi permetta di scegliere il cammino minimo fra due punti su una mappa organizzata in questo modo:
- mi posso muovere solo a n s o e e non in diagonale
- posso muovermi di un passo per volta
- ci sono caselle sulle quali non posso assolutamente passare
Avevo pensato all'algoritmo di Dijkstra ma ho visto che è molto efficiente nei casi di un grafo dove le caselle siano a distanze diverse, mentre nel mio caso il peso per andare da una casella a una qualsiasi delle sue 4 adiacenze è sempre 1.
Immagino che ci siano decine di algoritmi atti allo scopo, poichè Dijkstra mi sembra troppo complesso per un caso con pesi tutti 1.
Avete consigli o suggerimenti?
grazie
sto cercando un algortimo che mi permetta di scegliere il cammino minimo fra due punti su una mappa organizzata in questo modo:
- mi posso muovere solo a n s o e e non in diagonale
- posso muovermi di un passo per volta
- ci sono caselle sulle quali non posso assolutamente passare
Avevo pensato all'algoritmo di Dijkstra ma ho visto che è molto efficiente nei casi di un grafo dove le caselle siano a distanze diverse, mentre nel mio caso il peso per andare da una casella a una qualsiasi delle sue 4 adiacenze è sempre 1.
Immagino che ci siano decine di algoritmi atti allo scopo, poichè Dijkstra mi sembra troppo complesso per un caso con pesi tutti 1.
Avete consigli o suggerimenti?
grazie