[c] Backtracking

[cicciobaliccio]

Ho un piano che è una griglia infinita. Ci sono dei rettangoli che rappresentano ostacoli e dei punti che devo far muovere
Se il punto A deve raggiunfgere il punto B cercando il percorso migliore, ovvero quello + breve, secondo voi è giusto usare un algoritmo di backtracking?
oppure.....come faccio a stabilire qual è il percorso + corto?
ovviamente senza scontrarmi con gli ostacoli

[unomichisiada]

Originariamente inviato da cicciobaliccio
Ho un piano che è una griglia infinita. Ci sono dei rettangoli che rappresentano ostacoli e dei punti che devo far muovere
Se il punto A deve raggiunfgere il punto B cercando il percorso migliore, ovvero quello + breve, secondo voi è giusto usare un algoritmo di backtracking?
oppure.....come faccio a stabilire qual è il percorso + corto?
ovviamente senza scontrarmi con gli ostacoli

Io modellerei il problema con un grafo e userei uno dei tanti efficienti algoritmi di cammino minimo per trovare il percorso migliore.Ne conosco uno,l'algoritmo di Dijkstra (credo si scriva così).Ciao

[Lucis]

se il piano è infinito non so se il poblema è risolvibile... sicuramente anche io lo imposterei con un grafo