Poste de recherche
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.
17 mai 2021
Poste de recherche
17 mai 2021
Poste de recherche
17 mai 2021
Poste de recherche
Vous cherchez à renforcer les capacités en matière d'IA ? Vous avez besoin d'un conférencier pour votre événement ?
Participez à l'écosystème croissant de l'IA en Alberta ! Les demandes de conférenciers, de parrainage et de lettres de soutien sont les bienvenues.