4.10 Recherches arbo res centes
165
© Dunod – Toute reproduction non autorisée est un délit.
En cas d’éga lité, on se donne une règle arbi traire pour rete nir l’un des regrets
maximaux, par exemple le pre mier ren contré lors du balayage de la matrice ligne
après ligne.
On obtient ainsi la matrice 4, où le regret maximal, soit 4, concerne l’arc (B, D).
– Bloc D. On sait à présent, après que l’on ait pro cédé à
l’éva lua tion des regrets des zéros d’une matrice, et cela à
toute étape du pro blème, qu’il reste pos sible :
soit de renon cer à uti li ser l’arc (X, Y), de regret
p(X, Y), le plus fort parmi les regrets. Alors la valeur de
ce regret doit être ajou tée à la borne infé rieure, cal cu lée
plus haut, pour obte nir une borne du coût des solu tions
évi tant l’arc (X, Y) ;
soit de choi sir d’uti li ser l’arc (X, Y). Restent à exa mi
ner les consé quences de ce choix.
C’est ainsi que se déve lop pera l’arbo res cence décri vant
la recherche, par la créa tion d’un som met de type I : NON
(X, Y) et d’un som met de type II : (X, Y) : cf Fig 4.48.
D’où déjà, pour le som met de type I, cor res pon dant à la déci sion NON (X, Y), c’està-dire la déci sion de renon cer à l’uti li sation de (X, Y), ce qui a le surcoût p(X, Y) :
B : 5 B 1 p(X, Y).
Dans l’exemple cité, la borne du som met NON (B, D) de l’arbo res cence est :
B : 5 20 1 4 5 24.
– Bloc E.
1) Au contraire, si l’on inclut l’arc (X, Y), il faut sup pri mer la ligne X et la colonne
Y, de la matrice des coûts réduits, puis, par l’intro duc
tion d’un coût infini, inter
dire l’arc qui fer me rait un cir cuit « para site » (c’est- à-dire un cir cuit qui serait de
lon gueur infé rieure à n, donc non hamiltonien). Notons que les cir cuits para sites
n’existent plus lorsque l’on est par venu à une matrice de dimen sion 1 3 1.
2) Il faut main te nant véri
fier s’il existe tou jours dans la matrice
réduite (matrice 5) un zéro par ligne et par colonne. Sinon, faire
appa raître un zéro par ran gée (matrice 5 bis). Dans l’exemple,
il n’y a rien à modi fier ; ici la matrice 5 bis se confond avec la
matrice 5.
3) La borne du som met (X, Y) de l’arbo res cence devient, le
cas échéant :
B : 5 B 1 somme des élé
ments ôtés au § 2 du bloc E.
Dans notre exemple, elle reste égale à 20.
4) Si l’on a atteint une matrice 1 3 1, arrê ter les cal culs, car on a la solu tion. Sinon
pas ser au bloc sui vant.
2
1
2
1 2 2
0
2
4
A B C D E F
B
A
C
D
E
F
4. Regrets cor res pon -
dant aux zéros de la
matrice 3.
0 0 0 0
3 2 3 0
A B C E F
A
C
D
E
F
2 4 0 2
1 6 0 6
4 2 4 0
Matrice 5 et 5 bis
165
© Dunod – Toute reproduction non autorisée est un délit.
En cas d’éga lité, on se donne une règle arbi traire pour rete nir l’un des regrets
maximaux, par exemple le pre mier ren contré lors du balayage de la matrice ligne
après ligne.
On obtient ainsi la matrice 4, où le regret maximal, soit 4, concerne l’arc (B, D).
– Bloc D. On sait à présent, après que l’on ait pro cédé à
l’éva lua tion des regrets des zéros d’une matrice, et cela à
toute étape du pro blème, qu’il reste pos sible :
soit de renon cer à uti li ser l’arc (X, Y), de regret
p(X, Y), le plus fort parmi les regrets. Alors la valeur de
ce regret doit être ajou tée à la borne infé rieure, cal cu lée
plus haut, pour obte nir une borne du coût des solu tions
évi tant l’arc (X, Y) ;
soit de choi sir d’uti li ser l’arc (X, Y). Restent à exa mi
ner les consé quences de ce choix.
C’est ainsi que se déve lop pera l’arbo res cence décri vant
la recherche, par la créa tion d’un som met de type I : NON
(X, Y) et d’un som met de type II : (X, Y) : cf Fig 4.48.
D’où déjà, pour le som met de type I, cor res pon dant à la déci sion NON (X, Y), c’està-dire la déci sion de renon cer à l’uti li sation de (X, Y), ce qui a le surcoût p(X, Y) :
B : 5 B 1 p(X, Y).
Dans l’exemple cité, la borne du som met NON (B, D) de l’arbo res cence est :
B : 5 20 1 4 5 24.
– Bloc E.
1) Au contraire, si l’on inclut l’arc (X, Y), il faut sup pri mer la ligne X et la colonne
Y, de la matrice des coûts réduits, puis, par l’intro duc
tion d’un coût infini, inter
dire l’arc qui fer me rait un cir cuit « para site » (c’est- à-dire un cir cuit qui serait de
lon gueur infé rieure à n, donc non hamiltonien). Notons que les cir cuits para sites
n’existent plus lorsque l’on est par venu à une matrice de dimen sion 1 3 1.
2) Il faut main te nant véri
fier s’il existe tou jours dans la matrice
réduite (matrice 5) un zéro par ligne et par colonne. Sinon, faire
appa raître un zéro par ran gée (matrice 5 bis). Dans l’exemple,
il n’y a rien à modi fier ; ici la matrice 5 bis se confond avec la
matrice 5.
3) La borne du som met (X, Y) de l’arbo res cence devient, le
cas échéant :
B : 5 B 1 somme des élé
ments ôtés au § 2 du bloc E.
Dans notre exemple, elle reste égale à 20.
4) Si l’on a atteint une matrice 1 3 1, arrê ter les cal culs, car on a la solu tion. Sinon
pas ser au bloc sui vant.
2
1
2
1 2 2
0
2
4
A B C D E F
B
A
C
D
E
F
4. Regrets cor res pon -
dant aux zéros de la
matrice 3.
0 0 0 0
3 2 3 0
A B C E F
A
C
D
E
F
2 4 0 2
1 6 0 6
4 2 4 0
Matrice 5 et 5 bis