L’algorithme de branch-and-bound

L’algorithme de branch-and-bound permet de résoudre des problèmes de recherche et d’optimisation. Il est proche dans l’esprit de l’algorithme de backtracking.

Principe

L’algorithme branch-and-bound explore l’arbre des possibilités (dans le cas du voyageur de commerce l’arbre des chemins possibles). Il utilise pour cela un parcours en largeur (Dijkstra sur un graphe pondéré). À chaque nœud qu’il rencontre, il cherche à estimer un intervalle aussi étroit que possible estimant la longueur d’un plus court chemin obtenu à partir de la branche de l’arbre où nous sommes.

Pour obtenir ces intervalles, il y a plusieurs techniques.

Pour obtenir un majorant, il suffit d’utiliser un algorithme glouton. On obtient ainsi un chemin pas nécessairement optimal, mais dont on sait que la longueur ne peut être que supérieure à celle d’un chemin le plus court.

Pour obtenir un minorant, on peut par exemple compter le nombre de sommets restant à visiter (appelons ce nombre k). Dans le meilleur des cas, on peut les visiter en emprunter les k arêtes ayant les poids les plus faibles. La somme de ces k poids donne la borne inférieure. Cette minoration est souvent grossière, et il vaut mieux en chercher des plus fines.

Lorsque l’algorithme a déterminé plusieurs intervalles (un par branche en cours d’exploration), il peut les comparer les uns aux autres. Dans le cas de la recherche d’un chemin de longueur minimale, si une branche d’intervalle I a pour borne supérieure une valeur plus petite que la borne inférieure d’une autre branche d’intervalle J, alors on élimine le sous-arbre correspondant à J. En effet, il ne sert à rien d’explorer le sous-arbre correspondant à l’intervalle J sachant que les meilleures solutions trouvées seront de toute façon moins intéressantes que les moins bonnes en continuant sur la branche I.

Complexité

La complexité de l’algorithme est dans le pire des cas la même qu’une recherche exhaustive (si l’estimation des bornes ne coûte pas trop cher) c’est par exemple le cas avec un graphe complet dont toutes les arêtes ont le même poids.

En pratique, avoir une bonne précision sur l’estimation des intervalles peut faire gagner beaucoup de temps. Un cas optimal revient à une complexité linéaire.

Compromis précision-performance

Comme dans le cas des algorithmes approchés que nous verrons en cours 6, l’estimation des intervalles pose le problème du compromis précision-performance. En effet plus un intervalle est étroit et plus il va permettre d’élaguer des parties de l’arbre. Cependant si son estimation nécessite un calcul coûteux on peut perdre au final sur la complexité totale.

Il convient donc de trouver des estimations des bornes des intervalles qui proposent un bon compromis entre temps de calcul et précision.

Publié le

Laisser un commentaire