Solu tions des exer cices du cha pitre 4
479
© Dunod – Toute reproduction non autorisée est un délit.
4.18
Il s’agit du problème du voyageur de commerce (en anglais : travelling salesman problem,
« TSP ») qu’on résout par l’algorithme de LITTLE et al. (historiquement une des premières
méthodes de recherche arborescente, nommée « Branch and Bound »). Plus bas on écrit :
« C.H. » pour circuit hamiltonien.
• Initialisation
Partant du tableau initial des coûts, on commence par faire apparaître un « zéro » (coût réduit
nul) dans chaque ligne en retranchant à chaque ligne son plus petit élément ; puis un « zéro »
dans chaque colonne en retranchant, à chaque colonne du tableau obtenu, son plus petit
élément. On dit alors que le tableau des coûts est « réduit ».
Ainsi on retranche 1 à tous les éléments de la ligne D, puis 1 à tous ceux de la colonne B. Le
coût de tout C.H. est au moins égal à la somme des éléments retranchés, soit 2 : la borne b 0
associée à la racine s 0 de l’arborescence est b 0 = 2.
On obtient le tableau « réduit » suivant :
• 1
ère
itération
Puis on calcule le regret de chaque « zéro » (cf Tab. 0) et l’on considère l’arc de coût réduit
nul dont le regret est maximal, c’est ici (B,A) ; son regret vaut : c
0
BD 1 c
0
EA 5 3 1 0 5 3
On va alors séparer l’ensemble s 0 de tous les C.H. en deux sous-ensembles s 1 et s 2 . Ceux qui
n’empruntent pas l’arc (B,A) forment le sous-ensemble s 1 ; la borne inférieure de leur coût b 1 ,
est égale à la borne inférieure précédente b 0 = 2, augmentée du regret de (B,A) : 3, soit b 1 = 5.
Les C.H. qui empruntent l’arc (B,A) forment le sousensemble s 2 . Les implications du choix de (B,A) sont
de supprimer la ligne B et la colonne A et d’interdire
l’arc parasite (A,B) (on pose donc c
2
AB 5 `, cf Tab. 2)
et de faire apparaître (au moins) un zéro par ligne et par
colonne si le tableau restant n’est pas réduit ; mais, ici,
on constate qu’il est réduit).
Par suite b 2 = b 0 = 2 : l’arborescence Arb. 1 illustre cette
séparation.
• 2
ème
itération
On va séparer s 2 car il a la plus faible borne parmi
les sommets pendants ; son tableau de coûts réduits
tableau initial après réduction
tab. 0
arb. 1
tab. 2
479
© Dunod – Toute reproduction non autorisée est un délit.
4.18
Il s’agit du problème du voyageur de commerce (en anglais : travelling salesman problem,
« TSP ») qu’on résout par l’algorithme de LITTLE et al. (historiquement une des premières
méthodes de recherche arborescente, nommée « Branch and Bound »). Plus bas on écrit :
« C.H. » pour circuit hamiltonien.
• Initialisation
Partant du tableau initial des coûts, on commence par faire apparaître un « zéro » (coût réduit
nul) dans chaque ligne en retranchant à chaque ligne son plus petit élément ; puis un « zéro »
dans chaque colonne en retranchant, à chaque colonne du tableau obtenu, son plus petit
élément. On dit alors que le tableau des coûts est « réduit ».
Ainsi on retranche 1 à tous les éléments de la ligne D, puis 1 à tous ceux de la colonne B. Le
coût de tout C.H. est au moins égal à la somme des éléments retranchés, soit 2 : la borne b 0
associée à la racine s 0 de l’arborescence est b 0 = 2.
On obtient le tableau « réduit » suivant :
• 1
ère
itération
Puis on calcule le regret de chaque « zéro » (cf Tab. 0) et l’on considère l’arc de coût réduit
nul dont le regret est maximal, c’est ici (B,A) ; son regret vaut : c
0
BD 1 c
0
EA 5 3 1 0 5 3
On va alors séparer l’ensemble s 0 de tous les C.H. en deux sous-ensembles s 1 et s 2 . Ceux qui
n’empruntent pas l’arc (B,A) forment le sous-ensemble s 1 ; la borne inférieure de leur coût b 1 ,
est égale à la borne inférieure précédente b 0 = 2, augmentée du regret de (B,A) : 3, soit b 1 = 5.
Les C.H. qui empruntent l’arc (B,A) forment le sousensemble s 2 . Les implications du choix de (B,A) sont
de supprimer la ligne B et la colonne A et d’interdire
l’arc parasite (A,B) (on pose donc c
2
AB 5 `, cf Tab. 2)
et de faire apparaître (au moins) un zéro par ligne et par
colonne si le tableau restant n’est pas réduit ; mais, ici,
on constate qu’il est réduit).
Par suite b 2 = b 0 = 2 : l’arborescence Arb. 1 illustre cette
séparation.
• 2
ème
itération
On va séparer s 2 car il a la plus faible borne parmi
les sommets pendants ; son tableau de coûts réduits
tableau initial après réduction
tab. 0
arb. 1
tab. 2