Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Séparation et évaluation
Résumé
Un algorithme par séparation et évaluation, ou branch and bound en anglais, est une méthode générique de résolution de problèmes d'optimisation combinatoire. Cet algorithme a été introduit par Ailsa Land et Alison Harcourt (Doig) en 1960.
L'optimisation combinatoire consiste à trouver un point minimisant une fonction, appelée coût, dans un ensemble dénombrable. Une méthode naïve pour résoudre ce problème est d'énumérer toutes les solutions du problème, de calculer le coût pour chacune, puis de donner le minimum. Parfois, il est possible d'éviter d'énumérer des solutions dont on sait, par l'analyse des propriétés du problème, que ce sont de mauvaises solutions, c'est-à-dire des solutions qui ne peuvent pas être le minimum. La méthode séparation et évaluation est une méthode générale pour cela.
Cette méthode est très utilisée pour résoudre des problèmes NP-complets, c'est-à-dire des problèmes considérés comme difficiles à résoudre efficacement.
Le branch and bound est parfois comparé à une autre technique de recherche de solution, l'algorithme A*, très souvent utilisé en intelligence artificielle, alors que le branch and bound est plutôt destiné aux problèmes de recherche opérationnelle.
Soit S un ensemble fini mais de « grande » cardinalité qu'on appelle ensemble (ou espace) des solutions réalisables. On dispose d'une fonction f qui, pour toute solution réalisable x de S, renvoie à un coût f(x). Le but du problème est de trouver la solution réalisable x de coût minimal. D'un point de vue purement existentiel, le problème est trivial : une telle solution existe bien car l'ensemble S est fini. En revanche, l'approche effective du problème se confronte à deux difficultés. La première est qu'il n'existe pas forcément un algorithme simple pour énumérer les éléments de S. La seconde est que le nombre de solutions réalisables est très grand, ce qui signifie que le temps d'énumération de toutes les solutions est prohibitif (la complexité en temps est en général exponentielle).
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Proximité ontologique