L'algorithme Aller-Retour : un nouvel algorithme de recherche dans les graphes d'états.

J-M LABAT, L MYNARD, J-C POMEROL

IBP-Laforia 1994/28: Rapport de Recherche Laforia / Laforia research reports
19 pages - Décembre/December 1994 - French document.

PostScript : Ko /Kb

Titre / Title: L'algorithme Aller-Retour : un nouvel algorithme de recherche dans les graphes d'états.

Résumé : Un nouvel algorithme d'exploration d'espaces de recherche dédié à la résolution des problèmes d'optimisation combinatoire, appelé algorithme Aller-Retour, est présenté. L'originalité principale de cet algorithme réside dans le fait qu'il explore non seulement des états réalisables, mais aussi des états non-réalisables. Suivant l'utilisation plus ou moins importante de connaissances heuristiques pour éviter l'exploration de certaines branches du graphe d'états, l'algorithme obtenu est ou n'est plus admissible. La mesure des performances a été effectuée sur le problème du sac-à-dos multidimensionnel en variables entières, et prouve que l'Aller-Retour sur ce type de problèmes est beaucoup plus rapide que A*.

Abstract : A new state-space search algorithm dedicated to the combinatorial optimisation problems resolution and called Go-and-Back is presented. Its main originality is that it explores not only feasible states but unfeasibles ones too. Depending on the more or less large use of heuristic information for avoiding the exploration of some part of the state graph, the algorithm is or is not admissible. Tests on the multidimensional knapsack problem with integer variables gave results which show that our algorithm is much faster than A* for such problems.

Publications internes Laforia 1994 / Laforia research reports 1994