Recherche heuristique bidirectionnelle itérative d'approfondissement avec mémoire restreinte

Résumé :

Le domaine de la recherche heuristique bidirectionnelle a récemment connu de grandes avancées. Cependant, le sujet de la recherche bidirectionnelle restreinte par la mémoire n'a pas reçu d'attention récente. Dans cet article, nous présentons un algorithme général de recherche heuristique itérative d'approfondissement bidirectionnel (IDBiHS) qui recherche simultanément dans les deux directions tout en contrôlant le point de rencontre des frontières de recherche. Nous présentons d'abord la variante de base d'IDBiHS, dont la mémoire est linéaire dans la profondeur de recherche. Nous ajoutons ensuite des améliorations qui exploitent la cohérence et l'heuristique front-to-front. Ensuite, nous passons au cas où une quantité fixe de mémoire est disponible pour stocker les nœuds pendant la recherche et nous développons deux variantes de IDBiHS : (1) A*+IDBiHS, qui commence avec A* et passe à IDBiHS dès que la mémoire est épuisée. (2) Une variante qui stocke des frontières partielles vers l'avant jusqu'à ce que la mémoire soit épuisée et qui essaie ensuite de correspondre à chacune d'entre elles à partir de la partie arrière. Enfin, nous comparons expérimentalement les nouveaux algorithmes aux algorithmes unidirectionnels et bidirectionnels existants. Dans de nombreux cas, nos nouveaux algorithmes sont plus performants que les précédents, tant en termes d'expansion de nœuds que de temps.