Held–Karp algorithm

The Held–Karp algorithm, also called Bellman–Held–Karp algorithm, is a dynamic programming algorithm proposed in 1962 independently by Bellman[1] and by Held and Karp[2] to solve the Traveling Salesman Problem (TSP). TSP is an extension of the Hamiltonian circuit problem. The problem can be described as: find a tour of N cities in a country (assuming all cities to be visited are reachable), the tour should (a) visit every city just once, (b) return to the starting point and (c) be of minimum distance.[3] Broadly, the TSP is classified as symmetric travelling salesman problem (sTSP), asymmetric travelling salesman problem (aTSP), and multi-travelling salesman problem (mTSP).

Graph model

sTSP: Let V = {v₁ ,..., v_n } be a set of cities, E = {(r, s) | r, s ∈ V} be the edge set, and d_rs = d_sr be a cost measure associated with edge (r, s) ∈ E.

aTSP: If d_rs ≠ d_sr for at least one (r, s) then the sTSP becomes an aTSP. While sTSP can be defined using an undirected graph, aTSP is defined using a directed graph.

mTSP: In the multi-TSP problem, there are several salesmen starting from the same city; each city other than the starting one needs to be visited exactly once by exactly one salesman, and the sum of lengths of their tours needs to be minimized. One can look at mTSP as a modification of standard TSP in which it is allowed to re-visit the starting city. The mTSP is generally treated as a relaxed vehicle routing problem.

Algorithm

Description

Below is the dynamic programming procedure:

There is an optimization property for TSP:

   Every subpath of a path of minimum distance is itself of minimum distance.

Compute the solutions of all subproblems starting with the smallest. Whenever computing a solution requires solutions for smaller problems using the above recursive equations, look up these solutions which are already computed. To compute a minimum distance tour, use the final equation to generate the 1st node, and repeat for the other nodes. For this problem, we cannot know which subproblems we need to solve, so we solve them all.

Recursive formulation

Number the cities 1, 2, . . . , N and assume we start at city 1, and the distance between city i and city j is d_i,j. Consider subsets S ⊆ {2, . . . , N} of cities and, for c ∈ S, let D(S, c) be the minimum distance, starting at city 1, visiting all cities in S and finishing at city c.

First phase: if S = {c}, then D(S, c) = d_1,c. Otherwise: D(S, c) = min_x∈S−c (D(S − c, x) + d_x,c ).

Second phase: the minimum distance for a complete tour of all cities is M = min_{c∈{2,...,N}} (D({2, . . . , N}, c) + d_c,1 )

A tour n₁ , . . ., n_N is of minimum distance just when it satisfies M = D({2, . . . , N}, n_N ) + d_{n_N,1} .

Example[4]

Distance matrix:

C={\begin{pmatrix}0&2&9&10\\1&0&6&4\\15&7&0&8\\6&3&12&0\end{pmatrix}}

Functions description:

g(x, S) - starting from 1, path min cost ends at vertex x, passing vertices in set S exactly once
c_xy - edge cost ends at x from y
p(x, S) - the second-to-last vertex to x from set S. Used for constructing the TSP path back at the end.

k = 0, null set:

Set ∅:

       g(2, ∅) = c₂₁ = 1 
       g(3, ∅) = c₃₁ = 15
       g(4, ∅) = c₄₁ = 6

k = 1, consider sets of 1 element:

Set {2}:

       g(3,{2}) = c₃₂ + g(2, ∅ ) = c₃₂ + c₂₁ = 7 + 1 = 8       p(3,{2}) = 2
       g(4,{2}) = c₄₂ + g(2, ∅ ) = c₄₂ + c₂₁ = 3 + 1 = 4       p(4,{2}) = 2

Set {3}:

       g(2,{3}) = c₂₃ + g(3, ∅ ) = c₂₃ + c₃₁ = 6 + 15 = 21     p(2,{3}) = 3
       g(4,{3}) = c₄₃ + g(3, ∅ ) = c₄₃ + c₃₁ = 12 + 15 = 27    p(4,{3}) = 3

Set {4}:

       g(2,{4}) = c₂₄ + g(4, ∅ ) = c₂₄ + c₄₁ = 4 + 6 = 10      p(2,{4}) = 4
       g(3,{4}) = c₃₄ + g(4, ∅ ) = c₃₄ + c₄₁ = 8 + 6 = 14      p(3,{4}) = 4

k = 2, consider sets of 2 elements:

Set {2,3}:

         g(4,{2,3}) = min {c₄₂ + g(2,{3}), c₄₃ + g(3,{2})} = min {3+21, 12+8}= min {24, 20}= 20
         p(4,{2,3}) = 3

Set {2,4}:

         g(3,{2,4}) = min {c₃₂ + g(2,{4}), c₃₄ + g(4,{2})} = min {7+10, 8+4}= min {17, 12} = 12
         p(3,{2,4}) = 4

Set {3,4}:

          g(2,{3,4}) = min {c₂₃ + g(3,{4}), c₂₄ + g(4,{3})} = min {6+14, 4+27}= min {20, 31}= 20
          p(2,{3,4}) = 3

Length of an optimal tour:

 f = g(1,{2,3,4}) = min { c₁₂ + g(2,{3,4}), c₁₃ + g(3,{2,4}), c₁₄ + g(4,{2,3}) }
                  = min {2 + 20, 9 + 12, 10 + 20} = min {22, 21, 30} = 21

Predecessor of node 1: p(1,{2,3,4}) = 3

Predecessor of node 3: p(3, {2,4}) = 4

Predecessor of node 4: p(4, {2}) = 2

Predecessor of node 2: p(2, {}) = 1

Hence, an optimal TSP tour is given by 1 → 2 → 4 → 3 → 1.

Pseudocode[5]

function algorithm TSP (G, n) is
    for k := 2 to n do
        C({k}, k) := d_1,k
    end for

    for s := 2 to n−1 do
        for all S ⊆ {2, . . . , n}, |S| = s do
            for all k ∈ S do
                C(S, k) := min_m≠k,m∈S [C(S\{k}, m) + d_m,k]
            end for
        end for
    end for

    opt := min_k≠1 [C({2, 3, . . . , n}, k) + d_{k, 1}]
    return (opt)
end function

Complexity

Exhaustive enumeration

This brute-force method starting at any city, enumerate all possible permutations of cities to visit, and find the distance of each permutation and choose one of minimum distance. The total number of possible routes covering all $N$ cities can be given as $(N-1)!$ and ${\frac {1}{2}}(N-1)!$ in aTSP and sTSP respectively.[6]

Dynamic programming approach

This algorithm offers faster (but still exponential time) execution than exhaustive enumeration, with the disadvantage using a lot of space: the worst-case time complexity of this algorithm is $O(2^{n}n^{2})$ and the space $O(2^{n}n)$ .

Time: the fundamental operations employed in the computation are additions and comparisons. The number of each in the first phase is given by $\left(\sum _{k=2}^{n-1}k(k-1){\binom {n-1}{k}}\right)+(n-1)=(n-1)(n-2)2^{n-3}+(n-1)$

and the number of occurrence of each in the second phase is $\sum _{k=2}^{n-1}k={n(n-1) \over 2}-1$

Space: $\left(\sum _{k=2}^{n-1}k{\binom {n-1}{k}}\right)+(n-1)=(n-1)2^{n-2}$

The space complexity can be slightly improved by noticing that the calculation of minimum costs for subsets of size s only requires subsets of size s-1.

By storing only subsets of size s-1 and s at any point of the algorithm, the space complexity reduces to: $\max _{2\leq s<n}\left((s-1){\binom {n-1}{s-1}}+s{\binom {n-1}{s}}\right)+(n-1)=O\left(n{\binom {n-1}{\lfloor n/2\rfloor }}\right)=O(2^{n}{\sqrt {n}})$

Related algorithms

Precise algorithm for solving the TSP

Besides Dynamic Programming, Linear programming and Branch-bound algorithm are precise algorithms that can solve TSP. Linear programming applies to the cutting plane method in the integer programming, i.e. solving the LP formed by two constraints in the model and then seeking the cutting plane by adding inequality constraint to gradually converge at an optimal solution. When people apply this method to find a cutting plane, they often depend on experience. So this method is seldom deemed as a general method.

Branch-bound algorithm is a search algorithm widely used, although it's not good for solving the large-scale problem. It controls the searching process through effective restrictive boundary so that it can search for the optimal solution branch from the space state tree to find an optimal solution as soon as possible. The key point of this algorithm is the choice of the restrictive boundary. Different restrictive boundaries may form different branch-bound algorithms.

Approximate algorithm for solving the TSP

As the application of precise algorithm to solve problem is very limited, we often use approximate algorithm or heuristic algorithm. The result of the algorithm can be assessed by C / C* ≤ ε . C is the total travelling distance generated from approximate algorithm; C* is the optimal travelling distance; ε is the upper limit for the ratio of the total travelling distance of approximate solution to optimal solution under the worst condition. The value of ε >1.0. The more it closes to 1.0, the better the algorithm is. These algorithms include: Interpolation algorithm, Nearest neighbour algorithm, Clark & Wright algorithm, Double spanning tree algorithm, Christofides algorithm, Hybrid algorithm, Probabilistic algorithm.

References

‘Dynamic programming treatment of the travelling salesman problem’, Richard Bellman, Journal of Assoc. Computing Mach. 9. 1962.
'A dynamic programming approach to sequencing problems’, Michael Held and Richard M. Karp, Journal for the Society for Industrial and Applied Mathematics 1:10. 1962
http://www.cs.man.ac.uk/~david/algorithms/graphs.pdf
http://www.mafy.lut.fi/study/DiscreteOpt/tspdp.pdf
http://www.lsi.upc.edu/~mjserna/docencia/algofib/P07/dynprog.pdf%5B%5D
Gutin, Gregory, and Abraham P. Punnen, eds. The traveling salesman problem and its variations. Vol. 12. Springer, 2002.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] ‘Dynamic programming treatment of the travelling salesman problem’, Richard Bellman, Journal of Assoc. Computing Mach. 9. 1962.

[2] 'A dynamic programming approach to sequencing problems’, Michael Held and Richard M. Karp, Journal for the Society for Industrial and Applied Mathematics 1:10. 1962

[3] ttp://www.cs.man.ac.uk/~david/algorithms/graphs.pdf

[4] ttp://www.mafy.lut.fi/study/DiscreteOpt/tspdp.pdf

[5] ttp://www.lsi.upc.edu/~mjserna/docencia/algofib/P07/dynprog.pdf%5B%5D

[6] Gutin, Gregory, and Abraham P. Punnen, eds. The traveling salesman problem and its variations. Vol. 12. Springer, 2002.