El algoritmo de Christofides o algoritmo de Christofides–Serdyukov es un algoritmo para encontrar soluciones aproximadas al problema del viajante , en instancias donde las distancias forman un espacio métrico (son simétricas y obedecen a 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 lleva el nombre de Nicos Christofides y Anatoliy I. Serdyukov ( en ruso : Анатолий Иванович Сердюков ); este último lo descubrió de forma independiente en 1976 (pero la publicación está fechada en 1978). [2] [3] [4]
Sea G = ( V , w ) una instancia del problema del viajante de comercio. Es decir, G es un grafo completo en el conjunto V de vértices, y la función w asigna un peso real no negativo a cada arista de G . De acuerdo con la desigualdad triangular, para cada tres vértices u , v y x , debería darse el caso de que w ( uv ) + w ( vx ) ≥ w ( ux ) .
Luego el algoritmo se puede describir en pseudocódigo de la siguiente manera. [1]
Los pasos 5 y 6 no necesariamente producen un único resultado; por ello, la heurística puede proporcionar varios caminos diferentes.
La complejidad del peor caso del algoritmo está dominada por el paso de coincidencia perfecta, que tiene complejidad. [2] El artículo de Serdyukov afirmaba que tenía complejidad, [4] porque el autor solo conocía un algoritmo de coincidencia perfecta menos eficiente. [3]
El costo de la solución producida por el algoritmo está dentro de los 3/2 del óptimo. Para probar esto, sea C el viaje óptimo del viajante de comercio. Quitar una arista de C produce un árbol de expansión, que debe tener un peso al menos igual al del árbol de expansión mínimo, lo que implica que w ( T ) ≤ w ( C ) - límite inferior del costo de la solución óptima.
El algoritmo aborda el problema de que T no es un grafo 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 tales vértices. El algoritmo encuentra un M coincidente perfecto con peso mínimo entre los 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 rutas: aquellas en las que el primer vértice de la ruta en orden cíclico tiene un número impar y aquellas en las que el primer vértice de la ruta tiene un número par. Cada conjunto de rutas corresponde a una correspondencia perfecta de O que coincide con los dos puntos finales de cada ruta, y el peso de esta correspondencia es como máximo igual al peso de las rutas. De hecho, cada punto final de la ruta estará conectado a otro punto final, que también tiene un número impar de visitas debido a la naturaleza del recorrido.
Dado que estos dos conjuntos de caminos dividen los bordes 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 . Al sumar los pesos de T y M se obtiene el peso del recorrido de Euler, como máximo 3 w ( C )/2 . Gracias a la desigualdad triangular, aunque el recorrido de Euler podría 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 3 w ( C )/2 . [1]
Existen entradas al problema del viajante de comercio 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 esas clases de entradas está formada por un camino de n vértices, con aristas del camino que tienen peso 1 , junto con un conjunto de aristas que conectan vértices separados por dos pasos en el camino con peso 1 + ε para un número ε elegido cercano a cero pero positivo.
Todos los bordes 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, cuya coincidencia perfecta consiste en un solo borde con peso aproximadamente n /2 .
La unión del árbol y el emparejamiento es un ciclo, sin atajos posibles, y con peso aproximadamente 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 puntos finales del camino, y tiene un peso total (1 + ε )( n − 2) + 2 , cercano a n para valores pequeños de ε . Por lo tanto, obtenemos una relación de aproximación de 3/2. [5]
Este algoritmo sigue siendo el mejor algoritmo de aproximación de tiempo polinomial para el problema planteado que ha sido revisado exhaustivamente por pares por la comunidad científica relevante para el problema del viajante de comercio en espacios métricos generales. En julio de 2020, Karlin, Klein y Gharan publicaron una preimpresión en la que presentaron un nuevo algoritmo de aproximación y afirmaron que su relación de aproximación es 1,5 − 10 −36 . El suyo es un algoritmo aleatorio y sigue principios similares al algoritmo de Christofides, pero utiliza un árbol elegido aleatoriamente de una distribución aleatoria cuidadosamente elegida en lugar del árbol de expansión mínima. [6] [7] El artículo se publicó en STOC'21 [8] donde recibió un premio al mejor artículo. [9]
En el caso especial del espacio euclidiano , para cualquier c > 0, donde d es el número de dimensiones en el espacio euclidiano, hay un algoritmo de tiempo polinomial que encuentra un recorrido de longitud como máximo (1 + 1/ c ) veces la óptima para instancias geométricas de TSP en
Esto se llama esquema de aproximación de tiempo polinomial (PTAS). [10] 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.
