fbpx
Wikipedia

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), 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.

Algorithm description and motivation

Number the cities  , with   designated arbitrarily as a "starting" city (since the solution to TSP is a cycle, the choice of starting city doesn't matter). The Held–Karp algorithm begins by calculating, for each set of cities   and every city   not contained in  , the shortest one-way path from   to   that passes through every city in   in some order (but not through any other cities). Denote this distance  , and write   for the length of the direct edge from   to  . We'll compute values of   starting with the smallest sets   and finishing with the largest.

When   has two or fewer elements, then calculating   requires looking at one or two possible shortest paths. For example,   is simply  , and   is just the length of  . Likewise,   is the length of either   or  , whichever is shorter.

Once   contains three or more cities, the number of paths through   rises quickly, but only a few such paths need to be examined to find the shortest. For instance, if   is shorter than  , then   must be shorter than  , and the length of   is not a possible value of  . Similarly, if the shortest path from   through   to   is  , and the shortest path from   through   to   ends with the edge  , then the whole path from   to   must be  , and not any of the other five paths created by visiting   in a different order.

More generally, suppose   is a set of   cities. For every integer  , write   for the set created by removing   from  . Then if the shortest path from   through   to   has   as its second-to-last city, then removing the final edge from this path must give the shortest path from   to   through  . This means there are only   possible shortest paths from   to   through  , one for each possible second-to-last city   with length  , and  .

This stage of the algorithm finishes when   is known for every integer  , giving the shortest distance from city   to city   that passes through every other city. The much shorter second stage adds these distances to the edge lengths   to give   possible shortest cycles, and then finds the shortest.

The shortest path itself (and not just its length), finally, may be reconstructed by storing alongside   the label of the second-to-last city on the path from   to   through  , raising space requirements by only a constant factor.

Algorithmic complexity

The Held–Karp algorithm has exponential time complexity  , significantly better than the superexponential performance   of a brute-force algorithm. Held–Karp, however, requires   space to hold all computed values of the function  , while brute force needs only   space to store the graph itself.

Time

Computing one value of   for a  -element subset   of   requires finding the shortest of   possible paths, each found by adding a known value of   and an edge length from the original graph; that is, it requires time proportional to  . There are    -element subsets of  ; and each subset gives   possible values of  . Computing all values of   where   thus requires time  , for a total time across all subset sizes  . The second stage of the algorithm, finding a complete cycle from   candidates, takes   time and does not affect asymptotic performance.

For undirected graphs, the algorithm can be stopped early after the   step, and finding the minimum   for every  , where   is the complement set of  . This is analogous to a bidirectional search starting at   and meeting at midpoint  . However, this is a constant factor improvement and does not affect asymptotic performance.

Space

Storing all values of   for subsets of size   requires keeping   values. A complete table of values of   thus requires space  . This assumes that   is sufficiently small enough such that   can be stored as a bitmask of constant multiple of machine words, rather than an explicit k-tuple.

If only the length of the shortest cycle is needed, not the cycle itself, then space complexity can be improved somewhat by noting that calculating   for a   of size   requires only values of   for subsets of size  . Keeping only the   values of   where   has size either   or   reduces the algorithm's maximum space requirements, attained when  , to  .

Example[3]

Distance matrix:

 

Functions description:

  • g(x, S) - starting from 1, path min cost ends at vertex x, passing vertices in set S exactly once
  • cxy - 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, ∅) = c21 = 1 g(3, ∅) = c31 = 15 g(4, ∅) = c41 = 6 

k = 1, consider sets of 1 element:

Set {2}:

 g(3,{2}) = c32 + g(2, ∅ ) = c32 + c21 = 7 + 1 = 8 p(3,{2}) = 2 g(4,{2}) = c42 + g(2, ∅ ) = c42 + c21 = 3 + 1 = 4 p(4,{2}) = 2 

Set {3}:

 g(2,{3}) = c23 + g(3, ∅ ) = c23 + c31 = 6 + 15 = 21 p(2,{3}) = 3 g(4,{3}) = c43 + g(3, ∅ ) = c43 + c31 = 12 + 15 = 27 p(4,{3}) = 3 

Set {4}:

 g(2,{4}) = c24 + g(4, ∅ ) = c24 + c41 = 4 + 6 = 10 p(2,{4}) = 4 g(3,{4}) = c34 + g(4, ∅ ) = c34 + c41 = 8 + 6 = 14 p(3,{4}) = 4 

k = 2, consider sets of 2 elements:

Set {2,3}:

 g(4,{2,3}) = min {c42 + g(2,{3}), c43 + 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 {c32 + g(2,{4}), c34 + 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 {c23 + g(3,{4}), c24 + 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 { c12 + g(2,{3,4}), c13 + g(3,{2,4}), c14 + 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[4]

function algorithm TSP (G, n) is for k := 2 to n do g({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 g(S, k) := minm≠k,m∈S [g(S\{k}, m) + d(m, k)] end for end for end for opt := mink≠1 [g({2, 3, ..., n}, k) + d(k, 1)] return (opt) end function 

Related algorithms

Exact algorithms for solving the TSP

Besides Dynamic Programming, Linear programming and Branch and bound are design patterns also used for exact solutions to the TSP. Linear programming applies the cutting plane method in integer programming, i.e. solving the LP formed by two constraints in the model and then seeking the cutting plane by adding inequality constraints 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 used as a general method.

The term branch and bound was first used in 1963 in a paper published by Little et al. on the TSP, describing a technique of combining smaller search spaces and establishing lower bounds to enlarge the practical range of application for an exact solution. The technique is useful for expanding the number of cities able to be considered computationally, but still breaks down in large-scale data sets.

It controls the searching process through applying restrictive boundaries, allowing a search for the optimal solution branch from the space state tree to find an optimal solution as quickly as possible. The pivotal component of this algorithm is the selection of the restrictive boundary. Different restrictive boundaries may form different branch-bound algorithms.

Approximate algorithms 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 (such as Simulated annealing).

References

  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. ^ http://www.mafy.lut.fi/study/DiscreteOpt/tspdp.pdf[bare URL PDF]
  4. ^ http://www.lsi.upc.edu/~mjserna/docencia/algofib/P07/dynprog.pdf[permanent dead link]

held, karp, algorithm, also, called, bellman, dynamic, programming, algorithm, proposed, 1962, independently, bellman, held, karp, solve, traveling, salesman, problem, which, input, distance, matrix, between, cities, goal, find, minimum, length, tour, that, vi. 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 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 Contents 1 Algorithm description and motivation 2 Algorithmic complexity 2 1 Time 2 2 Space 3 Example 3 4 Pseudocode 4 5 Related algorithms 5 1 Exact algorithms for solving the TSP 5 2 Approximate algorithms for solving the TSP 6 ReferencesAlgorithm description and motivation EditNumber 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 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 For instance if 1 2 3 4 displaystyle 1 rightarrow 2 rightarrow 3 rightarrow 4 is shorter than 1 3 2 4 displaystyle 1 rightarrow 3 rightarrow 2 rightarrow 4 then 1 2 3 4 5 displaystyle 1 rightarrow 2 rightarrow 3 rightarrow 4 rightarrow 5 must be shorter than 1 3 2 4 5 displaystyle 1 rightarrow 3 rightarrow 2 rightarrow 4 rightarrow 5 and the length of 1 3 2 4 5 displaystyle 1 rightarrow 3 rightarrow 2 rightarrow 4 rightarrow 5 is not a possible value of g 2 3 4 5 displaystyle g 2 3 4 5 Similarly if the shortest path from 1 displaystyle 1 through 2 3 4 displaystyle 2 3 4 to 5 displaystyle 5 is 1 4 3 2 5 displaystyle 1 rightarrow 4 rightarrow 3 rightarrow 2 rightarrow 5 and the shortest path from 1 displaystyle 1 through 2 3 4 5 displaystyle 2 3 4 5 to 6 displaystyle 6 ends with the edge 5 6 displaystyle 5 rightarrow 6 then the whole path from 1 displaystyle 1 to 6 displaystyle 6 must be 1 4 3 2 5 6 displaystyle 1 rightarrow 4 rightarrow 3 rightarrow 2 rightarrow 5 rightarrow 6 and not any of the other five paths created by visiting 2 3 4 displaystyle 2 3 4 in a different order More generally suppose S s 1 s k displaystyle S s 1 ldots s k is a set of k displaystyle k cities For every integer 1 i k displaystyle 1 leq i leq k write S i S s i s 1 s i 1 s i 1 s k displaystyle S i S setminus s i s 1 ldots s i 1 s i 1 ldots s k for the set created by removing s i displaystyle s i from S displaystyle S Then if the shortest path from 1 displaystyle 1 through S displaystyle S to e displaystyle e has s i displaystyle s i as its second to last city then removing the final edge from this path must give the shortest path from 1 displaystyle 1 to s i displaystyle s i through S i displaystyle S i This means there are only k displaystyle k possible shortest paths from 1 displaystyle 1 to e displaystyle e through S displaystyle S one for each possible second to last city s i displaystyle s i with length g S i s i d s i e displaystyle g S i s i d s i e and g S e min 1 i k 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 This stage of the algorithm finishes when g 2 i 1 i 1 n i displaystyle g 2 ldots i 1 i 1 ldots n i is known for every integer 2 i n displaystyle 2 leq i leq n giving the shortest distance from city 1 displaystyle 1 to city i displaystyle i that passes through every other city The much shorter second stage adds these distances to the edge lengths d i 1 displaystyle d i 1 to give n 1 displaystyle n 1 possible shortest cycles and then finds the shortest The shortest path itself and not just its length finally may be reconstructed by storing alongside g S e displaystyle g S e the label of the second to last city on the path from 1 displaystyle 1 to e displaystyle e through S displaystyle S raising space requirements by only a constant factor Algorithmic complexity EditThe Held Karp algorithm has exponential time complexity 8 2 n n 2 displaystyle Theta 2 n n 2 significantly better than the superexponential performance 8 n displaystyle Theta n of a brute force algorithm Held Karp however requires 8 n 2 n displaystyle Theta n2 n space to hold all computed values of the function g S e displaystyle g S e while brute force needs only 8 n 2 displaystyle Theta n 2 space to store the graph itself Time Edit Computing one value of g S e displaystyle g S e for a k displaystyle k element subset S displaystyle S of 2 n displaystyle 2 ldots n requires finding the shortest of k displaystyle k possible paths each found by adding a known value of g displaystyle g and an edge length from the original graph that is it requires time proportional to k displaystyle k There are n 1 k textstyle binom n 1 k k displaystyle k element subsets of 2 n displaystyle 2 ldots n and each subset gives n k 1 displaystyle n k 1 possible values of e displaystyle e Computing all values of g S e displaystyle g S e where S k displaystyle S k thus requires time k n k 1 n 1 k n 1 n 2 n 3 k 1 textstyle k n k 1 binom n 1 k n 1 n 2 binom n 3 k 1 for a total time across all subset sizes n 1 n 2 k 1 n 2 n 3 k 1 n 1 n 2 2 n 3 8 n 2 2 n 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 The second stage of the algorithm finding a complete cycle from n 1 displaystyle n 1 candidates takes 8 n displaystyle Theta n time and does not affect asymptotic performance For undirected graphs the algorithm can be stopped early after the k n 1 2 textstyle k lfloor frac n 1 2 rfloor step and finding the minimum g S e g S c 1 e e textstyle g S e g S c setminus 1 e e for every S e S n 1 2 e S c 1 textstyle S e S lfloor frac n 1 2 rfloor e in S c setminus 1 where S c textstyle S c is the complement set of S textstyle S This is analogous to a bidirectional search starting at 1 textstyle 1 and meeting at midpoint e textstyle e However this is a constant factor improvement and does not affect asymptotic performance Space Edit Storing all values of g S e displaystyle g S e for subsets of size k displaystyle k requires keeping n k 1 n 1 k n 1 n 2 k textstyle n k 1 binom n 1 k n 1 binom n 2 k values A complete table of values of g S e displaystyle g S e thus requires space k 0 n 2 n 1 n 2 k n 1 2 n 8 n 2 n textstyle sum k 0 n 2 n 1 binom n 2 k n 1 2 n Theta n2 n This assumes that n textstyle n is sufficiently small enough such that S textstyle S can be stored as a bitmask of constant multiple of machine words rather than an explicit k tuple If only the length of the shortest cycle is needed not the cycle itself then space complexity can be improved somewhat by noting that calculating g S e displaystyle g S e for a S displaystyle S of size k displaystyle k requires only values of g displaystyle g for subsets of size k 1 displaystyle k 1 Keeping only the n 1 n 2 k 1 n 2 k textstyle n 1 left binom n 2 k 1 binom n 2 k right values of g S e displaystyle g S e where S displaystyle S has size either k 1 displaystyle k 1 or k displaystyle k reduces the algorithm s maximum space requirements attained when k n 2 textstyle k left lfloor frac n 2 right rfloor to 8 n 2 n displaystyle Theta sqrt n 2 n Example 3 EditDistance matrix C 0 2 9 10 1 0 6 4 15 7 0 8 6 3 12 0 displaystyle C begin pmatrix 0 amp 2 amp 9 amp 10 1 amp 0 amp 6 amp 4 15 amp 7 amp 0 amp 8 6 amp 3 amp 12 amp 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 cxy 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 c21 1 g 3 c31 15 g 4 c41 6 k 1 consider sets of 1 element Set 2 g 3 2 c32 g 2 c32 c21 7 1 8 p 3 2 2 g 4 2 c42 g 2 c42 c21 3 1 4 p 4 2 2 Set 3 g 2 3 c23 g 3 c23 c31 6 15 21 p 2 3 3 g 4 3 c43 g 3 c43 c31 12 15 27 p 4 3 3 Set 4 g 2 4 c24 g 4 c24 c41 4 6 10 p 2 4 4 g 3 4 c34 g 4 c34 c41 8 6 14 p 3 4 4 k 2 consider sets of 2 elements Set 2 3 g 4 2 3 min c42 g 2 3 c43 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 c32 g 2 4 c34 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 c23 g 3 4 c24 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 c12 g 2 3 4 c13 g 3 2 4 c14 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 3Predecessor of node 3 p 3 2 4 4Predecessor of node 4 p 4 2 2Predecessor of node 2 p 2 1Hence an optimal TSP tour is given by 1 2 4 3 1 Pseudocode 4 Editfunction algorithm TSP G n is for k 2 to n do g 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 g S k minm k m S g S k m d m k end for end for end for opt mink 1 g 2 3 n k d k 1 return opt end functionRelated algorithms EditExact algorithms for solving the TSP Edit Besides Dynamic Programming Linear programming and Branch and bound are design patterns also used for exact solutions to the TSP Linear programming applies the cutting plane method in integer programming i e solving the LP formed by two constraints in the model and then seeking the cutting plane by adding inequality constraints 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 used as a general method The term branch and bound was first used in 1963 in a paper published by Little et al on the TSP describing a technique of combining smaller search spaces and establishing lower bounds to enlarge the practical range of application for an exact solution The technique is useful for expanding the number of cities able to be considered computationally but still breaks down in large scale data sets It controls the searching process through applying restrictive boundaries allowing a search for the optimal solution branch from the space state tree to find an optimal solution as quickly as possible The pivotal component of this algorithm is the selection of the restrictive boundary Different restrictive boundaries may form different branch bound algorithms Approximate algorithms for solving the TSP Edit 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 e C is the total travelling distance generated from approximate algorithm C is the optimal travelling distance e 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 e gt 1 0 The more it closes to 1 0 the better the algorithm is These algorithms include Interpolation algorithm Nearest neighbour algorithm Clark amp Wright algorithm Double spanning tree algorithm Christofides algorithm Hybrid algorithm Probabilistic algorithm such as Simulated annealing References Edit 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 mafy lut fi study DiscreteOpt tspdp pdf bare URL PDF http www lsi upc edu mjserna docencia algofib P07 dynprog pdf permanent dead link Retrieved from https en wikipedia org w index php title Held Karp algorithm amp oldid 1125702259, wikipedia, wiki, book, books, library,

article

, read, download, free, free download, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, picture, music, song, movie, book, game, games.