2.2 Complexité des Problèmes
53
© Dunod – Toute reproduction non autorisée est un délit.
Exemple d’un algorithme polynomial avec garantie
de performance pour le problème du voyageur
de commerce euclidien
Nous allons ici donner l’exemple d’un algorithme polynomial ayant une garantie
relative de performance pour le problème du voyageur de commerce dans le cas où
les distances vérifient les inégalités triangulaires (cf. ci-dessous). Le problème du
voyageur de commerce ainsi qu’un algorithme (non polynomial) fournissant une
solution optimale sont présentés dans la section 4.10.1.
Nous considérons G 5 (X, A) un graphe non orienté complet de n sommets où
chaque arête [i, j] est valuée par un entier naturel c ij , appelé coût de l’arête [i, j]. On
suppose que les coûts satisfont l’inégalité triangulaire : pour tout triplet de sommets
{i, j, k} on a : c ij # c ik 1 c kj . Le problème du voyageur de commerce consiste à déterminer un cycle hamiltonien de longueur minimale.
L’instance suivante, comportant six sommets {a, b, c, d, e, f }, servira d’illustration
pour le déroulement de l’algorithme. Voici le tableau des coûts qui est symétrique :
b
b
a
c
c
d
d
e
e
f
1
1
1
2
2 2
3
3
3 4 4
2
2
2
2
L’algorithme est constitué de trois étapes, cf. Fig 2.2 ci-dessous :
La première consiste en la détermination d’un arbre couvrant de coût minimal qui
s’effectue en temps polynomial (le lecteur pourra se référer à la section 4.8). L’ensemble d’arêtes F 5 5 3a, b4, 3a, c 4, 3a, e4, 3e, f 4, 3e, d46 forme un arbre H 5 (X, F)
couvrant G de coût 7, minimal, pour l’exemple traité.
arbre H
graphe H
cycle C
1
1
a
a
a
b
b
b
c
c
c
d
d
d
e
e
e
f
f
f
1
2
2
Figure 2.2 La construction d’un cycle hamiltonien c
La seconde étape consiste à construire le graphe orienté symétrique Hr qui est
déduit de H en remplaçant chacune des ses arêtes [x, y] par les deux arcs (x, y) et
(y, x). Puis on construit dans Hr un circuit eulérien E (c-à-d empruntant tous les arcs
de Hr une fois et une seule). Dans notre exemple :
E 5 (a, b, a, c, a, e, d, e, f, e, a), qui a pour coût 14.
53
© Dunod – Toute reproduction non autorisée est un délit.
Exemple d’un algorithme polynomial avec garantie
de performance pour le problème du voyageur
de commerce euclidien
Nous allons ici donner l’exemple d’un algorithme polynomial ayant une garantie
relative de performance pour le problème du voyageur de commerce dans le cas où
les distances vérifient les inégalités triangulaires (cf. ci-dessous). Le problème du
voyageur de commerce ainsi qu’un algorithme (non polynomial) fournissant une
solution optimale sont présentés dans la section 4.10.1.
Nous considérons G 5 (X, A) un graphe non orienté complet de n sommets où
chaque arête [i, j] est valuée par un entier naturel c ij , appelé coût de l’arête [i, j]. On
suppose que les coûts satisfont l’inégalité triangulaire : pour tout triplet de sommets
{i, j, k} on a : c ij # c ik 1 c kj . Le problème du voyageur de commerce consiste à déterminer un cycle hamiltonien de longueur minimale.
L’instance suivante, comportant six sommets {a, b, c, d, e, f }, servira d’illustration
pour le déroulement de l’algorithme. Voici le tableau des coûts qui est symétrique :
b
b
a
c
c
d
d
e
e
f
1
1
1
2
2 2
3
3
3 4 4
2
2
2
2
L’algorithme est constitué de trois étapes, cf. Fig 2.2 ci-dessous :
La première consiste en la détermination d’un arbre couvrant de coût minimal qui
s’effectue en temps polynomial (le lecteur pourra se référer à la section 4.8). L’ensemble d’arêtes F 5 5 3a, b4, 3a, c 4, 3a, e4, 3e, f 4, 3e, d46 forme un arbre H 5 (X, F)
couvrant G de coût 7, minimal, pour l’exemple traité.
arbre H
graphe H
cycle C
1
1
a
a
a
b
b
b
c
c
c
d
d
d
e
e
e
f
f
f
1
2
2
Figure 2.2 La construction d’un cycle hamiltonien c
La seconde étape consiste à construire le graphe orienté symétrique Hr qui est
déduit de H en remplaçant chacune des ses arêtes [x, y] par les deux arcs (x, y) et
(y, x). Puis on construit dans Hr un circuit eulérien E (c-à-d empruntant tous les arcs
de Hr une fois et une seule). Dans notre exemple :
E 5 (a, b, a, c, a, e, d, e, f, e, a), qui a pour coût 14.