Algoritmo de Christofides

El algoritmo de Christofides es un algoritmo aproximado que permite resolver instancias del problema del viajante de comercio (designado convencionalmente por su acrónimo en inglés, TSP) en donde los pesos de las aristas del grafo satisfacen la desigualdad triangular. Fue desarrollado en 1976 por Nicos Christofides, profesor del Imperial College London.^[1]

Supongamos que $G=(V,w)$ representa una instancia del TSP, en donde $G$ es un grafo completo definido por: un conjunto $V$ de vértices o nodos y una función $w$ que asocia un peso o valor real positivo a cada arista del grafo $G$ .

Descripción

A continuación, se describen las fases del algoritmo en pseudocódigo:^[2]

Obtener el árbol recubridor mínimo T de G.
Sea O el conjunto de vértices de grado impar en T, hallar un apareamiento perfecto M de mínimo peso en el grafo completo sobre los vértices de O.
Combinar las aristas de M y T para crear el multigrafo H.
Obtener un ciclo euleriano en H (H se considera "euleriano" si es conexo y solo presenta vértices de grado par).
Obtener un ciclo hamiltoniano a partir del ciclo euleriano anterior, descartando los nodos visitados (shortcutting).

Demostración

El coste de la solución obtenida por el algoritmo es 3/2 de la solución óptima.

La prueba es la siguiente:^[3]

Sea A el conjunto de aristas de la solución óptima del TSP para G. Como (V,A) es conexo, contendrá varios árboles recubridores T, y por tanto, w(A) ≥ w(T). Además, sea B el conjunto de aristas de la solución óptima del TSP para el grafo completo sobre los vértices de O. Como los pesos asociados a las aristas son "triangulares" (visitar más nodos no reduce, en ningún caso, el coste total), se tiene que w(A) ≥ w(B). Se demuestra así que existe un apareamiento perfecto de vértices de O con peso tal que w(B)/2 ≤ w(A)/2, de forma que este límite constituye una cota superior para M (ya que M es un apareamiento perfecto de mínimo coste).

Debido a que O debe contener un número par de vértices, existe apareamiento perfecto. Sea e₁, ..., e_2k el (único) camino euleriano en (O,B). Es evidente que tanto e₁, e₃, ...,e_2k-1 como e₂, e₄, ..., e_2k son apareamientos perfectos, y que el peso de (al menos) uno de ellos es menor o igual que w(B)/2. Así, se tiene que w(M)+w(T) ≤ w(A) + w(A)/2, y de la desigualdad triangular se deduce que el algoritmo se aproxima en 3/2 al óptimo.

Referencias

↑ Erica Klarreich. «Computer Scientists Take Road Less Traveled.» (en inglés). Simons Fundation. Archivado desde el original el 3 de abril de 2013.
↑ «Definición del Algoritmo de Christofides.» (en inglés). National Institute of Standards and Technology (NIST).
↑ Christofides, Nicos (1976). «Worst-case analysis of a new heuristic for the travelling salesman problem». Graduate School of Industrial Administration (Report 388).

Datos: Q498144

[SimonF-1] Erica Klarreich. «Computer Scientists Take Road Less Traveled.» (en inglés). Simons Fundation. Archivado desde el original el 3 de abril de 2013.

[2] «Definición del Algoritmo de Christofides.» (en inglés). National Institute of Standards and Technology (NIST).

[3] Christofides, Nicos (1976). «Worst-case analysis of a new heuristic for the travelling salesman problem». Graduate School of Industrial Administration (Report 388).

[1]

[2]

[3]