Branch and bound
La technique branch and bound est la première qui ait été utilisée lors de l'exploration d'arbres de
possibilités trop complexes pour être parcourus intégralement (voir explosion combinatoire). Elle consiste tout simplelent lors de cette exploration :
- à choisir une heuristique dont on suppose qu'elle aura plus de
chance de faire venir le meilleur résultat dans les premiers (par exemple dans un problème du voyageur de commerce, on
ne choisit pas par priorité de passer d'une ville à la ville la plus éloignée !)
- à mémoriser chaque résultat meilleur que le meilleur trouvé antérieurement (qui, pour le premier, est évidemment... le
premier)
- à munir le programme d'un test de clé pupitre, d'interaction utilisateur par le moyen du clavier ou de
chronométrage assurant qu'il s'arrêtera au bout d'un temps compatible avec le budget, et en imprimant alors le meilleur
résultat trouvé à ce moment-là (les résultats sont souvent imprimés ou affichés au fur et à mesure, ce qui permet de savoir quand
s'arrêter).
Détails
Le programme mémorise aussi la croissance ou décroissance de la fonction objectif au fil du temps, afin de suggérer
éventuellement des temps d'exploration plus longs si des gains importants ont été obtenus vers la fin de la période de
recherche.
On peut, bien que ce ne soit pas obligatoire, mémoriser aussi les meilleures solutions trouvées au fur et à mesure qu'on les
trouve. La suite des réorganisations conduisant à de meilleurs résultat peut en effet à son tour aiguiller vers de
nouvelles heuristiques.
Perfectionnements
- Pour pallier l'imperfection des heuristiques, le programme est souvent muni de méta-heuristiques permettant
d'abandonner momentanément une exploration quand elle ne donne pas le rendement souhaité (par exemple chemin plus long en 5
étapes qu'en 25 étapes par un chemin antérieur, ce qui n'augure pas forcément bien de la suite).
- Lorsque l'exploration d'arbre se fait contre un joueur adverse, on utilise un autre court-circuit d'esprit voisin qui est la
coupure
alpha-béta (parfois nommée coupure P-Q).
- Pour éviter d'explorer des sous-arbres inutilement, il est intéressant de connaître des propriétés qui permettent de calculer
une borne inférieure (lower bound en anglais) pour la valeur de la meilleure solution du sous-arbre. Si elle
est supérieure à la meilleure solution connue, on élague le sous-arbre en question.
Page d'accueil
encyclopedie-enligne.com en page d'accueil