Branch & Bound
Table of Contents
1 Branch & Bound (B&B) pour la résolution du TSP
Soit le problème TSP suivant :
En calculant un arbre couvrant de poids minimal, on obtient efficacement une première borne inférieure (LB) sur le poids de la solution optimale (ici, 9). On peut de même obtenir une première borne supérieure en calculant une solution de manière gloutonne (ici, en privilégiant la plus petite arête voisine et l'ordre lexicographique, abcda de poids 15).
La forme générique du B&B correspond à une recherche en profondeur (DFS) avec mise à jour d'une borne inférieure et d'une borne supérieure dont l'utilisation conjointe permet de ne pas explorer certaines branches de l'arbre.
On propose de modifier l'exemple pour qu'au moins une coupe apparaisse. Il suffit d'assigner à l'arête \(c-d\) un poids supérieur ou égal à \(9\) pour introduire deux coupes. Par exemple, en mettant ce poids à \(10\) :
Les coupes apparaissent car la LB \(16\) est supérieure à la UB \(14\).
2 MIN-MAX / alpha-beta
On applique un principe similaire pour résoudre des jeux à deux joueurs (type échec, go, etc.).
2.1 Enoncé
Deux joueurs. Au départ, un tas d'objets. Un coup consiste à couper un tas en deux parties non vides et inégales. Le joueur qui ne peut plus jouer a perdu.