Algoritmo de Christofides

El algoritmo de Christofides o algoritmo de Christofides-Serdyukov es un algoritmo para encontrar soluciones aproximadas al problema del viajante de comercio , en instancias donde las distancias forman un espacio métrico (son simétricas y cumplen la desigualdad triangular ). ^{[ 1 ]} Es un algoritmo de aproximación que garantiza que sus soluciones estarán dentro de un factor de 3/2 de la longitud de la solución óptima, y ​​recibe su nombre de Nicos Christofides y Anatoliy Serdyukov ( en ruso : Анатолий Иванович Сердюков ). Christofides publicó el algoritmo en 1976; Serdyukov lo descubrió independientemente en 1976, pero lo publicó en 1978. ^{[ 2 ] [ 3 ] [ 4 ]}

Sea G = ( V , w ) una instancia del problema del viajante. Es decir, G es un grafo completo sobre el conjunto V de vértices, y la función w asigna un peso real no negativo a cada arista de G. Según la desigualdad triangular, para cada tres vértices u , v , y x , debe cumplirse que w ( uv ) + w ( vx ) ≥ w ( ux ) .

Entonces el algoritmo se puede describir en pseudocódigo de la siguiente manera. ^{[ 1 ]}

1. Crea un árbol de expansión mínima T de G.
2. Sea O el conjunto de vértices con grado impar en T. Por el lema del apretón de manos , O tiene un número par de vértices.
3. Encuentra un emparejamiento perfecto de peso mínimo M en el subgrafo inducido en G por O.
4. Combina las aristas de M y T para formar un multigrafo conexo H en el que cada vértice tenga grado par.
5. Formar un circuito euleriano en H.
6. Convierta el circuito encontrado en el paso anterior en un circuito hamiltoniano omitiendo vértices repetidos ( atajo ).

Los pasos 5 y 6 no necesariamente dan como resultado un único resultado; por lo tanto, la heurística puede ofrecer varios caminos diferentes.

El coste de la solución obtenida mediante el algoritmo se encuentra dentro de 3/2 del óptimo. Para demostrarlo, sea C el recorrido óptimo del viajante. Al eliminar una arista de C se obtiene un árbol de expansión, cuyo peso debe ser al menos igual al del árbol de expansión mínimo, lo que implica que w ( T ) ≤ w ( C ) , límite inferior del coste de la solución óptima.

El algoritmo resuelve el problema de que T no sea un recorrido identificando todos los vértices de grado impar en T ; dado que la suma de los grados en cualquier grafo es par (según el lema del apretón de manos ), existe un número par de dichos vértices. El algoritmo encuentra un emparejamiento perfecto de peso mínimo M entre los vértices de grado impar.

A continuación, numeramos los vértices de O en orden cíclico alrededor de C y dividimos C en dos conjuntos de caminos: aquellos en los que el primer vértice del camino en orden cíclico tiene un número impar y aquellos en los que el primer vértice del camino tiene un número par. Cada conjunto de caminos corresponde a un emparejamiento perfecto de O que coincide con los dos extremos de cada camino, y el peso de este emparejamiento es como máximo igual al peso de los caminos. De hecho, cada extremo de un camino estará conectado a otro extremo, que también tiene un número impar de visitas debido a la naturaleza del recorrido.

Dado que estos dos conjuntos de caminos dividen las aristas de C , uno de los dos conjuntos tiene como máximo la mitad del peso de C , y gracias a la desigualdad triangular, su emparejamiento correspondiente tiene un peso que también es como máximo la mitad del peso de C. El emparejamiento perfecto de peso mínimo no puede tener un peso mayor, por lo que w ( M ) ≤ w ( C )/2 . La suma de los pesos de T y M da el peso del recorrido de Euler, como máximo 3w ( C )/2 . Gracias a la desigualdad triangular, aunque el recorrido de Euler pueda volver a visitar vértices, los atajos no aumentan el peso, por lo que el peso de la salida también es como máximo 3w ( C ) /2 . ^{[ 1 ]}

Existen entradas para el problema del viajante que hacen que el algoritmo de Christofides encuentre una solución cuya razón de aproximación es arbitrariamente cercana a 3/2 . Una de estas clases de entradas está formada por un camino de n vértices, con aristas del camino que tienen un peso de 1 , junto con un conjunto de aristas que conectan vértices separados por dos pasos en el camino con un peso de 1 + ε para un número ε elegido cercano a cero pero positivo.

Todas las aristas restantes del grafo completo tienen distancias dadas por los caminos más cortos en este subgrafo. Entonces, el árbol de expansión mínimo estará dado por el camino, de longitud n − 1 , y los únicos dos vértices impares serán los puntos finales del camino, cuyo emparejamiento perfecto consiste en una sola arista con un peso aproximado de n /2 .

La unión del árbol y el emparejamiento es un ciclo, sin atajos posibles, y con un peso aproximado de 3 n /2 . Sin embargo, la solución óptima utiliza las aristas de peso 1 + ε junto con dos aristas de peso 1 incidentes a los extremos del camino, y tiene un peso total (1 + ε )( n − 2) + 2 , cercano a n para valores pequeños de ε . Por lo tanto, obtenemos una razón de aproximación de 3/2. ^{[ 5 ]}

Este algoritmo ya no es el mejor algoritmo de aproximación en tiempo polinomial para el TSP en espacios métricos generales. Karlin, Klein y Gharan introdujeron un algoritmo de aproximación aleatorio con una razón de aproximación de 1,5 − 10 ⁻³⁶ . Sigue principios similares al algoritmo de Christofides, pero utiliza un árbol elegido aleatoriamente de una distribución aleatoria cuidadosamente seleccionada en lugar del árbol de expansión mínima. ^{[ 6 ] [ 7 ]} El artículo recibió un premio al mejor artículo en el Simposio de Teoría de la Computación de 2021. ^{[ 8 ]}  

En el caso especial del espacio euclidiano de dimensión${\displaystyle d}$, para cualquier${\displaystyle c>0}$, existe un algoritmo de tiempo polinomial que encuentra un recorrido de longitud como máximo${\displaystyle 1+{\tfrac {1}{c}}}$veces el óptimo para instancias geométricas del TSP en

${\displaystyle O\left(n(\log n)^{(O(c{\sqrt {d}}))^{d-1}}\right)}$tiempo.

Para cada constante${\displaystyle c}$Este límite de tiempo está en tiempo polinomial , por lo que se le llama esquema de aproximación en tiempo polinomial (PTAS). ^{[ 9 ]} Sanjeev Arora y Joseph SB Mitchell recibieron el Premio Gödel en 2010 por su descubrimiento simultáneo de un PTAS para el TSP euclidiano.

Los métodos basados ​​en el algoritmo de Christofides-Serdyukov también pueden utilizarse para aproximar el problema de la grúa apiladora , una generalización del problema del viajante en la que la entrada consiste en pares ordenados de puntos de un espacio métrico que deben recorrerse consecutivamente y en orden. Para este problema, se alcanza una razón de aproximación de 9/5. ^{[ 10 ]}

• Definición del algoritmo de Christofides del NIST