Algorithme de Christofides

Un exemple de tournée du voyageur de commerce en Allemagne.

Le problème du voyageur de commerce (dans sa version optimisation[4]) est le problème suivant : étant donné un ensemble de villes reliées entre elles par des routes, trouver l'itinéraire le plus court passant par chaque ville une et une seule fois. En termes de graphe, on cherche le cycle hamiltonien le plus court. C'est un problème d'optimisation NP-difficile classique[5].

Plusieurs cas particuliers ont été étudiés, notamment le cas dit « métrique » où les arêtes respectent l'inégalité triangulaire c'est-à-dire que pour tout triplet de sommet ${\displaystyle u,v,w}$, on a ${\displaystyle w(u,v)+w(v,w)\geq w(u,w)}$.

Dans le cas général, cet algorithme est en fait une heuristique, cependant dans le cas métrique, on peut montrer que la solution est au plus 3/2 fois plus longue que l'optimal. On dit que le facteur d'approximation est de 3/2.

L'algorithme résout deux sous-problèmes considérés «faciles», car appartenant à la classe P : le problème de l'arbre couvrant de poids minimal[6] et celui du couplage de poids minimum[7].

Exemple

	Étant donné un graphe ${\displaystyle G=\left(V,E\right)}$ dont les poids respectent l'inégalité triangulaire.
	Calculer un arbre couvrant de poids minimum ${\displaystyle T}$.
	Calculer l'ensemble ${\displaystyle I}$ des sommets de degrés impairs dans ${\displaystyle T}$.
	Considérer le graphe induit par ${\displaystyle I}$ (${\displaystyle G|_{I}}$).
	Calculer un couplage de poids minimum ${\displaystyle M}$ dans ${\displaystyle G|_{I}}$.
	Faire l'union du couplage et de l'arbre couvrant (${\displaystyle T\cup M}$).
	Calculer le tour eulérien sur ${\displaystyle T\cup M}$ : (A-B-C-A-D-E-A).
	Enlever les sommets qui apparaissent deux fois : (A-B-C-D-E-A). Ce cycle est la sortie de l'algorithme.

Pour le problème du chemin hamiltonien (Path TSP), qui est la variante du problème du voyageur de commerce où un départ et une arrivée sont imposées, des variantes de l'algorithme de Christofides sont utilisées pour obtenir de bonnes approximations[10] - [11].

Le problème dans le cas métrique est APX-difficile, même avec des poids 1 ou 2[12], ce qui empêche l'existence d'un schéma d'approximation en temps polynomial. Le facteur de 3/2 est en fait le meilleur facteur connu[13].

Dans son article, Christofides a amélioré le facteur d'approximation du problème de 2 à 3/2[9]. Il a en fait affiné l'algorithme précédent qui consistait à construire un arbre couvrant minimal et à le parcourir[14].

Depuis les années de 2010, une nouvelle approche basée sur l'algorithme, appelée best-of-many, a permis de faire avancer certains cas particuliers et se révèle plus efficace dans la pratique[15]. Elle consiste schématiquement à utiliser l'algorithme de Christofides, sur plusieurs instances définies à partir d'une solution à la relaxation de Held et Karp[16].

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Christofides algorithm » (voir la liste des auteurs).

• Nicos Christofides, « Worst-case analysis of a new heuristic for the travelling salesman problem », Technical Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh,‎ 1976
• (en) Gerhard Reinelt, The Traveling Salesman, Computational Solutions for TSP Applications, vol. 840, Springer, coll. « Lecture Notes in Computer Science », 1994, 223 p. (ISBN 978-3-540-58334-9, BNF 37482407, lire en ligne)
• Gilbert Laporte, « The traveling salesman problem: An overview of exact and approximate algorithms », European Journal of Operational Research, vol. 59, n^o 2,‎ 1992, p. 231-247

• « Présentation et preuve de l'algorithme (par Alain Hertz) » (consulté le 28 avril 2014)
• Le problème du voyageur de commerce métrique (Minimum metric traveling salesperson) sur le Compendium of NP optimization problems.