Algoritmo Held-Karp

---

El algoritmo 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 el La entrada es una matriz de distancia entre un conjunto de ciudades, y el objetivo es encontrar un recorrido de duración 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 .

Numere las ciudades , con designadas arbitrariamente como una ciudad "inicial" (dado que la solución para TSP es un ciclo, la elección de la ciudad inicial no importa). El algoritmo de Held-Karp comienza calculando, para cada conjunto de ciudades y cada ciudad no contenida en , el camino de ida más corto desde a que pasa por cada ciudad en algún orden (pero no a través de otras ciudades). Denote esta distancia y escriba la longitud del borde directo de a . Calcularemos los valores de comenzar con los conjuntos más pequeños y terminar con los más grandes.${\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, el cálculo requiere mirar uno o dos posibles caminos más cortos. Por ejemplo, es simplemente y tiene 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}$

---