Conditions pour éviter les réexpansions de nœuds dans la recherche sous-optimale bornée

De nombreux problèmes pratiques sont trop difficiles à résoudre de manière optimale, ce qui motive la nécessité de trouver des solutions sous-optimales, en particulier celles qui ont des limites sur la qualité de la solution finale. Des algorithmes comme A* pondéré, A*-epsilon, la recherche optimiste, EES et DPS ont été développés pour trouver des solutions sous-optimales avec une qualité de solution qui se situe dans une limite constante de la solution optimale. Cependant, à l'exception de A* pondéré, tous ces algorithmes nécessitent d'effectuer des réexpansions de nœuds pendant la recherche. Cet article explore les propriétés des fonctions de priorité qui peuvent trouver une solution sous-optimale bornée sans nécessiter de réexpansion de nœuds. Après avoir développé des limites générales, deux nouvelles fonctions de priorité convexes sont développées et peuvent surpasser A* pondéré.