170
Recherche opérationnelle
qui ne change pas l'évaluation par défaut 52. Regret maximal sur cette matrice
d'où H13 et
est vide et
correspond à la matrice 12.
qui donne la matrice 13 par soustraction de 2 à la ligne C
Regrets maximaux sur cette matrice :
. Deux nouveaux sommets
(vide) et
qui correspond également à un circuit hamiltonien unique :
,
,
,
, de valeur égale à
et qui est en fait le même cycle que celui
trouvé précédemment. L'algorithme est alors terminé; il n'est pas utile en effet de séparer
les ensembles non vides correspondant aux sommets pendants d'évaluation finie, cette
évaluation étant supérieure à celle des deux sommets terminaux non vides.
B
C
D
B +
0
0
C 0
+
2
E 0
+
0
Matrice 11
B
D
C +
2
E 0
0
Matrice 12
- 2
B
D
C +
0
E 0
0
Matrice 13
- 2