MM : un algorithme de recherche bidirectionnel qui garantit une rencontre au milieu du chemin

Les algorithmes de recherche bidirectionnelle entrelacent deux recherches distinctes, une recherche normale en avant de l'état de départ et une recherche en arrière du but. Il est bien connu que l'ajout d'une heuristique à la recherche unidirectionnelle réduit considérablement l'effort de recherche. En revanche, malgré des décennies de recherche, la recherche heuristique bidirectionnelle n'a pas encore eu d'impact majeur. De plus, aucune théorie complète n'a été élaborée pour comprendre la nature de la recherche heuristique bidirectionnelle. Dans cet article, nous cherchons à combler cette lacune. Nous présentons d'abord MM, un nouvel algorithme de recherche heuristique bidirectionnelle. Contrairement aux algorithmes de recherche heuristique bidirectionnelle précédents, les recherches avant et arrière de MM sont garanties de se rencontrer au milieu, c'est-à-dire qu'elles n'étendent jamais un nœud au-delà du point médian de la solution. Sur la base de cet attribut unique, nous présentons un nouveau cadre pour comparer MM, A* et leurs variantes de force brute. Pour ce faire, nous divisons l'ensemble de l'espace d'état en régions disjointes en fonction de leur distance par rapport au départ et au but. Cela nous permet d'effectuer une comparaison de ces algorithmes par région et d'identifier les conditions qui favorisent chaque algorithme. Enfin, nous présentons des résultats expérimentaux qui soutiennent notre analyse théorique.