Algorisme de Christofides

En teoria de grafs, l'algorisme de Christofides és un algorisme que serveix per resoldre el problema del viatjant de comerç, en el cas en què les distàncies formen un espai mètric (són simètriques i compleixen la desigualtat triangular).^[1] Es tracta d'un algorisme d'aproximació que garanteix que les seves solucions es trobaran en un factor màxim de 3/2 respecte a la distància total de la solució òptima. i rep el nom de Nicos Christofides, que el va publicar el 1976.^[2] A data de 2015, és el millor ratio d'aproximació que s'ha demostrat pel problema del viatjant de comerç en espais mètrics generals, tot i que es coneixen millors aproximacions per a alguns casos particulars.

Algorisme[modifica]

Sigui $G = (V, w)$ un exemple del problema del viatjant de comerç. Això vol dir que $G$ és un graf complet del conjunt $V$ de vèrtexs, i la funció $w$ assigna un pes real no negatiu a cada aresta de $G$ . Segons la desigualtat triangular, per a cada tres vèrtexs $u$ , $v$ , i $x$ , s'ha de complir que $w (uv) + w (vx) \geq w (ux)$ .

Llavors l'algorisme es pot escriure en pseudocodi com segueix:^[1]

Crear un arbre generador mínim $T$ de $G$ .
Sigui $O$ el conjunt de vèrtexs amb grau senar a $T$ . A través del lema de l'encaixada de mans, $O$ té un nombre parell de vèrtexs.
Trobar un aparellament perfecte de pes mínim $M$ en el subgraf induït a partir dels vèrtexs de $O$ .
Combinar les arestes de $M$ i $T$ per formar un multigraf connex $H$ en què cada vèrtex té un grau parell.
Formar un camí eulerià a $H$ .
Convertir el circuit trobat en el pas previ en un camí hamiltonià saltant vèrtexs repetits (fent dreceres).

Exemple[modifica]

La següent taula mostra un exemple d'ús de l'algorisme de Christofides:

	Es parteix d'un graf $G$ complet amb arestes les distàncies de les quals compleixen la desigualtat triangular.
	Calcular l'arbre generador mínim $T$
	Trobar el conjunt de vèrtexs $O$ amb valència (nombre d'arestes que surten d'un vèrtex) senar a $T$
	Es forma el subgraf $G'$ de $G$ usant només els vèrtexs de $O$
	Es realitza un aparellament perfecte (aquell que aparella els vèrtexs dos a dos) $M$ de mínim pes en el subgraf $G'$
	S'uneix l'aparellament amb l'arbre generador $T \cup M$ per formar un multigraf eulerià
	Es calcula el camí eulerià
	Finalment es treuen els vèrtexs repetits. En unit C amb D en aquest cas, s'assegura una reducció de distància a partir de la desigualtat triangular.

Referències[modifica]

↑ ^1,0 ^1,1 Goodrich, Michael T.; Tamassia, Roberto. «18.1.2 The Christofides Approximation Algorithm». A: Algorithm Design and Applications. Wiley, 2015, p. 513–514.
↑ Nicos Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem, Report 388, Graduate School of Industrial Administration, CMU, 1976.

Enllaços externs[modifica]

NIST Definició de l'algorisme de Christofides

[gt-1] 1,0 ^1,1 Goodrich, Michael T.; Tamassia, Roberto. «18.1.2 The Christofides Approximation Algorithm». A: Algorithm Design and Applications. Wiley, 2015, p. 513–514.

[2] Nicos Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem, Report 388, Graduate School of Industrial Administration, CMU, 1976.

[1]

[2]