Dynamic programming 0/49

Lesson 3 of 3 Advanced

Bitmask DP: states over subsets

Store the used items as a bitmask, add whatever else decides the remaining choices, and solve routes, pairings, groupings and rides over a small set.

5,897 words · 27 min read

Part 1 of 9 A round trip through every city

A round trip through every city

Some problems ask for the best order in which to do a small number of things: the order to visit a few cities, or to run a few jobs. Trying every ordering solves them up to about 10 items, because nn items have n!n! orderings: 10!10! is about 3.6 million, and 20!20! is about 2.4×10182.4 \times 10^{18}. This lesson reaches about 20 items with dynamic programming whose states are sets of the items. Its first problem is the best known of the kind, the travelling salesman problem.

There are NN cities in three-dimensional space, and city ii sits at the point (Xi,Yi,Zi)(X_i, Y_i, Z_i). Travelling from a city at (a,b,c)(a, b, c) to a city at (p,q,r)(p, q, r) costs ∣p−a∣+∣q−b∣+max⁡(0,r−c)|p - a| + |q - b| + \max(0, r - c): you pay the horizontal distance, and you pay for climbing but not for descending.

Start at city 1, visit every other city at least once and return to city 1. Print the smallest total cost. The input gives NN, then one line Xi Yi ZiX_i\ Y_i\ Z_i per city.

Constraints

  • 2≤N≤172 \le N \le 17
  • −106≤Xi,Yi,Zi≤106-10^6 \le X_i, Y_i, Z_i \le 10^6
  • No two cities are at the same point

Sample 1 · Input

2
0 0 0
1 2 3

Output

9

Sample 2 · Input

3
0 0 0
1 1 1
-1 -1 -1

Output

10

In the first sample the leg from city 1 up to city 2 costs 1+2+3=61 + 2 + 3 = 6 and the leg back down costs 1+2+0=31 + 2 + 0 = 3, so the round trip costs 9. The two directions of a leg can cost different amounts, because only climbing is paid for. In the second sample the round trip 1→2→3→11 \to 2 \to 3 \to 1 costs 3+4+3=103 + 4 + 3 = 10.

The statement says "at least once", so a route may pass through a city it has already visited. With this cost that never saves anything, because going straight from one city to another costs no more than going by way of a third (the Deeper read at the end of this part gives the reason). So we look for the cheapest round trip that visits every city exactly once.

The samples are too small to show how the search goes, so our example has four cities. They are numbered from 0, the way the program will number them, so the starting city, which the problem calls city 1, is city 0. A driver starts there, at the depot, delivers to cities 1, 2 and 3 in some order and drives back. The example gives the cost of each leg directly, as a driving time in minutes that is the same in both directions:

The leg from city 1 to city 3 takes 11 minutes. The programs call this table cost, so that entry is cost[1][3].

A round trip is fixed by the order of cities 1, 2 and 3. There are 3!=63! = 6 orders, few enough to list:

Every round trip from the depot, with its cost in minutes
OrderLegsTotal
0→1→2→3→00 \to 1 \to 2 \to 3 \to 02+6+7+122 + 6 + 7 + 1227
0→1→3→2→00 \to 1 \to 3 \to 2 \to 02+11+7+12 + 11 + 7 + 121
0→2→1→3→00 \to 2 \to 1 \to 3 \to 01+6+11+121 + 6 + 11 + 1230
0→2→3→1→00 \to 2 \to 3 \to 1 \to 01+7+11+21 + 7 + 11 + 221
0→3→1→2→00 \to 3 \to 1 \to 2 \to 012+11+6+112 + 11 + 6 + 130
0→3→2→1→00 \to 3 \to 2 \to 1 \to 012+7+6+212 + 7 + 6 + 227

The cheapest round trip takes 21 minutes. Two orders reach it, and each is the other driven backwards. Driving to the nearest unvisited city each time does not find it: that rule gives 0→2→1→3→00 \to 2 \to 1 \to 3 \to 0, which takes 30 minutes, because it leaves the far city for last and then pays 12 to get home.

Six orders are quick to list, but the number grows fast. With 17 cities, the limit of the problem, the 16 cities after the first can be ordered in 16!16! ways:

16!=20,922,789,888,000≈2.1×101316! = 20{,}922{,}789{,}888{,}000 \approx 2.1 \times 10^{13}

A loop written in Python runs roughly 10710^7 simple operations a second, so even at one operation per order the search would take more than three weeks.

Deeper read: why no city needs a second visit

Suppose a walk goes from a city xx to a city yy and on to a city zz, and yy is a city that the walk also visits at another time. Replace the two legs by the single leg from xx to zz, or by nothing when xx and zz are the same city. The walk still visits every city.

The direct leg also costs no more than the two legs it replaces. Each of its two horizontal distances, along XX and along YY, is at most the sum of the same distance on the two legs, by the triangle inequality for absolute values, and the same holds for its climb. With hxh_x, hyh_y and hzh_z for the heights of the three cities:

max⁡(0, hz−hx)≤max⁡(0, hy−hx)+max⁡(0, hz−hy)\max(0,\ h_z - h_x) \le \max(0,\ h_y - h_x) + \max(0,\ h_z - h_y)

Repeating the replacement removes every repeated visit without raising the cost, and what is left is a round trip that visits each city exactly once. In the second sample the official explanation walks through the cities 1, 2, 1, 3, 1 for a cost of 10, and the round trip 1→2→3→11 \to 2 \to 3 \to 1 also costs 10.