Solutions
480
est donné ci-dessous (Tab. 2) ; on y a indiqué aussi le regret de chaque « zéro », le regret
maximal est 2, relatif à l’arc (A,C). On sépare donc s 2 en deux sous-ensembles s 3 et s 4 . s 3 est
l’ensemble des C.H. passant par (B,A) mais évitant (A, C), de borne b 3 = b 2 + r
2
A C p
4
A C = 2 + 2 = 4 ;
s 4 est l’ensemble des C.H. passant par (B,A) et (A,C).
On supprime alors dans le tableau de s 2 (Tab. 2) la ligne A, la colonne C et on interdit
l’arc parasite (C,B) qui formerait avec les deux arcs déjà retenus, un circuit de longueur
3 : pas un C.H. (on pose donc c
4
CB : 5 `) ce qui donne le nouveau tableau (Tab.4).
L’arborescence Arb. 2 illustre cette nouvelle séparation :
Le tableau restant (Tab. 4) étant réduit, on a b 4 = b 2 =2.
• 3
ème
itération
On va séparer le sommet qui a la plus faible borne parmi les sommets pendants, soit s 4 . L’arc
(D,E) a le plus fort regret (il vaut 5) : on va séparer s 4 en s 5 et s 6 ; b 5 = b 4 + r
4
DE = 2 + 5 = 7.
Le tableau associé à s 6 (Tab. 6) est obtenu en supprimant la ligne D et la colonne E et en
interdisant l’arc parasite (E,D) ; mais, cette fois, le tableau restant (Tab. 5) n’est pas réduit (il
ne comporte pas un « zéro » dans chaque ligne et chaque colonne) : il faut retrancher 4 aux
éléments de sa ligne C (pour le réduire) ; par suite : b 6 = b 4 + 4 = 6 : cf Tab. 6′.
Remarquons qu’on n’a alors plus le choix ; les arcs (C,D) et (E,B) doivent être pris ; avec
ceux précédemment pris ils forment le C.H. (B,A,C,D,E,B), de coût 6. Mais il n’est pas
nécessairement optimal.
• 4
ème
itération
Cette fois le sommet pendant de plus faible borne (s 3 ) n’est
pas le fils (s 6 ) du sommet qu’on vient de séparer (s 4 ) d’où un
SAUT vers le sommet s 3 (dans le nom anglais “Branch and
Bound”, Bound a les deux sens : borne et bond/saut).
Le tableau relatif à s 3 s’obtient à partir de celui de s 2 ,
simplement en posant c
3
A , C 5 `, puis en le réduisant : on
retranche 1 en ligne A et 1 en colonne C ; la somme des
éléments retranchés (1+1) est précisément le regret de l’arc
(A,C), qui a déjà été pris en compte pour évaluer la borne de
s 3 (= b 2 + r
3
AC ) qui vaut bien 2.
Il serait donc faux de l’ajouter à nouveau à b 3 .
tab. 4
arb. 2
tab. 6
tab. 69
tab. 3
480
est donné ci-dessous (Tab. 2) ; on y a indiqué aussi le regret de chaque « zéro », le regret
maximal est 2, relatif à l’arc (A,C). On sépare donc s 2 en deux sous-ensembles s 3 et s 4 . s 3 est
l’ensemble des C.H. passant par (B,A) mais évitant (A, C), de borne b 3 = b 2 + r
2
A C p
4
A C = 2 + 2 = 4 ;
s 4 est l’ensemble des C.H. passant par (B,A) et (A,C).
On supprime alors dans le tableau de s 2 (Tab. 2) la ligne A, la colonne C et on interdit
l’arc parasite (C,B) qui formerait avec les deux arcs déjà retenus, un circuit de longueur
3 : pas un C.H. (on pose donc c
4
CB : 5 `) ce qui donne le nouveau tableau (Tab.4).
L’arborescence Arb. 2 illustre cette nouvelle séparation :
Le tableau restant (Tab. 4) étant réduit, on a b 4 = b 2 =2.
• 3
ème
itération
On va séparer le sommet qui a la plus faible borne parmi les sommets pendants, soit s 4 . L’arc
(D,E) a le plus fort regret (il vaut 5) : on va séparer s 4 en s 5 et s 6 ; b 5 = b 4 + r
4
DE = 2 + 5 = 7.
Le tableau associé à s 6 (Tab. 6) est obtenu en supprimant la ligne D et la colonne E et en
interdisant l’arc parasite (E,D) ; mais, cette fois, le tableau restant (Tab. 5) n’est pas réduit (il
ne comporte pas un « zéro » dans chaque ligne et chaque colonne) : il faut retrancher 4 aux
éléments de sa ligne C (pour le réduire) ; par suite : b 6 = b 4 + 4 = 6 : cf Tab. 6′.
Remarquons qu’on n’a alors plus le choix ; les arcs (C,D) et (E,B) doivent être pris ; avec
ceux précédemment pris ils forment le C.H. (B,A,C,D,E,B), de coût 6. Mais il n’est pas
nécessairement optimal.
• 4
ème
itération
Cette fois le sommet pendant de plus faible borne (s 3 ) n’est
pas le fils (s 6 ) du sommet qu’on vient de séparer (s 4 ) d’où un
SAUT vers le sommet s 3 (dans le nom anglais “Branch and
Bound”, Bound a les deux sens : borne et bond/saut).
Le tableau relatif à s 3 s’obtient à partir de celui de s 2 ,
simplement en posant c
3
A , C 5 `, puis en le réduisant : on
retranche 1 en ligne A et 1 en colonne C ; la somme des
éléments retranchés (1+1) est précisément le regret de l’arc
(A,C), qui a déjà été pris en compte pour évaluer la borne de
s 3 (= b 2 + r
3
AC ) qui vaut bien 2.
Il serait donc faux de l’ajouter à nouveau à b 3 .
tab. 4
arb. 2
tab. 6
tab. 69
tab. 3