Recherche heuristique bidirectionnelle de front à front avec des expansions de nœuds quasi-optimales

Il est bien connu que tout algorithme de recherche heuristique unidirectionnelle admissible doit développer tous les états dont la valeur f est inférieure au coût de la solution optimale lorsqu'il utilise une heuristique cohérente. De tels états sont appelés "sûrement étendus" (s.e.). Une étude récente a caractérisé les paires d'états s.e. pour la recherche bidirectionnelle avec des heuristiques cohérentes : si une paire d'états est s.e., alors au moins un des deux états doit être étendu. Cet article dérive une limite inférieure, VC, sur le nombre minimum d'expansions requises pour couvrir toutes les paires s.e., et présente un nouvel algorithme de recherche heuristique bidirectionnelle frontale admissible, Near-Optimal Bidirectional Search (NBS), qui est garanti de ne pas faire plus de 2VC expansions. Nous prouvons également qu'aucun algorithme frontal admissible n'est meilleur que 2VC dans le pire des cas. Les résultats expérimentaux montrent que NBS rivalise avec ou surpasse les algorithmes de recherche bidirectionnelle existants, et surpasse souvent A* également.