El algoritmo de Christofides o el 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 del triángulo ). [1] Es un algoritmo de aproximación que garantiza que sus soluciones estarán dentro de un factor de 3/2 de la longitud óptima de la solución, y lleva el nombre de Nicos Christofides y Anatoliy I. Serdyukov , quienes lo descubrieron de forma independiente en 1976. [2] [3] [4]
Este algoritmo sigue siendo el mejor algoritmo de aproximación de tiempo polinomial que ha sido revisado minuciosamente por pares por la comunidad científica relevante para el problema del vendedor ambulante en espacios métricos generales. Sin embargo, en julio de 2020, Karlin, Klein y Gharan publicaron una preimpresión en la que introdujeron un algoritmo de aproximación novedoso y afirmaron que su relación de aproximación es 1,5 - 10 −36 . Su método sigue principios similares al algoritmo de Christofides, pero utiliza un árbol elegido al azar de una distribución aleatoria cuidadosamente elegida en lugar del árbol de expansión mínimo. [5] [6]
Algoritmo
Sea G = ( V , w ) un ejemplo del problema del viajante. 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 borde de G . Según la desigualdad del triángulo, por cada tres vértices u , v y x , debería darse el caso de que w ( uv ) + w ( vx ) ≥ w ( ux ) .
Entonces, el algoritmo se puede describir en pseudocódigo de la siguiente manera. [1]
- Crear un árbol de expansión mínima T de G .
- Deje O el conjunto de vértices con impar grado en T . Según el lema del apretón de manos , O tiene un número par de vértices.
- Encontrar un mínimo peso perfecta coincidencia de M en el subgrafo inducido dado por los vértices de O .
- Combine las aristas de M y T para formar un H multigrafo conectado en el que cada vértice tiene un grado par.
- Formar un circuito euleriano en H .
- Convierta el circuito encontrado en el paso anterior en un circuito hamiltoniano omitiendo vértices repetidos ( atajo ).
Relación de aproximación
El costo de la solución producida por el algoritmo está dentro de 3/2 del óptimo. Para probar esto, dejemos que C sea el viaje óptimo para los vendedores ambulantes. Quitar un borde 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 ) . Luego, numere los vértices de O en orden cíclico alrededor de C , y divida C en dos conjuntos de caminos: aquellos en los que el primer vértice de camino en orden cíclico tiene un número impar y aquellos en los que el primer vértice de camino tiene un número par. . Cada conjunto de rutas corresponde a una coincidencia perfecta de O que coincide con los dos puntos finales de cada ruta, y el peso de esta coincidencia es como máximo igual al peso de las rutas. Dado que estos dos conjuntos de trayectorias de partición de los bordes de C , uno de los dos conjuntos tiene a lo sumo la mitad del peso de C , y gracias a la desigualdad triangular su correspondiente juego tiene un peso que es también a lo sumo la mitad del peso de C . La combinación perfecta de peso mínimo no puede tener un peso mayor, por lo que w ( M ) ≤ w ( C ) / 2 . Sumando los pesos de T y M da el peso del recorrido de Euler, como máximo 3 w ( C ) / 2 . Gracias a la desigualdad del triángulo, el atajo no aumenta el peso, por lo que el peso de la salida también es como máximo 3 w ( C ) / 2 . [1]
Límites inferiores
Existen entradas para el problema del viajante que hacen que el algoritmo de Christofides encuentre una solución cuya relación de aproximación sea arbitrariamente cercana a 3/2. Una de estas clases de entradas está formada por una ruta de n vértices, con los bordes de la ruta que tienen un peso 1 , junto con un conjunto de bordes que conectan los vértices separados por dos pasos en la ruta con un peso 1 + ε para un número ε elegido cercano a cero pero positivo. Todos los bordes restantes del gráfico completo tienen distancias dadas por los caminos más cortos en este subgrafo. Entonces, el árbol de expansión mínimo vendrá dado por la ruta, de longitud n - 1 , y los únicos dos vértices impares serán los puntos finales de la ruta, cuya coincidencia perfecta consiste en un solo borde con un peso aproximado n / 2 . La unión del árbol y el emparejamiento es un ciclo, sin posibles atajos, y con un peso aproximado de 3 n / 2 . Sin embargo, la solución óptima usa los bordes de peso 1 + ε junto con dos bordes de peso- 1 incidentes a los puntos finales de la ruta, y tiene un peso total (1 + ε ) ( n - 2) + 2 , cercano an para pequeños valores de ε . Por tanto, obtenemos una relación de aproximación de 3/2. [7]
Ejemplo
Dado: gráfica completa cuyos pesos de aristas obedecen a la desigualdad del triángulo | |
Calcular el árbol de expansión mínimo T | |
Calcule el conjunto de vértices O con grado impar en T | |
Forme el subgrafo de G usando solo los vértices de O | |
Construya una M de coincidencia perfecta de peso mínimo en este subgrafo | |
Unir el árbol de coincidencia y expansión T ∪ M para formar un multigraph euleriano | |
Calcular el recorrido de Euler | |
Eliminar vértices repetidos, dando la salida del algoritmo |
Referencias
- ↑ a b c Goodrich, Michael T .; Tamassia, Roberto (2015), "18.1.2 El algoritmo de aproximación de Christofides", Diseño y aplicaciones de algoritmos , Wiley, págs. 513–514.
- ^ Christofides, Nicos (1976), Análisis del peor caso de una nueva heurística para el problema del viajante de comercio (PDF) , Informe 388, Graduate School of Industrial Administration, CMU
- ^ van Bevern, René; Slugina, Viktoriia A. (2020), "Una nota histórica sobre el algoritmo de aproximación 3/2 para el problema métrico del viajante de comercio", Historia Mathematica , arXiv : 2004.02437 , doi : 10.1016 / j.hm.2020.04.003 , S2CID 214803097
- ^ Serdyukov, Anatoliy I. (1978), "О некоторых экстремальных обходах в графах" [Sobre algunos paseos extremos en gráficos] (PDF) , Upravlyaemye Sistemy (en ruso), 17 : 76–79
- ^ Karlin, Anna R .; Klein, Nathan; Gharan, Shayan Oveis (30 de agosto de 2020). "Un algoritmo de aproximación (ligeramente) mejorado para TSP métrico". arXiv : 2007.01409 [ cs.DS ].
- ^ Klarreich, Erica. "Los informáticos rompen el récord de vendedor ambulante" . Revista Quanta . Consultado el 10 de octubre de 2020 .
- ^ Bläser, Markus (2008), "Metric TSP" , en Kao, Ming-Yang (ed.), Encyclopedia of Algorithms} , Springer-Verlag, págs. 517–519, ISBN 9780387307701.
enlaces externos
- Definición del algoritmo Christofides del NIST