Poste de recherche

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.

Derniers documents de recherche

Connectez-vous avec la communauté

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.

Explorer la formation et l'enseignement supérieur

Vous êtes curieux de connaître les possibilités d'études auprès de l'un de nos chercheurs ? Vous voulez plus d'informations sur les possibilités de formation ?

Exploiter le potentiel de l'intelligence artificielle

Faites-nous part de vos objectifs et de vos défis concernant l'adoption de l'IA dans votre entreprise. Notre équipe Investissements & Partenariats vous contactera sous peu !