Algoritmo de Held-Karp

Solución del problema del viajante de comercio

El algoritmo de Held-Karp , también llamado algoritmo Bellman-Held-Karp , es un algoritmo de programación dinámica propuesto en 1962 de forma independiente por Bellman ^[1] y por Held y Karp ^[2] para resolver el problema del viajante de comercio (TSP), en el que la entrada es una matriz de distancias entre un conjunto de ciudades, y el objetivo es encontrar un recorrido de longitud mínima que visite cada ciudad exactamente una vez antes de regresar al punto de partida. Encuentra la solución exacta a este problema, y ​​a varios problemas relacionados, incluido el problema del ciclo hamiltoniano , en tiempo exponencial .

Descripción y motivación del algoritmo

Numere las ciudades , con designada arbitrariamente como ciudad "de partida" (ya que la solución de TSP es un ciclo hamiltoniano, la elección de la ciudad de partida no importa). El algoritmo de Held-Karp comienza calculando, para cada conjunto de ciudades y cada ciudad no contenida en , el camino unidireccional más corto desde hasta que pase por cada ciudad en en algún orden (pero no por ninguna otra ciudad). Denote esta distancia , y escriba para la longitud del borde directo desde hasta . Calcularemos valores de comenzando con los conjuntos más pequeños y terminando con el más grande. ${\displaystyle 1,2,\ldots ,n}$ ${\displaystyle 1}$ ${\displaystyle S\subseteq \{2,\ldots ,n\}}$ ${\displaystyle e\neq 1}$ ${\displaystyle S}$ ${\displaystyle 1}$ ${\displaystyle e}$ ${\displaystyle S}$ ${\displaystyle g(S,e)}$ ${\displaystyle d(u,v)}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle g(S,e)}$ ${\displaystyle S}$

Cuando tiene dos o menos elementos, entonces el cálculo requiere considerar uno o dos caminos más cortos posibles. Por ejemplo, es simplemente y es solo la longitud de . Del mismo modo, es la longitud de o , lo que sea más corto. ${\displaystyle S}$ ${\displaystyle g(S,e)}$ ${\displaystyle g(\emptyset ,e)}$ ${\displaystyle d(1,e)}$ ${\displaystyle g(\{2\},3)}$ ${\displaystyle 1\rightarrow 2\rightarrow 3}$ ${\displaystyle g(\{2,3\},4)}$ ${\displaystyle 1\rightarrow 2\rightarrow 3\rightarrow 4}$ ${\displaystyle 1\rightarrow 3\rightarrow 2\rightarrow 4}$

Una vez que contiene tres o más ciudades, el número de caminos a través de aumenta rápidamente, pero solo se necesitan examinar unos pocos de esos caminos para encontrar el más corto. Por ejemplo, si es más corto que , entonces debe ser más corto que , y la longitud de no es un valor posible de . De manera similar, si el camino más corto desde a través de hasta es , y el camino más corto desde a través de hasta termina en el borde , entonces todo el camino desde a debe ser , y no ninguno de los otros cinco caminos creados al visitar en un orden diferente. ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle 1\rightarrow 2\rightarrow 3\rightarrow 4}$ ${\displaystyle 1\rightarrow 3\rightarrow 2\rightarrow 4}$ ${\displaystyle 1\rightarrow 2\rightarrow 3\rightarrow 4\rightarrow 5}$ ${\displaystyle 1\rightarrow 3\rightarrow 2\rightarrow 4\rightarrow 5}$ ${\displaystyle 1\rightarrow 3\rightarrow 2\rightarrow 4\rightarrow 5}$ ${\displaystyle g(\{2,3,4\},5)}$ ${\displaystyle 1}$ ${\displaystyle \{2,3,4\}}$ ${\displaystyle 5}$ ${\displaystyle 1\rightarrow 4\rightarrow 3\rightarrow 2\rightarrow 5}$ ${\displaystyle 1}$ ${\displaystyle \{2,3,4,5\}}$ ${\displaystyle 6}$ ${\displaystyle 5\rightarrow 6}$ ${\displaystyle 1}$ ${\displaystyle 6}$ ${\displaystyle 1\rightarrow 4\rightarrow 3\rightarrow 2\rightarrow 5\rightarrow 6}$ ${\displaystyle \{2,3,4\}}$

En términos más generales, supongamos que es un conjunto de ciudades. Para cada entero , escriba para el conjunto creado al eliminar de . Entonces, si el camino más corto desde hasta tiene como su segunda ciudad a la última, entonces eliminar la arista final de este camino debe dar el camino más corto desde hasta hasta hasta . Esto significa que solo hay caminos más cortos posibles desde hasta hasta , uno para cada posible segunda ciudad a la última con longitud , y . ${\displaystyle S=\{s_{1},\ldots ,s_{k}\}}$ ${\displaystyle k}$ ${\displaystyle 1\leq i\leq k}$ ${\displaystyle S_{i}=S\setminus \{s_{i}\}=\{s_{1},\ldots ,s_{i-1},s_{i+1},\ldots ,s_{k}\}}$ ${\displaystyle s_{i}}$ ${\displaystyle S}$ ${\displaystyle 1}$ ${\displaystyle S}$ ${\displaystyle e}$ ${\displaystyle s_{i}}$ ${\displaystyle 1}$ ${\displaystyle s_{i}}$ ${\displaystyle S_{i}}$ ${\displaystyle k}$ ${\displaystyle 1}$ ${\displaystyle e}$ ${\displaystyle S}$ ${\displaystyle s_{i}}$ ${\displaystyle g(S_{i},s_{i})+d(s_{i},e)}$ ${\displaystyle g(S,e)=\min _{1\leq i\leq k}g(S_{i},s_{i})+d(s_{i},e)}$

Esta etapa del algoritmo finaliza cuando se conoce para cada entero , lo que da la distancia más corta de ciudad a ciudad que pasa por cada una de las demás ciudades. La segunda etapa, mucho más corta, suma estas distancias a las longitudes de los bordes para dar los ciclos más cortos posibles y luego encuentra el más corto. ${\displaystyle g(\{2,\ldots ,i-1,i+1,\ldots ,n\},i)}$ ${\displaystyle 2\leq i\leq n}$ ${\displaystyle 1}$ ${\displaystyle i}$ ${\displaystyle d(i,1)}$ ${\displaystyle n-1}$

El camino más corto en sí (y no solo su longitud), finalmente, puede reconstruirse almacenándolo junto con la etiqueta de la segunda ciudad antes de la última en el camino desde a hasta pasando por , lo que aumenta los requisitos de espacio solo en un factor constante. ${\displaystyle g(S,e)}$ ${\displaystyle 1}$ ${\displaystyle e}$ ${\displaystyle S}$

Complejidad algorítmica

El algoritmo Held-Karp tiene una complejidad temporal exponencial , significativamente mejor que el rendimiento superexponencial de un algoritmo de fuerza bruta. Sin embargo, Held-Karp requiere espacio para almacenar todos los valores calculados de la función , mientras que la fuerza bruta solo necesita espacio para almacenar el gráfico en sí. ${\displaystyle \Theta (2^{n}n^{2})}$ ${\displaystyle \Theta (n!)}$ ${\displaystyle \Theta (n2^{n})}$ ${\displaystyle g(S,e)}$ ${\displaystyle \Theta (n^{2})}$

Tiempo

Calcular un valor de para un subconjunto de elementos de requiere encontrar la ruta más corta posible, cada una de las cuales se obtiene sumando un valor conocido de y una longitud de arista del gráfico original; es decir, requiere un tiempo proporcional a . Hay subconjuntos de elementos de ; y cada subconjunto da valores posibles de . Calcular todos los valores de donde requiere, por lo tanto, tiempo , para un tiempo total en todos los tamaños de subconjunto . La segunda etapa del algoritmo, encontrar un ciclo completo a partir de candidatos, lleva tiempo y no afecta el rendimiento asintótico. ${\displaystyle g(S,e)}$ ${\displaystyle k}$ ${\displaystyle S}$ ${\displaystyle \{2,\ldots ,n\}}$ ${\displaystyle k}$ ${\displaystyle g}$ ${\displaystyle k}$ ${\textstyle {\binom {n-1}{k}}}$ ${\displaystyle k}$ ${\displaystyle \{2,\ldots ,n\}}$ ${\displaystyle n-k-1}$ ${\displaystyle e}$ ${\displaystyle g(S,e)}$ ${\displaystyle |S|=k}$ ${\textstyle k(n-k-1){\binom {n-1}{k}}=(n-1)(n-2){\binom {n-3}{k-1}}}$ ${\textstyle (n-1)(n-2)\sum _{k=1}^{n-2}{\binom {n-3}{k-1}}=(n-1)(n-2)2^{n-3}=\Theta (n^{2}2^{n})}$ ${\displaystyle n-1}$ ${\displaystyle \Theta (n)}$

Para los gráficos no dirigidos , el algoritmo se puede detener antes de tiempo después del paso y encontrar el mínimo para cada , donde es el conjunto complementario de . Esto es análogo a una búsqueda bidireccional que comienza en y se encuentra en el punto medio . Sin embargo, esta es una mejora de factor constante y no afecta el rendimiento asintótico. ${\textstyle k=\lfloor {\frac {n-1}{2}}\rfloor }$ ${\textstyle g(S,e)+g(S^{c}\setminus \{1,e\},e)}$ ${\textstyle \{(S,e):|S|=\lfloor {\frac {n-1}{2}}\rfloor ,e\in S^{c}\setminus \{1\}\}}$ ${\textstyle S^{c}}$ ${\textstyle S}$ ${\textstyle 1}$ ${\textstyle e}$

Espacio

Para almacenar todos los valores de para los subconjuntos de tamaño es necesario conservar los valores. Por lo tanto, una tabla completa de valores de requiere espacio . Esto supone que es lo suficientemente pequeño como para que pueda almacenarse como una máscara de bits de múltiplo constante de palabras de máquina , en lugar de una k-tupla explícita. ${\displaystyle g(S,e)}$ ${\displaystyle k}$ ${\textstyle (n-k-1){\binom {n-1}{k}}=(n-1){\binom {n-2}{k}}}$ ${\displaystyle g(S,e)}$ ${\textstyle \sum _{k=0}^{n-2}(n-1){\binom {n-2}{k}}=(n-1)2^{n}=\Theta (n2^{n})}$ ${\textstyle n}$ ${\textstyle S}$

Si solo se necesita la longitud del ciclo más corto, no el ciclo en sí, entonces la complejidad espacial se puede mejorar un poco teniendo en cuenta que el cálculo para un tamaño requiere solo valores de para subconjuntos de tamaño . Mantener solo los valores de donde tiene tamaño o reduce los requisitos de espacio máximo del algoritmo, alcanzados cuando , a . ${\displaystyle g(S,e)}$ ${\displaystyle S}$ ${\displaystyle k}$ ${\displaystyle g}$ ${\displaystyle k-1}$ ${\textstyle (n-1)\left[{\binom {n-2}{k-1}}+{\binom {n-2}{k}}\right]}$ ${\displaystyle g(S,e)}$ ${\displaystyle S}$ ${\displaystyle k-1}$ ${\displaystyle k}$ ${\textstyle k=\left\lfloor {\frac {n}{2}}\right\rfloor }$ ${\displaystyle \Theta ({\sqrt {n}}2^{n})}$

Pseudocódigo

Fuente: ^[3]

El algoritmo de función TSP (G, n) es  para k := 2 a n g({k}, k) := d(1, k) fin para para s := 2 a n−1 hacer  para todo S ⊆ {2, ..., n}, |S| = s hacer  para todo k ∈ S hacer g(S, k) := min m≠k,m∈S [g(S\{k}, m) + d(m, k)] fin para  fin para  fin para opt := min k≠1 [g({2, 3, ..., n}, k) + d(k, 1)] return (opt) fin de la función

Algoritmos relacionados

Algoritmos exactos para resolver el TSP

Además de la programación dinámica, la programación lineal y la ramificación y acotación son patrones de diseño que también se utilizan para soluciones exactas al TSP. La programación lineal aplica el método del plano de corte en la programación entera , es decir, resuelve el PL formado por dos restricciones en el modelo y luego busca el plano de corte agregando restricciones de desigualdad para converger gradualmente en una solución óptima. Cuando las personas aplican este método para encontrar un plano de corte, a menudo dependen de la experiencia, por lo que este método rara vez se usa como método general.

El término "ramificación y acotación" se utilizó por primera vez en 1963 en un artículo publicado por Little et al. sobre el TSP, en el que se describía una técnica para combinar espacios de búsqueda más pequeños y establecer acotamientos inferiores para ampliar el rango práctico de aplicación de una solución exacta. La técnica es útil para ampliar el número de ciudades que se pueden considerar computacionalmente, pero sigue fallando en conjuntos de datos a gran escala.

Controla el proceso de búsqueda mediante la aplicación de límites restrictivos, lo que permite buscar la rama de solución óptima a partir del árbol de estados espaciales para encontrar una solución óptima lo más rápido posible. El componente fundamental de este algoritmo es la selección del límite restrictivo. Diferentes límites restrictivos pueden formar diferentes algoritmos de rama límite.

Algoritmos aproximados para resolver el TSP

Como la aplicación de algoritmos precisos para resolver problemas es muy limitada, a menudo utilizamos algoritmos aproximados o algoritmos heurísticos. El resultado del algoritmo se puede evaluar por C / C* ≤ ε . C es la distancia total de viaje generada a partir del algoritmo aproximado; C* es la distancia óptima de viaje; ε es el límite superior para la relación de la distancia total de viaje de la solución aproximada a la solución óptima en la peor condición. El valor de ε >1.0. Cuanto más se acerque a 1.0, mejor será el algoritmo. Estos algoritmos incluyen: algoritmo de interpolación, algoritmo del vecino más cercano , algoritmo de Clark y Wright, algoritmo de árbol de expansión doble, algoritmo de Christofides , algoritmo híbrido, algoritmo probabilístico (como recocido simulado ).

Referencias

1. 'Tratamiento de programación dinámica del problema del viajante', Richard Bellman, Journal of Assoc. Computing Mach. 9. 1962.
2. 'Un enfoque de programación dinámica para problemas de secuenciación', Michael Held y Richard M. Karp, Journal for the Society for Industrial and Applied Mathematics 1:10. 1962
3. "Programación dinámica" (PDF) . Enero de 2020. Archivado desde el original (PDF) el 8 de febrero de 2015.