Expand description
§All in a Single Night
This is a variant of the classic NP-hard Travelling Salesman Problem.
There are 8 locations, so naively it would require checking 8! = 40,320 permutations. We can reduce this to 7!/2 = 2,520 permutations by arbitrarily choosing one of the locations as the start, and skipping lexically reversed permutations (since the path a->b->c has the same length as c->b->a). Computing the shortest and longest path is then done by completing the cycle for each permutation, then discarding the longest or shortest edge seen along the way. Skipping lexically reversed permutations is possible with [Steinhaus-Johnson-Trotter][Steinhaus-Johnson-Trotter’s algorithm].
However, since the graph is complete (every node has a distance to every other node), this
particular problem can be solved even faster, by avoiding the overhead of permutations and
instead using Held-Karp’s dynamic programming solution. This algorithm is
O(n²*2ⁿ); for our puzzle with 8 nodes, this gives 8*7/2*256/2 or 3,584 comparisons needed.
On the surface, this is more comparisons than the 2,520 sequences visited by the O(n!)
permutation solution, but set manipulation is less expensive than computation of permutations
followed by casting out the longest or shortest edge, so it is an overall win.
The core behavior of Held-Karp involves computing the function g(set, k) for all possible sets of cities, where the function represents the best (shortest or longest) distance seen so far for a given set of cities and ending on the city k which is a member of the set. Unlike the permutations approach which visits every path in the graph, Held-Karp discards information along the way to compute only the best cycle in a graph anchored to a given start point. It is easy to demonstrate a graph where the best path is not part of the best cycle (discarding the longest edge from the shortest cycle might leave you with a path longer than the graph’s true shortest path, if that other path had a different start anchor). But this is easy to work around, by adding a ninth “location” with distance 0 to every other location, and using that location as the start and end for every cycle, at which point the best cycle of nine includes the best path of all eight locations.
The algorithm is recursive: with a base case of g({k},k) being zero (the best distance to a singleton set from our ninth point is 0), all other g(set,k) can be computed by iterating over each member of set excluding k, and choosing the best variant g(set∖k,m)+d(k,m) possible from a smaller set ending in m. Iterating over bitmasks from 0 to 255 ensures that all earlier subsets are available when computing for a larger set.
For speed we first convert each location into an index, then store the distances between every pair of locations in an array for fast lookup. Storing sets plus the last city visited requires 8 bits for the set and 3 bits for the city, for a total table size of 2¹¹ distances.
Functions§
Type Aliases§
- Result 🔒