C++ Reference: hamiltonian_path

Note: This documentation is automatically generated.

Solves the Shortest Hamiltonian Path Problem using a complete algorithm. The algorithm was first described in M. Held, R.M. Karp, A dynamic programming approach to sequencing problems, J. SIAM 10 (1962) 196-210

The Shortest Hamiltonian Path Problem (SHPP) is similar to the Traveling Salesperson Problem (TSP). You have to visit all the cities, starting from a given one and you do not need to return to your starting point. With the TSP, you can start anywhere, but you have to return to your start location.

By complete we mean that the algorithm guarantees to compute the optimal solution. The algorithm uses dynamic programming. Its time complexity is O(n^2 * 2^(n-1)), where n is the number of nodes to be visited, and '^' denotes exponentiation. Its space complexity is O(n * 2 ^ (n - 1)).

Note that the naive implementation of the SHPP exploring all permutations without memorizing intermediate results would have a complexity of (n - 1)! (factorial of (n - 1) ), which is much higher than n^2 * 2^(n-1). To convince oneself of this, just use Stirling's formula: n! ~ sqrt(2 * pi * n)*( n / exp(1)) ^ n. Because of these complexity figures, the algorithm is not practical for problems with more than 20 nodes.

Here is how the algorithm works: Let us denote the nodes to be visited by their indices 0 .. n - 1 Let us pick 0 as the starting node. Let d(i,j) denote the distance (or cost) from i to j. f(S, j) where S is a set of nodes and j is a node in S is defined as follows: f(S, j) = min (i in S \ {j}, f(S \ {j}, i) + cost(i, j)) (j is an element of S) Note that this formulation, from the original Held-Karp paper is a bit different, but equivalent to the one used in Caseau and Laburthe, Solving Small TSPs with Constraints, 1997, ICLP f(S, j) = min (i in S, f(S \ {i}, i) + cost(i, j)) (j is not an element of S)

The advantage of the Held and Karp formulation is that it enables:
   - to build the dynamic programming lattice layer by layer starting from the subsets with cardinality 1, and increasing the cardinality.


   - to traverse the dynamic programming lattice using sequential memory accesses, making the algorithm cache-friendly, and faster, despite the large

amount of computation needed to get the position when f(S, j) is stored.
   - TODO(user): implement pruning procedures on top of the Held-Karp algorithm.

The set S can be represented by an integer where bit i corresponds to

element i in the set. In the following S denotes the integer corresponding to set S.

The dynamic programming iteration is implemented in the method Solve. The optimal value of the Hamiltonian path starting at 0 is given by min (i in S, f(2 ^ n - 1, i)) The optimal value of the Traveling Salesman tour is given by f(2 ^ n, 0). (There is actually no need to duplicate the first node, as all the paths are computed from node 0.)

To implement dynamic programming, we store the preceding results of computing f(S,j) in an array M[Offset(S,j)]. See the comments about LatticeMemoryManager::BaseOffset() to see how this is computed.

Keywords: Traveling Salesman, Hamiltonian Path, Dynamic Programming, Held, Karp.

Classes
ElementIterator
HamiltonianPathSolver
LatticeMemoryManager
PruningHamiltonianSolver
Set
SetRangeIterator
SetRangeWithCardinality