164
Recherche opérationnelle
L'algorithme de Little préconise alors de choisir l'arc de regret maximal (par exemple
) pour partitionner l'ensemble H (il s'agit d'une règle empirique qui en principe
accélère la recherche de l'optimum). Dans ces conditions, H sera partitionné en deux
sous-ensembles : , ensemble de circuits hamiltoniens ne passant pas par
et
ensemble des circuits hamiltoniens contenant
ce que nous allons symboliser de la
façon suivante :
On connait une évaluation par défaut pour
. Qu'en est-il pour
?
Comme un circuit hamiltonien n'emprunte qu'un seul arc partant de A et qu'un seul arc
arrivant en E, les arcs autres que
des circuits de
seront choisis sur la matrice 4
obtenue à partir de la matrice 3 en supprimant la ligne A et la colonne E.
On remarquera que l'on a fait apparaître
en EA pour éviter des circuits parasites du
type :
On observe alors qu'on peut faire apparaître un nouveau zéro dans la colonne A en ôtant
4 à tous les éléments de cette matrice.
48
52
H
H1
H2
AE
AE
A
B
C
D
B 7
+
0
0
C 9
0
+
2
D 4
0
2
+
E +
0
+
0
Matrice 4
Car on a supprimé l’arc AE
(- 4)
A
E