Une recherche bidirectionnelle qui garantit une rencontre au milieu du chemin

Nous présentons MM, le premier algorithme de recherche heuristique bidirectionnelle dont les recherches avant et arrière sont garanties de se rencontrer au milieu, c'est-à-dire de ne jamais étendre un nœud au-delà du milieu de la solution. Nous présentons également un nouveau cadre pour comparer MM, A* et la recherche par force brute, et nous identifions les conditions qui favorisent chaque algorithme. Enfin, nous présentons des résultats expérimentaux qui appuient notre analyse théorique.

Remerciements

Merci à Joseph Barker pour avoir répondu aux questions et fourni des données supplémentaires liées à (Barker et Korf 2015) et à Sandra Zilles et Andre Grahl Pereira pour avoir suggéré des im- ' prouvations dans l'analyse théorique du MM. Le soutien financier de cette recherche a été fourni en partie par le Conseil de recherches en sciences naturelles et en génie du Canada (CRSNG) et par la subvention #417/13 de la Fondation scientifique d'Israël (ISF). Les installations de calcul pour certaines de nos expériences ont été fournies par Calcul Canada. Ce matériel est basé sur des travaux soutenus par la National Science Foundation dans le cadre de la subvention n° 1551406.