Recherche exponentielle itérative budgétisée

Nous abordons deux problèmes de longue date liés aux réexpansions dans les algorithmes de recherche heuristique. Pour la recherche de graphes, A* peut nécessiter Ω(2n) expansions, où n est le nombre d'états dans la borne f finale. Les algorithmes existants qui traitent ce problème comme B et B' améliorent cette limite à Ω(n2). Pour la recherche d'arbres, IDA* peut également nécessiter Ω(n2) expansions. Nous décrivons un nouveau cadre algorithmique qui contrôle itérativement un budget d'expansion et une limite de coût de solution, donnant lieu à de nouveaux algorithmes de recherche de graphes et d'arbres pour lesquels le nombre d'expansions est O(nlogC), où C est le coût de solution optimal. Nos expériences montrent que les nouveaux algorithmes sont robustes dans des scénarios où les algorithmes existants échouent. Dans le cas de la recherche d'arbres, nos nouveaux algorithmes n'ont pas de surcharge par rapport à IDA* dans des scénarios auxquels IDA* est bien adapté et peuvent donc être recommandés comme remplacement général de IDA*.