L'algorithme Aller-Retour : un nouvel algorithme de recherche dans les graphes d'états. J-M LABAT, L MYNARD, J-C POMEROL 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é prin­ cipale 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*. A new state-space search algorithm ded­ icated 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. De­ pending 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.