Prédire l'efficacité de la recherche heuristique bidirectionnelle

Résumé

La question de savoir quand la recherche heuristique bidirectionnelle surpasse la recherche heuristique unidirectionnelle a été réexaminée à de nombreuses reprises dans le domaine de l'intelligence artificielle. Cet article aborde à nouveau la question de savoir quand la recherche bidirectionnelle surpasse la recherche unidirectionnelle en utilisant une compréhension théorique actualisée du problème. Nous montrons qu'un noyau d'états critiques dans l'espace d'état est le facteur principal déterminant si une recherche bidirectionnelle peut surpasser une recherche unidirectionnelle et nous fournissons des mesures simples pour déterminer si un espace d'état et une heuristique contiennent ces états critiques. De même, nous discutons et montrons l'impact de l'asymétrie du graphe du problème sous-jacent sur les performances des algorithmes bidirectionnels. Les résultats expérimentaux montrent l'impact de ces facteurs sur la résolution d'un problème par une recherche unidirectionnelle ou bidirectionnelle.