Conditions suffisantes pour l'expansion des nœuds dans la recherche heuristique bidirectionnelle

Dans cet article, nous étudions la recherche bidirectionnelle dans l'espace d'état avec des heuristiques cohérentes, en nous concentrant sur l'obtention de conditions suffisantes pour l'expansion des nœuds, c'est-à-dire des conditions caractérisant les nœuds qui doivent être étendus par tout algorithme de recherche bidirectionnelle admissible. Nous fournissons de telles conditions pour la recherche bidirectionnelle front-to-front et front-to-end. Les conditions suffisantes sont utilisées pour prouver que l'algorithme de recherche bidirectionnelle frontale BDS1 est optimalement efficace, en termes d'expansion de nœuds, parmi une large classe d'algorithmes de recherche bidirectionnelle, pour une classe spécifique d'instances de problèmes. On montre que le résultat bien connu de Dechter et Pearl sur les conditions suffisantes pour l'expansion des nœuds par des algorithmes unidirectionnels tels que A* est un cas particulier de nos résultats.

Remerciements

Nous remercions Ariel Felner et les réviseurs anonymes pour leurs nombreuses suggestions qui ont permis d'améliorer le document. 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). Ce matériel est basé sur des travaux soutenus par la National Science Foundation dans le cadre de la subvention n° 1551406.