168
Recherche opérationnelle
Quant à la séparation elle-même, on utilise toujours le même principe que
précédemment : les deux parties du sous-ensemble séparé se distingueront par le fait que
leurs éléments (circuits hamiltoniens) passeront ou ne passeront pas par l'arc de plus fort
regret. On peut alors avoir trois éventualités :
a) le sommet que l'on veut séparer correspond à un sous-ensemble vide. On dira alors
qu'il est terminal vide.
Sur l'exemple, on peut s'en apercevoir en considérant la suite d'arcs par où doivent passer
les circuits hamiltoniens du sous-ensemble à séparer. Si un sommet apparaît plus de
deux fois dans cette suite d'arcs, le sous-ensemble est vide (en effet tout sommet du
graphe apparaît exactement deux fois dans un circuit hamiltonien). De la même façon, si
le graphe partiel constitué par cette suite d'arcs contient déjà un circuit, il ne peut y avoir
de circuit hamiltonien passant par ces arcs.
Alors, ce sommet n’est pas à séparer, on le raye des sommets pendants de l'arborescence,
et on recherche le sommet d'évaluation minimale parmi les sommets restants : on tentera
de séparer le sommet trouvé.
b) Le sommet que l'on veut trouver n'est pas vide
5 et il contient plus d'un élément (ou du
moins, on ne peut décider si l'une ou l'autre de ces propositions est fausse) : alors, on
sépare ce sommet, et on calcule l'évaluation par défaut des deux sommets obtenus. On
continue alors la procédure.
c) le sommet que l'on veut séparer contient exactement un élément : c'est le cas d'un
sommet où le nombre d'arcs par où doivent passer les circuits hamiltoniens relatifs à ce
sommet est exactement égal à 5 et où le graphe partiel correspondant à ces arcs forme un
circuit hamiltonien. Ce sommet sera dit terminal non vide. Mais en ce sommet, on a
exactement la valeur du circuit hamiltonien; et non plus une valeur par défaut (c'est la
somme des valeurs des 5 arcs retenues).
D'après la règle utilisée pour choisir le sommet à séparer, la valeur de ce circuit
hamiltonien est inférieure aux évaluations par défaut calculées en chacun des autres
sommets pendants. Mais cela signifie que les circuits hamiltoniens correspondant à ces
sommets pendants sont tous de valeur supérieure à celle du circuit hamiltonien trouvé;
ce dernier est donc le circuit hamiltonien optimum.
Remarque : cela est vrai si le sommet à séparer est unique, c'est-à-dire s'il n'existe pas
plusieurs sommets d'évaluations par défaut minimales et égales. Dans ce cas, il peut y
avoir des solutions optimales équivalentes.
Pour illustrer ces constatations, reprenons l'exemple proposé et appliquons la procédure
à partir de calculs déjà effectués.
Séparons le sous-ensemble
les regrets calculés sur la matrice 8 sont :
0
=
0
=
2
=
3
=
BE
BD
BC
AD
5 Par commodité de langage, on confond ici le sommet et le sous-ensemble qui lui correspond.
Recherche opérationnelle
Quant à la séparation elle-même, on utilise toujours le même principe que
précédemment : les deux parties du sous-ensemble séparé se distingueront par le fait que
leurs éléments (circuits hamiltoniens) passeront ou ne passeront pas par l'arc de plus fort
regret. On peut alors avoir trois éventualités :
a) le sommet que l'on veut séparer correspond à un sous-ensemble vide. On dira alors
qu'il est terminal vide.
Sur l'exemple, on peut s'en apercevoir en considérant la suite d'arcs par où doivent passer
les circuits hamiltoniens du sous-ensemble à séparer. Si un sommet apparaît plus de
deux fois dans cette suite d'arcs, le sous-ensemble est vide (en effet tout sommet du
graphe apparaît exactement deux fois dans un circuit hamiltonien). De la même façon, si
le graphe partiel constitué par cette suite d'arcs contient déjà un circuit, il ne peut y avoir
de circuit hamiltonien passant par ces arcs.
Alors, ce sommet n’est pas à séparer, on le raye des sommets pendants de l'arborescence,
et on recherche le sommet d'évaluation minimale parmi les sommets restants : on tentera
de séparer le sommet trouvé.
b) Le sommet que l'on veut trouver n'est pas vide
5 et il contient plus d'un élément (ou du
moins, on ne peut décider si l'une ou l'autre de ces propositions est fausse) : alors, on
sépare ce sommet, et on calcule l'évaluation par défaut des deux sommets obtenus. On
continue alors la procédure.
c) le sommet que l'on veut séparer contient exactement un élément : c'est le cas d'un
sommet où le nombre d'arcs par où doivent passer les circuits hamiltoniens relatifs à ce
sommet est exactement égal à 5 et où le graphe partiel correspondant à ces arcs forme un
circuit hamiltonien. Ce sommet sera dit terminal non vide. Mais en ce sommet, on a
exactement la valeur du circuit hamiltonien; et non plus une valeur par défaut (c'est la
somme des valeurs des 5 arcs retenues).
D'après la règle utilisée pour choisir le sommet à séparer, la valeur de ce circuit
hamiltonien est inférieure aux évaluations par défaut calculées en chacun des autres
sommets pendants. Mais cela signifie que les circuits hamiltoniens correspondant à ces
sommets pendants sont tous de valeur supérieure à celle du circuit hamiltonien trouvé;
ce dernier est donc le circuit hamiltonien optimum.
Remarque : cela est vrai si le sommet à séparer est unique, c'est-à-dire s'il n'existe pas
plusieurs sommets d'évaluations par défaut minimales et égales. Dans ce cas, il peut y
avoir des solutions optimales équivalentes.
Pour illustrer ces constatations, reprenons l'exemple proposé et appliquons la procédure
à partir de calculs déjà effectués.
Séparons le sous-ensemble
les regrets calculés sur la matrice 8 sont :
0
=
0
=
2
=
3
=
BE
BD
BC
AD
5 Par commodité de langage, on confond ici le sommet et le sous-ensemble qui lui correspond.