Held–Karp algorithm

EN Texto en inglés Aún no hay artículo en tu idioma: extracto en inglés.

The Held–Karp algorithm, also called the Bellman–Held–Karp algorithm, is a dynamic programming algorithm proposed in 1962 independently by Bellman and by Held and Karp to solve the traveling salesman problem (TSP), in which the input is a distance matrix between a set of cities, and the goal is to find a minimum-length tour that visits each city exactly once before returning to the starting point. It finds the exact solution to this problem, and to several related problems including the Hamiltonian cycle problem, in exponential time. Number the cities 1 , 2 , … , n {\displaystyle 1,2,\ldots ,n} , with 1 {\displaystyle 1} designated arbitrarily as a "starting" city (since the solution to TSP is a Hamiltonian cycle, the choice of starting city doesn't matter). The Held–Karp algorithm begins by calculating, for each set of cities S ⊆ { 2 , … , n } {\displaystyle S\subseteq \{2,\ldots ,n\}} and every city e ≠ 1 {\displaystyle e\neq 1} not contained in S {\displaystyle S} , the shortest one-way path from 1 {\displaystyle 1} to e {\displaystyle e} that passes through every city in S {\displaystyle S} in some order (but not through any other cities). Denote this distance g ( S , e ) {\displaystyle g(S,e)} , and write d ( u , v ) {\displaystyle d(u,v)} for the length of the direct edge from u {\displaystyle u} to v {\displaystyle v} . We'll compute values of g ( S , e ) {\displaystyle g(S,e)} starting with the smallest sets S {\displaystyle S} and finishing with the largest. When S {\displaystyle S} has two or fewer elements, then calculating g ( S , e ) {\displaystyle g(S,e)} requires looking at one or two possible shortest paths. For example, g ( ∅ , e ) {\displaystyle g(\emptyset ,e)} is simply d ( 1 , e ) {\displaystyle d(1,e)} , and g ( { 2 } , 3 ) {\displaystyle g(\{2\},3)} is just the length of 1 → 2 → 3 {\displaystyle 1\rightarrow 2\rightarrow 3} . Likewise, g ( { 2 , 3 } , 4 ) {\displaystyle g(\{2,3\},4)} is the length of either 1 → 2 → 3 → 4 {\displaystyle 1\rightarrow 2\rightarrow 3\rightarrow 4} or 1 → 3 → 2 → 4 {\displaystyle 1\rightarrow 3\rightarrow 2\rightarrow 4} , whichever is shorter. Once S {\displaystyle S} contains three or more cities, the number of paths through S {\displaystyle S} rises quickly, but only a few such paths need to be examined to find the shortest.