Comment utilisez-vous un BFS bidirectionnel pour trouver le chemin le plus court?
Comment utilisez-vous Bidirectionnel BFS pour trouver le chemin le plus court? Disons qu'il y a une grille de 6x6.
Le point de départ est dans (0,5) et le point de fin (4,1). Quel est le plus court chemin à l'aide de bidirectionnel bfs? Il n'y a pas les coûts de chemin. Et il est non-orienté.
source d'informationauteur Zik | 2012-06-12
Vous devez vous connecter pour publier un commentaire.
Comment Bi-directionnelle BFS travail?
D'exécuter simultanément deux BFS à partir à la fois la source et la cible des sommets, appelé à disparaître une fois un sommet commun aux deux parcours de découverte. Ce sommet sera à mi-chemin entre la source et la cible.
Pourquoi est-il mieux que BFS?
Bi-directionnelle BFS donnera de bien meilleurs résultats que la simple BFS dans la plupart des cas. Supposons que la distance entre la source et la cible est
k
et le facteur de branchement estB
(tous les sommets a, en moyenne B bords).1 + B + B^2 + ... + B^k
sommets.2 + 2B^2 + ... + 2B^(k/2)
sommets.Pour les grandes
B
etk
la deuxième est évidemment beaucoup plus rapide que le premier.Dans votre cas:
Pour des raisons de simplicité, je vais supposer qu'il n'y a pas d'obstacles dans la matrice. Voici ce qui arrive:
Maintenant, nous avons découvert que les fronts se coupent en (1,2), en collaboration avec les chemins d'accès pour vous y rendre à partir de la source et de la cible les sommets:
Nous avons maintenant, il suffit d'inverser 2 chemin et l'ajouter à la voie 1 (enlever un de la commune d'intersection des sommets de cours), pour nous donner notre chemin d'accès complet: