Conditions nécessaires et suffisantes pour éviter les réouvertures dans la recherche du meilleur premier sous-optimal avec des fonctions limites générales

Résumé

Des travaux récents ont introduit les fonctions de priorité XDP et XUP pour la recherche sous-optimale bornée par le meilleur d'abord, qui n'ont pas besoin d'effectuer des réexpansions d'état tant que l'heuristique de recherche est cohérente. Cependant, ce travail présentait plusieurs limitations qui sont corrigées ici. Cet article analyse la suffisance et la nécessité des conditions utilisées pour formuler XDP et XUP. L'analyse présente une preuve plus simple et généralise le résultat sous trois aspects : (1) la fonction de priorité ne doit plus être différentiable partout, (2) la qualité de la solution ne doit pas être limitée par un facteur constant, et (3) les graphes dirigés sont traités correctement. Ces résultats permettent l'introduction d'autres fonctions de priorité, telles que les fonctions linéaires par morceaux, et d'autres variantes de la recherche sous-optimale bornée, telles que la sous-optimalité constante. Plusieurs nouvelles fonctions de priorité sont présentées dans cet article qui, selon les résultats empiriques, peuvent surpasser de manière significative les approches existantes, y compris XDP.