Algoritmo de Held-Karp

El algoritmo de Held-Karp , también llamado algoritmo de Bellman-Held-Karp , es un algoritmo de programación dinámica propuesto en 1962 independientemente por Bellman ^{[ 1 ]} y por Held y Karp ^{[ 2 ]} para resolver el problema del viajante (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 .

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

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

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

De forma más general, supongamos que${\displaystyle S=\{s_{1},\ldots ,s_{k}\}}$es un conjunto de${\displaystyle k}$ciudades. Para cada entero${\displaystyle 1\leq i\leq k}$, escribir${\displaystyle S_{i}=S\setminus \{s_{i}\}=\{s_{1},\ldots ,s_{i-1},s_{i+1},\ldots ,s_{k}\}}$para el conjunto creado al eliminar${\displaystyle s_{i}}$de${\displaystyle S}$Entonces, si el camino más corto desde${\displaystyle 1}$a través de${\displaystyle S}$a${\displaystyle e}$tiene${\displaystyle s_{i}}$como su penúltima ciudad, entonces quitar el borde final de este camino debe dar el camino más corto desde${\displaystyle 1}$a${\displaystyle s_{i}}$a través de${\displaystyle S_{i}}$Esto significa que solo hay${\displaystyle k}$posibles rutas más cortas desde${\displaystyle 1}$a${\displaystyle e}$a través de${\displaystyle S}$, uno por cada posible penúltima ciudad${\displaystyle s_{i}}$con longitud${\displaystyle g(S_{i},s_{i})+d(s_{i},e)}$, y${\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${\displaystyle g(\{2,\ldots ,i-1,i+1,\ldots ,n\},i)}$es conocido para cada entero${\displaystyle 2\leq i\leq n}$, dando la distancia más corta desde la ciudad${\displaystyle 1}$a la ciudad${\displaystyle i}$que pasa por todas las demás ciudades. La segunda etapa, mucho más corta, suma estas distancias a las longitudes de los bordes.${\displaystyle d(i,1)}$dar${\displaystyle n-1}$posibles ciclos más cortos, y luego encuentra el más corto.

Finalmente, el camino más corto en sí (y no solo su longitud) puede reconstruirse almacenándolo junto a${\displaystyle g(S,e)}$la etiqueta de la penúltima ciudad en el camino desde${\displaystyle 1}$a${\displaystyle e}$a través de${\displaystyle S}$, aumentando los requisitos de espacio solo en un factor constante.

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

Fuente: ^{[ 3 ]}

El algoritmo de función TSP (G, n) es para k := 2 a n hacer g({k}, k) := d(1, k) fin parapara 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) end function