Qu'est-ce qu'un algorithme de chemin optimal de type BFS approprié pour plusieurs entrées et plusieurs sorties?

Question

Je recherche un algorithme de chemin optimal qui trouve le chemin optimal de n'importe lequel des nœuds de départ aux nœuds de sortie les plus proches.

Le graphique dans ce cas est une grille carrée et tous les coûts d'un voisin-carré sont 1. Toutes les optimisations utilisant ces restrictions sont correctes.

Fondamentalement, vous entrez la grille carrée à partir d'une entrée choisie au hasard, maintenant vous voulez trouver le chemin le plus proche de l'une des sorties données. Jusqu'à présent, je fais BFS plusieurs fois, une fois pour chaque sortie et combiner les résultats. Bien que je doute que ce soit la façon la plus performante de le faire.

Answer 1

Vous démarrez BFS à toutes les sorties. Lorsque vous découvrez un nouveau carré, sa distance par rapport à la sortie la plus proche est la distance du carré précédent +1, et la direction du chemin est vers le carré précédent. Puisqu'aucun des tuples (distance, direction) ne dépend de l'endroit où vous entrez, vous pouvez précalculer ces valeurs pour tous les carrés une fois, de sorte que vous n'avez pas à refaire la recherche si vous recommencez à une nouvelle entrée.