Chapitre 2 • Notions de complexité
54
Dans la dernière étape on construit un cycle hamiltonien à partir du circuit E. Ce
cycle est obtenu en considérant uniquement la première occurrence de chaque sommet dans E puis en ajoutant en dernière position le sommet initial (ici : a). Le cycle
C 5 (a, b, c, e, d, f, a) est la solution approchée, son coût est : Ĉ 5 11. Le coût de
l’optimum (inconnu ici) est noté C*.
Nous allons montrer que pour toute instance du problème du voyageur de commerce euclidien l’algorithme précédant construit une solution de coût Ĉ vérifiant
C
C*
# 2 : notons c(H) le coût d’un arbre couvrant de coût minimal. Le coût du
circuit eulérien E est : l(E) 5 2 c(H). Puisque que tous les coûts vérifient l’inégalité triangulaire, nous avons : l(E) $ C; en effet : l(E) 5 c ab 1 (c ba 1 c ac ) 1
(c ca 1 c ae ) 1 c ed 1 (c de 1 c ef ) 1 (c fe 1 c ea ) $ c ab 1 c bc 1 c ce 1 c ed 1 c df 1 c fa 5 C.
D’autre part tout cycle hamiltonien est la réunion d’une chaîne élémentaire P couvrant
les sommets de G et de l’arête [k, l] joignant les deux extrémités k et l de cette chaîne.
Toute chaîne qui couvre les sommets de G est aussi un arbre couvrant ; ainsi en notant
l(P) le coût de la chaîne P, nous avons : c(H) # l(P) puisque H est un arbre couvrant de coût minimal. Comme les valuations (coûts) des arêtes sont positives, tout
cycle hamiltonien C a un coût l(C) 5 l(P) 1 c kl qui vérifie : l(C) $ l(P) $ c(H).
En particulier un cycle hamiltonien de longueur minimale est tel que C* $ c(H).
En regroupant les inégalités nous obtenons : C # l(E) 5 2 c(H) # 2 C* et ainsi
C
C*
# 2. En fait, ici, C* 5 9 avec (a, b, f, e, d, c, a) et *
, .
C
= =
11
9
1 22
Ĉ
On peut montrer que l’algorithme permettant d’obtenir cette solution approchée
est polynomial ; nous avons donc un algorithme polynomial avec une garantie relative de performance de rapport 2 pour le problème du voyageur de commerce euclidien (ce problème étant prouvé NP-difficile, il n’exite pas d’algorithme polynomial
fournissant une solution optimale, sauf si P 5 NP : ce qui est très improbable !).
Autre exemple : un algorithme polynomial avec garantie de
performance pour le problème du bin packing
Considérons n objets de même forme linéaire, dont les tailles a 1 , c , a n vérifient : 0 , a i , A. On cherche à placer ces objets dans des boîtes de taille A de
façon à utiliser un nombre minimal de boîtes. Par exemple ces objets peuvent être
des livres ; la ‘taille’ de chacun est son épaisseur ; on désir les ranger dans des étagères, chacune de longueur A ; on veut minimiser le nombre d’étagères à acheter. Ce
problème connu sous le nom de bin packing (mise en boîte) est NP-difficile. L’algorithme suivant permet d’obtenir une solution approchée : les objets sont placés un
à un dans les boîtes suivant l’ordre arbitraire 1, c , n. L’étape i (i 5 1, c , n) de
l’algorithme consiste à placer l’objet i dans une des boîtes déjà partiellement remplie
(sauf pour l’objet 1 rangé dans une boîte vide), si cela est possible (la somme des
tailles des objets placés dans chacune des boîtes ne doit pas dépasser la capacité A).
Si ce n’est pas possible, l’objet i est placé dans une nouvelle boîte.
ˆ
ˆ
ˆ
ˆ
ˆ
54
Dans la dernière étape on construit un cycle hamiltonien à partir du circuit E. Ce
cycle est obtenu en considérant uniquement la première occurrence de chaque sommet dans E puis en ajoutant en dernière position le sommet initial (ici : a). Le cycle
C 5 (a, b, c, e, d, f, a) est la solution approchée, son coût est : Ĉ 5 11. Le coût de
l’optimum (inconnu ici) est noté C*.
Nous allons montrer que pour toute instance du problème du voyageur de commerce euclidien l’algorithme précédant construit une solution de coût Ĉ vérifiant
C
C*
# 2 : notons c(H) le coût d’un arbre couvrant de coût minimal. Le coût du
circuit eulérien E est : l(E) 5 2 c(H). Puisque que tous les coûts vérifient l’inégalité triangulaire, nous avons : l(E) $ C; en effet : l(E) 5 c ab 1 (c ba 1 c ac ) 1
(c ca 1 c ae ) 1 c ed 1 (c de 1 c ef ) 1 (c fe 1 c ea ) $ c ab 1 c bc 1 c ce 1 c ed 1 c df 1 c fa 5 C.
D’autre part tout cycle hamiltonien est la réunion d’une chaîne élémentaire P couvrant
les sommets de G et de l’arête [k, l] joignant les deux extrémités k et l de cette chaîne.
Toute chaîne qui couvre les sommets de G est aussi un arbre couvrant ; ainsi en notant
l(P) le coût de la chaîne P, nous avons : c(H) # l(P) puisque H est un arbre couvrant de coût minimal. Comme les valuations (coûts) des arêtes sont positives, tout
cycle hamiltonien C a un coût l(C) 5 l(P) 1 c kl qui vérifie : l(C) $ l(P) $ c(H).
En particulier un cycle hamiltonien de longueur minimale est tel que C* $ c(H).
En regroupant les inégalités nous obtenons : C # l(E) 5 2 c(H) # 2 C* et ainsi
C
C*
# 2. En fait, ici, C* 5 9 avec (a, b, f, e, d, c, a) et *
, .
C
= =
11
9
1 22
Ĉ
On peut montrer que l’algorithme permettant d’obtenir cette solution approchée
est polynomial ; nous avons donc un algorithme polynomial avec une garantie relative de performance de rapport 2 pour le problème du voyageur de commerce euclidien (ce problème étant prouvé NP-difficile, il n’exite pas d’algorithme polynomial
fournissant une solution optimale, sauf si P 5 NP : ce qui est très improbable !).
Autre exemple : un algorithme polynomial avec garantie de
performance pour le problème du bin packing
Considérons n objets de même forme linéaire, dont les tailles a 1 , c , a n vérifient : 0 , a i , A. On cherche à placer ces objets dans des boîtes de taille A de
façon à utiliser un nombre minimal de boîtes. Par exemple ces objets peuvent être
des livres ; la ‘taille’ de chacun est son épaisseur ; on désir les ranger dans des étagères, chacune de longueur A ; on veut minimiser le nombre d’étagères à acheter. Ce
problème connu sous le nom de bin packing (mise en boîte) est NP-difficile. L’algorithme suivant permet d’obtenir une solution approchée : les objets sont placés un
à un dans les boîtes suivant l’ordre arbitraire 1, c , n. L’étape i (i 5 1, c , n) de
l’algorithme consiste à placer l’objet i dans une des boîtes déjà partiellement remplie
(sauf pour l’objet 1 rangé dans une boîte vide), si cela est possible (la somme des
tailles des objets placés dans chacune des boîtes ne doit pas dépasser la capacité A).
Si ce n’est pas possible, l’objet i est placé dans une nouvelle boîte.
ˆ
ˆ
ˆ
ˆ
ˆ