Voir la source de Algorithme de Christofides

L''''algorithme de Christofides''' est un [[algorithme d'approximation]] pour le [[problème du voyageur de commerce]], dans le cas métrique, et que l'[[inégalité triangulaire]] est respectée. L'analyse de cet algorithme est due à [[Nicos Christofides]] and [[Anatoliy I. Serdyukov]], qui l'ont découvert indépendamment en 1976<ref>{{ouvrage|langue=en|auteur=Nicos Christofides|année=1976|titre=Worst-case analysis of a new heuristic for the travelling salesman problem|éditeur=Graduate School of Industrial Administration, CMU|url=https://apps.dtic.mil/dtic/tr/fulltext/u2/a025602.pdf|passage=Report 388}}.</ref>{{,}}<ref>{{article|auteur1=René van Bevern|auteur2=Viktoriaa A. Slugina|année=2020|titre=A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem|journal=Historia Mathematica|doi=10.1016/j.hm.2020.04.003|arxiv=2004.02437|s2cid=214803097}}.</ref>{{,}}<ref>{{article|auteur=Anatoliy I. Serdyukov|année=1978|titre=О некоторых экстремальных обходах в графах|langue=ru|url=http://nas1.math.nsc.ru/aim/journals/us/us17/us17_007.pdf|journal=Upravlyaemye Sistemy|volume=17|pages=76–79}}.</ref>.

== Problème du voyageur de commerce métrique ==
[[Image:TSP Deutschland 3.png|vignette|Un exemple de tournée du voyageur de commerce en Allemagne.]]
{{article détaillé|Problème du voyageur de commerce}}

Le problème du voyageur de commerce (dans sa version optimisation<ref>Au sens de [[Optimisation combinatoire|problème d'optimisation]] par contraste avec le [[problème de décision]] associé.</ref>) 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<ref>Présent notamment dans la liste des [[21 problèmes NP-complets de Karp]] : {{Reducibility Karp 1972}}. </ref>.

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 <math>u,v,w</math>, on a <math>w(u,v)+w(v,w)\geq w(u,w)</math>.

== Algorithme ==
Dans le cas général, cet algorithme est en fait une [[heuristique (mathématiques)|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 [[algorithme d'approximation|facteur d'approximation]] est de 3/2.

L'algorithme résout deux sous-problèmes considérés «faciles», car appartenant à la [[P (complexité)|classe P]] : le problème de l'[[arbre couvrant de poids minimal]]<ref>Pour lequel on peut utiliser par exemple les algorithmes polynomiaux de [[algorithme de Prim|Prim]], [[algorithme de Kruskal|Kruskal]] ou [[Algorithme de Borůvka|Borůvka]].</ref> et celui du [[couplage (théorie des graphes)|couplage]] de poids minimum<ref>Par exemple avec l'[[algorithme d'Edmonds pour les couplages]].</ref>.

=== Pseudo-code ===
En [[pseudo-code]]<ref>Adapté de {{Lien web|langue= fr |url=http://www.gerad.ca/~alainh/Euler-Hamilton.pdf |titre= Présentation et preuve de l'algorithme (par Alain Hertz) |site=   |consulté le=28 avril 2014}}.</ref> :
# Calculer un [[arbre couvrant de poids minimal]] <math>T</math> de <math>G</math> ;
# Soit <math>I</math> l'ensemble des sommets de [[degré (théorie des graphes)|degré]] [[impair]] dans <math>T</math>, calculer un [[Couplage (théorie des graphes)|couplage]] parfait <math>M</math> de poids minimum dans le sous-graphe induit par les sommets de <math>I</math> ;
# On définit un [[multigraphe]] <math>H</math> à partir des arêtes issues de <math>M</math> et <math>T</math> ;
# Trouver un [[cycle eulérien]] dans <math>H</math> (H est eulérien car il est connexe et tous les sommets sont de degré pair) ;
# Transformer le cycle eulérien en un [[cycle hamiltonien]] en supprimant les éventuels passages en double sur certains sommets.

=== Exemple ===

{| class="wikitable"
|-
|[[Fichier:Metrischer_Graph_mit_5_Knoten.svg|160px]]|| Étant donné un graphe <math>G=\left(V,E\right)</math> dont les poids respectent l'inégalité triangulaire.
|-
|[[Fichier:Christofides MST.svg|160px]] || Calculer un arbre couvrant de poids minimum <math>T</math>.
|-
|[[Fichier:V'.svg|160px]] || Calculer l'ensemble  <math>I</math> des sommets de degrés impairs dans <math>T</math>.
|-
|[[Fichier:G V'.svg|160px]] || Considérer le graphe induit par <math>I</math> (<math>G|_{I}</math>).
|-
|[[Fichier:Christofides Matching.svg|160px]] || Calculer un couplage de poids minimum <math>M</math> dans <math>G|_{I}</math>.
|-
|[[Fichier:TuM.svg|160px]] || Faire l'union du couplage et de l'arbre couvrant (<math>T\cup M</math>).
|-
|[[Fichier:Eulertour.svg|160px]] || Calculer le tour eulérien sur <math>T\cup M</math> : (A-B-C-A-D-E-A).
|-
|[[Fichier:Eulertour_bereinigt.svg|160px]] || Enlever les sommets qui apparaissent deux fois : (A-B-C-D-E-A). Ce cycle est la sortie de l'algorithme.
|}

=== Facteur d'approximation dans le cas métrique ===
Soit <math>U</math> le cycle hamiltonien de poids minimum, et <math>c(U)</math> son poids.

L'arbre couvrant de poids minimum <math>T</math> est de poids inférieur ou égal au poids de U (c'est-à-dire <math>c(T)\leq c(U)</math>), car en enlevant une arête au cycle on obtient un arbre couvrant.

Le couplage trouvé par l’algorithme est de poids inférieur ou égal à <math>0.5 c(U)</math>. En effet, si on considère le cycle hamiltonien de poids minimum sur le sous graphe induit par les sommets de degré impair, on a un poids inférieur ou égal à <math>c(U)</math> du fait de l'inégalité triangulaire, et en prenant une arête sur deux de ce cycle (qui est de longueur paire puisque constitué d'un nombre pair de sommets) on obtient un couplage qui est de poids inférieur à la moitié du poids du cycle (si ce n'est pas le cas on peut prendre le complémentaire).

D'où un poids final majoré par <math>c(T)+0,5 c(U)\leq 3/2 c(U)</math> : noter que la transformation du cycle eulérien en cycle hamiltonien ne peut pas faire croître le poids grâce à l'inégalité triangulaire.

=== Complexité de l'algorithme ===

L'algorithme a une [[complexité en temps|complexité cubique]]<ref name= christofides>{{harvsp|Christofides|1976}}</ref>.

== Variantes ==

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<ref>
{{article
 |titre=Analysis of Christofides' heuristic: Some paths are more difficult than cycles
 | auteur= JA Hoogeveen, 
 | périodique=Operations Research Letters
 | volume=10
 | numéro=5
 | passage=291-295
 |année=1991
 | éditeur=Elsevier
}}</ref>{{,}}<ref>
{{chapitre
 | auteur1   = Hyung-Chan An
 | auteur2 = Robert Kleinberg 
 | auteur3 = David B. Shmoys
 | titre chapitre    = Improving christofides' algorithm for the s-t path {TSP}
 | titre ouvrage = Proceedings of the 44th Symposium on Theory of Computing Conference (STOC) 2012, New York, NY, USA, May 19 - 22, 2012
 | passage     = 875-886
 | année  = 2012
}}</ref>.

== Contexte et historique ==

Le problème dans le cas métrique est [[APX (complexité)|APX-difficile]], même avec des poids 1 ou 2<ref>
Voir {{article
 | titre=The traveling salesman problem with distances one and two
 | nom1=Papadimitriou |prénom1 = Christos H. |lien auteur1 = Christos Papadimitriou
 | nom2 = Yannakakis | prénom2 = Mihalis | lien auteur2 = Mihalis Yannakakis
 | périodique=Mathematics of Operations Research
 | volume=18 | numéro=1 | passage = 1--11
 | année = 1993 
 | éditeur = INFORMS }}. Dans le cas des poids 1-2, l'article montre aussi que l'on peut obtenir une meilleure approximation : 7/8.</ref>, 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<ref>[http://www.csc.kth.se/~viggo/wwwcompendium/node105.html#5239 Le problème du voyageur de commerce métrique] (Minimum metric traveling salesperson) sur le ''[http://www.csc.kth.se/~viggo/wwwcompendium/ Compendium of NP optimization problems]''.</ref>.

Dans son article, Christofides a amélioré le facteur d'approximation du problème de 2 à 3/2<ref name = christofides/>. Il a en fait affiné l'algorithme précédent qui consistait à construire un arbre couvrant minimal et à le parcourir<ref>Une description précise et un survey sur le TSP peuvent être trouvés dans {{harvsp|Laporte|1992}}.</ref>.

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<ref>
{{chapitre
| auteur1   = Kyle Genova
| auteur2 = [[David P. Williamson]]
| titre chapitre  = An Experimental Evaluation of the Best-of-Many Christofides' Algorithm for the Traveling Salesman Problem
|titre ouvrage = Algorithms - {ESA} 2015 - 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings
| passage     = 570--581
|année      = 2015
| doi       = 10.1007/978-3-662-48350-3_48
}}</ref>. Elle consiste schématiquement à utiliser l'algorithme de Christofides, sur plusieurs instances définies à partir d'une solution à la relaxation de Held et Karp<ref>Voir l'article [[Problème du voyageur de commerce]].</ref>.

== Notes et références ==
{{Traduction/Référence|en|Christofides algorithm|593879139}}
<references />

== Bibliographie ==
* {{article
 | titre=Worst-case analysis of a new heuristic for the travelling salesman problem
 | nom =Christofides |prénom = Nicos
 | année=1976
 | périodique = Technical Report 388, Graduate School of Industrial Administration, [[Université Carnegie-Mellon|Carnegie-Mellon University]], Pittsburgh}}
* {{Ouvrage
 | langue=en
 | prénom1=Gerhard
 | nom1=Reinelt
 | titre=The Traveling Salesman, Computational Solutions for TSP Applications
 | volume=840
 | éditeur=Springer
 | collection=Lecture Notes in Computer Science
 | année=1994
 | pages totales=223
 | isbn=978-3-540-58334-9
 | isbn10=3-540-58334-3
 | bnf=37482407
 | lire en ligne=http://f3.tiera.ru/2/Cs_Computer%20science/CsAl_Algorithms/Reinelt%20G.%20The%20traveling%20salesman%20%28Springer,%201994%29%28ISBN%203540583343%29%28230s%29_CsAl_.pdf
}}
* {{article
 | titre=The traveling salesman problem: An overview of exact and approximate algorithms
 | nom=Laporte |prénom= Gilbert
 | périodique=European Journal of Operational Research
 | volume=59 | numéro =2
 | passage=231-247
 | année=1992}}

== Liens externes ==
* {{Lien web|langue= fr |url=http://www.gerad.ca/~alainh/Euler-Hamilton.pdf |titre= Présentation et preuve de l'algorithme (par Alain Hertz) |site=   |consulté le=28 avril 2014}}
* [http://www.csc.kth.se/~viggo/wwwcompendium/node105.html#5239 Le problème du voyageur de commerce métrique] (Minimum metric traveling salesperson) sur le ''[http://www.csc.kth.se/~viggo/wwwcompendium/ Compendium of NP optimization problems]''.

{{Portail|informatique théorique}}

[[Catégorie:Algorithme de la théorie des graphes|Christofides]]