Advanced Conceptsbitmaskminimizationgraph

Traveling Salesman Problem

Given n cities and the travel cost between every pair of them, starting and ending at the same city, find the minimum-cost route that visits every other city exactly once.

Do this lesson first: coin change

Example input

dist = [[0, 5, 3, 4], [5, 0, 1, 9], [3, 1, 0, 2], [4, 9, 2, 0]], four cities, home is city 0

Expected output

12

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

dp[mask][j] is the cheapest cost of a route that starts at home, has visited exactly the cities in mask, each once, and is standing at city j, which is one of them. The single exception is the starting point, dp[0000][0]: standing at home before visiting anything, so home sits outside the empty set. The mask is a set written as a binary number, bit k for city k. Notice what the state forgets: the ORDER the cities were visited in. Two routes through {1, 2, 3} that both end at city 3 face exactly the same future, the same cities left and the same place to leave from, so only the cheaper of them is worth remembering. That forgetting is the whole method. It turns (n - 1)! orderings into 2^(n - 1) sets times n endpoints.

dp[mask][j] = min over k in mask without j of dp[mask without j][k] + dist[k][j], and when mask without j is empty the only k is home, read from dp[0000][0]

Ask where the route stood just before it arrived at j. Call that city k. Before the last leg the route had visited every city in mask except j and was standing at k, and the cheapest way to be in that position is dp[mask without j][k], the same question on a set one city smaller. Add the leg dist[k][j] and you have one candidate per possible k. It is a min because exactly one city was the predecessor and you want the cheapest of them. The trip home is not a special case: it is the same rule applied once more, at the full set, standing at home. In code, mask without j is mask & ~(1 << j), which clears j's bit.

One base: dp[0000][0] = 0, standing at home having visited nothing. Every other cell clears one bit to find its predecessors, so it only ever reads a SMALLER mask, and filling the rows in increasing mask order guarantees every predecessor is final before it is read. Two kinds of cell are missing on purpose, shown as dots. A cell whose city is not in its own set cannot exist, since you cannot stand somewhere you have not been; the base is the one exception, home before the route begins. And the rows skip every set that contains home but not everything, because such a set describes a route that came home before the tour was over. Home's bit appears in exactly one row, the last, where it is the final city visited. That also keeps the table at 9 rows for 4 cities rather than 16.

Tabulation. The answer takes a min over every route, so every reachable (set, city) pair has to be priced anyway, and memoization would visit the same states with call overhead added. The cost is 2^(n - 1) × n cells with up to n candidates each. At four cities there are only 3! = 6 orderings, 24 leg additions in all, so at this size the table is a demonstration rather than a saving. It pays off as n grows: at 16 cities brute force faces 15!, about 1.3 trillion orderings, while the table holds 2^15 × 16 cells of at most 16 candidates each, about 8.4 million reads. Still exponential, which is the honest headline: this is the best known exact method, not a fast one, and memory is as much the limit as time, since at 25 cities the table alone holds 2^24 × 25, about 420 million entries.

Time O(2^n × n^2)Space O(2^n × n)

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

One base: dp[0000][0] = 0, standing at home having visited nothing. Every other cell clears one bit to find its predecessors, so it only ever reads a SMALLER mask, and filling the rows in increasing mask order guarantees every predecessor is final before it is read. Two kinds of cell are missing on purpose, shown as dots. A cell whose city is not in its own set cannot exist, since you cannot stand somewhere you have not been; the base is the one exception, home before the route begins. And the rows skip every set that contains home but not everything, because such a set describes a route that came home before the tour was over. Home's bit appears in exactly one row, the last, where it is the final city visited. That also keeps the table at 9 rows for 4 cities rather than 16.

Rows ↓
Cols →

0 home

city 1

city 2

city 3

0000

0

·

0010

·

5

·

0100

·

3

·

0110

·

4

6

·

1000

·

4

1010

·

13

·

14

1100

·

6

5

1110

·

7

14

8

1111

12

·

Rows ↓mask: the set of cities visited, bit k for city k, so the rightmost digit is home; home's bit is set only in the last row

Cols →city j where the route is standing

traveling-salesman-problem.ts

1function tsp(dist) {
2 const n = dist.length, FULL = (1 << n) - 1;
3 const dp = Array.from({ length: FULL + 1 }, () => new Array(n).fill(Infinity));
4 dp[0][0] = 0; // at home, nothing visited yet
5 for (let mask = 1; mask <= FULL; mask++) {
6 if (mask & 1 && mask !== FULL) continue; // home comes last, never midway
7 for (let j = 0; j < n; j++) {
8 if (!(mask & (1 << j))) continue; // you can only stand on a visited city
9 if (mask === FULL && j !== 0) continue; // the tour ends at home
10 const prev = mask & ~(1 << j);
11 for (let k = 0; k < n; k++)
12 dp[mask][j] = Math.min(dp[mask][j], dp[prev][k] + dist[k][j]);
13 }
14 }
15 return dp[FULL][0];
16}

Base caseComputedBeing readAnswer

The code, the trap, the variations

traveling-salesman-problem.ts

1function tsp(dist) {
2 const n = dist.length, FULL = (1 << n) - 1;
3 const dp = Array.from({ length: FULL + 1 }, () => new Array(n).fill(Infinity));
4 dp[0][0] = 0; // at home, nothing visited yet
5 for (let mask = 1; mask <= FULL; mask++) {
6 if (mask & 1 && mask !== FULL) continue; // home comes last, never midway
7 for (let j = 0; j < n; j++) {
8 if (!(mask & (1 << j))) continue; // you can only stand on a visited city
9 if (mask === FULL && j !== 0) continue; // the tour ends at home
10 const prev = mask & ~(1 << j);
11 for (let k = 0; k < n; k++)
12 dp[mask][j] = Math.min(dp[mask][j], dp[prev][k] + dist[k][j]);
13 }
14 }
15 return dp[FULL][0];
16}

Where people go wrong

Walking to the nearest unvisited city each time. From home the cheapest leg on this map is city 2 at 3, then city 1 at 1, and now the only city left is 3, nine away from city 1, before 4 more to get home: 3 + 1 + 9 + 4 = 17. Both 12-cost tours open with a dearer leg, 5 to city 1 or 4 to city 3, and neither touches the 9. A cheap step is worth nothing if it strands you, and only something that prices every set of visited cities can see that. The second slip is quieter: stopping at the row of all away cities and reporting its smallest cell, 7 here, which forgets the leg home and is the answer to a different problem.

Drop the return trip: the route starts at home and may end anywhere.
State, recurrence and order are unchanged; the full-set row disappears and the answer becomes the smallest cell in the row of all away cities, 7 on this map. That is a min over a row rather than one cell, so you read it off the table instead of storing it.
Make costs one-way, so dist[k][j] and dist[j][k] can differ.
Nothing in the recurrence assumed they were equal, so nothing changes. What goes away is the tie in the final cell: a tour and its reverse now usually cost different amounts.
Add a fifth city.
The method is unchanged, but the table needs 16 home-free sets plus the full set, 17 rows, which is past this page's 10-row budget. That is why the slider stops at four cities. The home-free rows double with every city added, 4, 8, 16, plus the one final row, which is the exponential cost showing up as screen space.

Bitmasking and DP Digit DP