4.10 Recherches arbo res centes
169
© Dunod – Toute reproduction non autorisée est un délit.
Le lec teur obser vera que dans la méthode gour -
mande, le choix ini tial d’arcs de faible coût peut
avoir pour consé quence (impli ca tion) l’obli ga tion
de prendre des arcs « chers » en fin d’appli ca tion
de la méthode.
Figure 4.49 L’opti mum est le cir cuit hamiltonien (B, D, F, E, C, A, B) de coût 23.
Il se pose alors la ques tion de l’exis tence d’une garan tie de per for mance pour une
heu ris tique don née : peut- on bor ner l’écart entre le coût de l’opti mum c
*
d’un pro -
blème et le coût c H d’une solu tion heu ris tique cal cu lée en temps poly no mial ? Pour le
pro blème du voya geur de com merce, on peut mon trer qu’il n’existe pas de garan tie
rela tive de per for mance, c’est- à-dire qu’il existe des exemples (ou ins tances) pour
les quels le rap port c H /c
*
peut être rendu arbi trai re ment grand.
En revanche, pour ce même pro blème du voya geur de com merce, si le tableau des
coûts (ou dis tances) est eucli
dien, c’est àdire s’il véri fie les inéga li tés tri an gu laires :
pour tout i, j, k : c ij < c ik 1 c kj , comme le font les dis tances géo gra phiques, il existe
des heu ris tiques pour les quelles c H^ c
* < 2, quelle que soit l’ins tance consi dé rée.
Mon trons com ment pour un autre pro blème, une heu ris tique gour mande (glou tonne)
four nit une garan tie de per for mance. Le pro blème appelé bin packing s’énonce de la
façon sui vante : n objets non sécables, l’objet i étant de taille a i , 0 , a i , A, sont à pla cer
dans un nombre mini mal de boîtes toutes de taille A (la somme des tailles des objets
A
A
2
2
2
2
1
1
1
100
100
1
1
1
C D
B
B
D
C
Matrice 19.
169
© Dunod – Toute reproduction non autorisée est un délit.
Le lec teur obser vera que dans la méthode gour -
mande, le choix ini tial d’arcs de faible coût peut
avoir pour consé quence (impli ca tion) l’obli ga tion
de prendre des arcs « chers » en fin d’appli ca tion
de la méthode.
Figure 4.49 L’opti mum est le cir cuit hamiltonien (B, D, F, E, C, A, B) de coût 23.
Il se pose alors la ques tion de l’exis tence d’une garan tie de per for mance pour une
heu ris tique don née : peut- on bor ner l’écart entre le coût de l’opti mum c
*
d’un pro -
blème et le coût c H d’une solu tion heu ris tique cal cu lée en temps poly no mial ? Pour le
pro blème du voya geur de com merce, on peut mon trer qu’il n’existe pas de garan tie
rela tive de per for mance, c’est- à-dire qu’il existe des exemples (ou ins tances) pour
les quels le rap port c H /c
*
peut être rendu arbi trai re ment grand.
En revanche, pour ce même pro blème du voya geur de com merce, si le tableau des
coûts (ou dis tances) est eucli
dien, c’est àdire s’il véri fie les inéga li tés tri an gu laires :
pour tout i, j, k : c ij < c ik 1 c kj , comme le font les dis tances géo gra phiques, il existe
des heu ris tiques pour les quelles c H^ c
* < 2, quelle que soit l’ins tance consi dé rée.
Mon trons com ment pour un autre pro blème, une heu ris tique gour mande (glou tonne)
four nit une garan tie de per for mance. Le pro blème appelé bin packing s’énonce de la
façon sui vante : n objets non sécables, l’objet i étant de taille a i , 0 , a i , A, sont à pla cer
dans un nombre mini mal de boîtes toutes de taille A (la somme des tailles des objets
A
A
2
2
2
2
1
1
1
100
100
1
1
1
C D
B
B
D
C
Matrice 19.