Problème du voyageur de commerce et cas
euclidien
Julien Devevey
2018-2019
Ref : Cormen - Introduction to Algorithms p.1096 et 1112
Définition 1. Soit G = (V, E) un graphe complet et c : E → R+ une fonction
de valuation des arêtes telle que c(x, x) = 0, ∀x ∈ V et k ∈ N. Le problème du
voyageur de commerce est de savoir s’il existe un chemin qui passe par tous les
sommets du graphe une unique fois de coût total inférieur ou égal à k. On le
note TSP (pour Traveling Salesman Problem).
Proposition 2. TSP est NP-Complet.
Démonstration.
Etant donné une instance du problème, on utilise comme certificat la suite
des n sommets formant le cycle. Alors on vérifie linéairement que le coût de ce
cycle (la somme du coût de chacune des arêtes le composant) est bien inférieure
à k. Donc le problème est dans NP.
On va ensuite réduire HAM-CYCLE à TSP, car on sait que HAM-CYCLE est
NP-complet. Soit alors G = (V, E) une instance de HAM-CYCLE. On construit
alors une instance de TSP en posant :
c(i, j) = 0 si (i, j) ∈ E
= 1 sinon
L’instance de TSP est alors (G, c, 0) : en effet, s’il y a un cycle hamiltonien dans
G, ce cycle correspond bien à un cycle de coût 0 pour TSP. Et si TSP admet
un cycle de coût nul, c’est un cycle hamiltonien.
Théorème 3. On peut rajouter une hypothèse sur c qui est ∀(i, j, k) ∈ V 3 , c(i, j) ≤
c(i, k) + c(k, j), c’est à dire l’inégalité triangulaire. Dans ce cas, il existe une 2-
approximation au problème du voyageur de commerce.
Algorithme 4. L’algorithme suivant est une telle 2-approximation :
1
Algorithm 1 Approx-TSP
Entrée: G = (V, E), c
Sortie: Un cycle hamiltonien H
1: choisir un sommet r de V
2: calculer un arbre couvrant minimal T ayant r pour racine
3: H ← la liste des sommets dans l’ordre dans lequel ils sont visités dans un
parcours en profondeur de T
4: return H
Démonstration du théorème.
L’algorithme 4 peut être implémenté en utilisant l’algorithme de Prim, ce
qui permet de donner une complexité de l’ordre de O(|V |2 ) : l’algorithme est
polynomial.
Soit H ∗ un cycle optimal. Si on supprime une de ses arêtes, comme il passe
une et une seule fois par chaque sommet, on obtient un arbre couvrant, et chaque
arête a un coût positif. Ainsi, l’arbre couvrant minimal calculé ligne 2 a un coût
plus faible que celui d’un cycle optimal : c(T ) ≤ c(H ∗ ). Or dans un parcours en
profondeur P de T , on passe par chaque arête de l’arbre au plus deux fois, ce
qui donne l’inégalité c(P ) ≤ 2c(T ). Mais le parcours en profondeur n’est pas en
général un cycle hamiltonien, d’où la sélection que l’on fait quand on choisit de
ne retenir chaque sommet que la première fois qu’on le visite, ce qui donne le
cycle hamiltonien H (comme le graphe est complet, la donnée des n sommets
dans un certain ordre définit toujours un cycle hamiltonien).
On fait ensuite intervenir ici l’inégalité triangulaire pour dire que le fait
d’avoir supprimé des sommets n’augmente pas le coût du parcours : en effet, si
P contient le chemin (si , . . . , si+k ) et qu’il ne reste plus que (si , si+k ) dans H,
Pk
on a bien c(si , si+k ) ≤ j=1 c(si+j−1 , si+j ) par inégalité triangulaire.
Au final, avec toutes les inégalités qu’on a trouvées, on peut écrire que
c(H) ≤ 2c(H ∗ ), c’est à dire qu’on a bien une 2-approximation.
Remarque 5. Dans le cas où P 6= N P , on a que pour toute constante ρ,
il n’existe pas de ρ-approximation qui soit polynomiale pour le problème du
voyageur de commerce.
En pratique, le cas euclidien est celui qu’on rencontre le plus souvent. De
plus, il existe de meilleurs algorithmes que celui présenté ici (par exemple une
3/2-approximation).