Algoritmo de Christofides

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

El algoritmo de Christofides o algoritmo de Christofides-Serdyukov es un algoritmo para encontrar soluciones aproximadas al problema del viajante, en casos donde las distancias forman un espacio métrico (son simétrica y obedece a la desigualdad del triángulo). 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 (ruso: Анатолий Иванович Сердюков ); este último lo descubrió de forma independiente en 1976 (pero la publicación está fechada en 1978).

Algoritmo

Sea $G = (V, w)$ una instancia del desplazamiento problema del vendedor. Es decir, $G$ es un gráfico completo en 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 del triángulo, por cada tres vértices $u$ , $v$ y $x$ , debería darse el caso de que $w (uv) + w (vx) \geq w (ux)$ .

Entonces el algoritmo se puede describir en pseudocódigo de la siguiente manera.

Crear un árbol de lazo mínimo $T$ de $G$ .
Vamos. $O$ ser el conjunto de vértices con extraño grado en $T$ . Por el apretón de manos lema, $O$ tiene incluso un número de vértices.
Encontrar una combinación de peso mínimo $M$ en el subgrafo inducido $G$ por $O$ .
Combine los bordes de $M$ y $T$ para formar un multigrafo conectado $H$ en el cual cada vértice tiene grado.
Forma un circuito eulerio en $H$ .
Hacer el circuito encontrado en el paso anterior en un circuito Hamiltoniano saltando vértices repetidos (corto).

Los pasos 5 y 6 no necesariamente producen un solo resultado; como tal, la heurística puede dar varios caminos diferentes.

Complejidad computacional

La peor complejidad del algoritmo está dominada por el paso perfecto, que tiene $O(n^{3}$ complejidad. El periódico de Serdyukov decía $O(n^{3}\log n)$ complejidad, porque el autor sólo era consciente de un algoritmo de emparejamiento perfecto menos eficiente.

Relación de aproximación

El costo de la solución producida por el algoritmo está dentro de $3/2$ del óptimo. Para demostrarlo, supongamos que $C$ sea el recorrido óptimo del viajante de comercio. 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) \leq w (C)$ - límite inferior al costo de la solución óptima.

El algoritmo aborda el problema de que $T$ no es un recorrido identificando todos los vértices de grados impares en $T$ ; dado que la suma de grados en cualquier gráfico es par (según el lema del apretón de manos), existe un número par de dichos vértices. El algoritmo encuentra una coincidencia perfecta $M$ de peso mínimo entre las de grado impar.

A continuación, numere los vértices de $O$ en orden cíclico alrededor de $C$ y dividir $C$ en dos conjuntos de rutas: aquellas en las que la primera El 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 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 los caminos. De hecho, cada punto final del camino 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 rutas 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 del triángulo su correspondiente coincidencia tiene un peso que también es como máximo la mitad del peso de $C$ . La coincidencia perfecta de peso mínimo no puede tener un peso mayor, por lo que $w (M) \leq w (< i>C)/2$ . Sumando los pesos de $T$ y $M< /span> proporciona el peso del recorrido de Euler, como máximo 3 w (C)/2 . Gracias a la desigualdad del triángulo, aunque el recorrido de Euler podría volver a visitar los vértices, el atajo no aumenta el peso. por lo que el peso de la salida también es como máximo 3 w (C)/2 .$

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 esas clases de las entradas están formadas por una ruta de $n$ vértices, y los bordes de la ruta tienen un 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 gráfico completo tienen distancias dadas por los caminos más cortos en este subgráfico. Entonces el árbol de expansión mínimo estará dado por la ruta, de longitud $n - 1$ , y los únicos dos vértices impares serán los puntos finales de la ruta, cuyos La combinación perfecta consta de un solo borde 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 los bordes del peso $1 + ε$ junto con dos pesos- $1$ bordes 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 tanto obtenemos una relación de aproximación de 3/2.

Ejemplo

	Dado: gráfico completo cuyos pesos de borde obedecen la desigualdad triángulo
	Calcular el árbol mínimo de azotes $T$
	Calcular el conjunto de vértices $O$ con extraño grado en $T$
	Forma el subgrafo $G$ usando sólo los vértices de $O$
	Construir una combinación perfecta de peso mínimo $M$ en este subgrafo
	Unitario concordante y azotado árbol $T \cup M$ para formar un multigraph Eulerian
	Calcular el tour Euler Aquí se realiza el tour A- confíaB- títuloC- títuloA- títuloD- títuloE- títuloA. Igualmente válido es A- títuloB- confianzaC- títuloA- títuloE- títuloD- títuloA.
	Eliminar los vértices repetidos, dando la salida del algoritmo. Si se hubiera utilizado el tour alternativo, el acceso directo sería de C a E que resulta en una ruta más corta (A- títuloB- confianzaC- títuloE- títuloD- títuloA) si se trata de un gráfico euclideano como la ruta A- título B- títuloC- títuloD- títuloE- título A tiene líneas de intersección que se demuestra que no es la ruta más corta.

Nuevos desarrollos

Este algoritmo sigue siendo el mejor algoritmo de aproximación de tiempo polinomial para el problema planteado y ha sido revisado minuciosamente por la comunidad científica relevante para el problema del viajante en espacios métricos generales. En julio de 2020, Karlin, Klein y Gharan publicaron una preimpresión en la que introdujeron un nuevo algoritmo de aproximación y afirmaron que su relación de aproximación es 1,5 − 10⁻³⁶. El suyo es un algoritmo aleatorio y sigue principios similares a los de Christofides. algoritmo, pero utiliza un árbol elegido aleatoriamente de una distribución aleatoria cuidadosamente elegida en lugar del árbol de expansión mínima. El artículo se publicó en STOC'21, donde recibió el premio al mejor artículo.

En el caso especial del espacio euclidiano, para cualquier c > 0, donde d es el número de dimensiones en el espacio euclidiano, existe un algoritmo de tiempo polinomial que encuentra un recorrido de longitud como máximo (1 + 1/c) veces el óptimo para instancias geométricas de TSP en

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

tiempo;

esto se denomina esquema de aproximación en tiempo polinomial (PTAS). Sanjeev Arora y Joseph S. B. Mitchell recibieron el Premio Gödel en 2010 por su descubrimiento simultáneo de un PTAS para el TSP euclidiano.

Más resultados...