Bitmask DP in Python: travelling salesman over subsets

Why this matters

A travelling salesman must visit a list of cities, visit each one exactly once, and then return home. He wants the shortest total distance. This is the travelling salesman problem, usually shortened to TSP. The same problem shows up in delivery routes, in the order a drilling machine visits holes in a circuit board, and in any plan that orders stops along a loop.

The simplest method is to try every order of the cities and keep the shortest loop. Fix city 0 as the start, so only the other cities need ordering. With 4 cities there are 3 cities to order, which gives 3 * 2 * 1 = 6 orders. With 10 cities there are 9! orders, which is 362,880. With 20 cities there are 19! orders, which is 121,645,100,408,832,000. A computer that checks a billion orders per second would need about four years for that count.

Bitmask dynamic programming (DP) solves the same problem in about 2^n * n * n steps. For 20 cities that is roughly 400 million simple steps. Python runs each step much more slowly than compiled code, so the 20-city test in this lesson takes seconds, not milliseconds. Dynamic programming means solving a large problem from smaller pieces, storing each piece's answer in a table, and never solving the same piece twice. A bitmask is a way to store a set of cities as one whole number.

This lesson assumes you know lists, for loops, if statements and functions. A list is an ordered row of values, written [10, 20, 30]. lst[i] reads the value at position i, and positions count from 0. The lesson also uses the bit operators &, | and ^, and the shift <<. If those are new, the next section explains each one. The next lesson in this module, on assigning tasks to people, uses the same bit tricks on a different problem.

Sets stored as numbers

A bit is a single binary digit, either 0 or 1. Every whole number is a row of bits. The number 13 is 1101 in binary. Read the bits from the right. The rightmost bit stands for 1, the next for 2, then 4, then 8. The bits that are 1 add up to the number: 1 + 4 + 8 = 13.

Now give each city its own bit position. Number the cities 0, 1, 2 and 3. Position 0 belongs to city 0, position 1 to city 1, and so on. A set of cities becomes a number where bit c is 1 when city c is in the set. The set of cities 0, 2 and 3 has bits 0, 2 and 3 set and bit 1 clear:

bit position:   3   2   1   0
bit value:      1   1   0   1     which is binary 1101, or 13
cities in set:  3   2       0

Python gives five operations on these numbers. Each one is a single fast step.

• 1 << c is the number with only bit c set. The << operator moves bits to the left, so 1 << 2 is 4.
• mask | (1 << c) adds city c to the set. The | operator (called OR) gives 1 in a bit when either input has 1 there.
• mask & (1 << c) keeps only the bits that both inputs have set. The & operator is called AND. The result is 0 when city c is not in the set and a nonzero number when it is. In an if, 0 counts as false and any other number counts as true, so if mask & bit: tests membership.
• mask ^ (1 << c) removes city c, but only when city c is already in the set. The ^ operator (called XOR) flips the bit.
• mask.bit_count() counts how many cities are in the set. It is a method on the integer, available from Python 3.10 on.

Run this short program to see each one on the set 13:

Save it as bits.py and run it with python3 bits.py. The output is:

mask = 13 binary = 0b1101
contains 2? True
contains 1? False
add 1: 15
remove 3: 5
count: 3
full set of 4 cities: 15
1 << 20 = 1048576
1 << 31 = 2147483648
1 << 100 = 1267650600228229401496703205376

bin() writes a number in binary and puts 0b in front to show that it is binary. Python reads & before !=, so mask & bit != 0 also works. The brackets are kept in this lesson so the order is obvious to a reader.

The full set of n cities is (1 << n) - 1. For 4 cities that is 15, which is 1111 in binary. Every set of 4 cities is a whole number from 0 to 15, so a table with 16 slots can hold one entry per set. For 20 cities there are 2^20, which is 1,048,576 sets.

Python integers have no fixed size. The last two lines of the output show the difference from a 32-bit integer in Java. 1 << 31 is 2147483648 here, not a negative number, and 1 << 100 is printed in full. The bitmask method stops being practical at about 20 cities because the table doubles with each extra city, not because of overflow.

The main idea: keep the best way to stand in each place

Here is the example that the rest of the lesson uses. Four cities, with the distance between each pair. The distances are the same in both directions, which is the common case for roads that can be driven either way. The program in this lesson also works when the two directions differ, but the example keeps the numbers easy to follow.

            to 0   to 1   to 2   to 3
from 0        0     10     15     20
from 1       10      0     35     25
from 2       15     35      0     30
from 3       20     25     30      0

A route is a list of cities in visiting order. Its cost is the sum of the distances between neighbours in the list, plus the distance from the last city back to city 0.

The program fills a table with one entry for each pair (set, last city):

• The set is the cities visited so far. It always contains city 0.
• The last city is the city the salesman is standing in now. It is one of the cities in the set.
• The entry is the smallest total distance of any route that starts at city 0, visits exactly the cities in that set, and ends at that last city.

Why keep only the smallest entry? Suppose two routes both visit all four cities and both end at city 2. One route, 0, 1, 3, 2, costs 65. The other, 0, 3, 1, 2, costs 80. The rest of the trip is the same for both: return home from city 2, which costs 15. So the 80 route can never beat the 65 route, and the program can throw it away. This is the core fact behind bitmask DP: once you know the set and the current city, the past order does not matter for the future.

The program starts from one known entry: the set {0} with the salesman standing at city 0 has cost 0. From each entry, it tries every city not yet in the set. Moving to a new city d from entry (set, c) makes a new entry (set plus d, d) with cost equal to the old cost plus the distance from c to d. If that new entry already has a value, the program keeps the smaller one.

When every set has been processed, the program looks at each entry where all cities are in the set. For each one it adds the distance back to city 0. The smallest of these totals is the answer.

Worked example, one layer at a time

The sets are processed in order of their size. Each layer below lists the entries that the program fills, with the cost of the cheapest route for each. These numbers are worked out by hand.

Layer 1, only city 0 visited:

• set {0}, standing at 0: cost 0

Layer 2, two cities visited:

• set {0, 1}, standing at 1: 0 + 10 = 10
• set {0, 2}, standing at 2: 0 + 15 = 15
• set {0, 3}, standing at 3: 0 + 20 = 20

Layer 3, three cities visited. Each set has two possible last cities, so each set has two entries. Each entry has one predecessor, because the previous city must be the one other city in the set:

• set {0, 1, 2}, standing at 2: from {0, 1} at 1, cost 10 + 35 = 45
• set {0, 1, 2}, standing at 1: from {0, 2} at 2, cost 15 + 35 = 50
• set {0, 1, 3}, standing at 3: from {0, 1} at 1, cost 10 + 25 = 35
• set {0, 1, 3}, standing at 1: from {0, 3} at 3, cost 20 + 25 = 45
• set {0, 2, 3}, standing at 3: from {0, 2} at 2, cost 15 + 30 = 45
• set {0, 2, 3}, standing at 2: from {0, 3} at 3, cost 20 + 30 = 50

Layer 4, all four cities visited. The program needs an entry for each possible last city. For each one it compares the predecessors and keeps the smaller total:

• standing at 1: from {0, 2, 3} at 3 costs 45 + 25 = 70, and from {0, 2, 3} at 2 costs 50 + 35 = 85. Keep 70.
• standing at 2: from {0, 1, 3} at 3 costs 35 + 30 = 65, and from {0, 1, 3} at 1 costs 45 + 35 = 80. Keep 65.
• standing at 3: from {0, 1, 2} at 2 costs 45 + 30 = 75, and from {0, 1, 2} at 1 costs 50 + 25 = 75. Keep 75.

Close the loop by adding the distance back to city 0:

• last city 1: 70 + 10 = 80
• last city 2: 65 + 15 = 80
• last city 3: 75 + 20 = 95

The smallest total is 80. Two different loops reach it: 0, 2, 3, 1, 0 and 0, 1, 3, 2, 0. Both have a total of 80. The program keeps the first one it finds, because it only replaces a value when the new one is strictly smaller.

The program

Create a file named tsp.py:

Run it with python3 tsp.py. The output is:

best cost: 80
route: [0, 2, 3, 1, 0]

The code has four parts worth reading slowly.

The table is one flat list. The entry for (set, last city) lives at index mask * n + last. A list of lists would also work, but it would create one separate row object for each of the 2^n sets. One flat list avoids that, and the common mistakes section shows a trap that comes with list of lists.

The loop over masks is range(1, full, 2). It counts 1, 3, 5, and so on up to full, without the last value. Every set this program uses contains city 0, and in binary that means bit 0 is 1, so the set number is odd. The loop never visits the even numbers, which skips sets the program would never use.

The parent list records the city the salesman came from for each entry. It is what makes the route recoverable. The program does not store whole routes in the table, which would take far more memory. It stores one city per entry and rebuilds the route at the end.

The rebuild starts at the best last city with the full set. It adds the city to the route, looks up where it came from, removes the city from the set, and repeats until it reaches the start, where the stored parent is -1. The cities come out in reverse order, so the list is reversed at the end. A Python list works as a stack: append adds to the end, and reverse() flips the whole list.

The if __name__ == "__main__": line runs the test code only when the file is run directly. When another file imports solve, that code does not run. The 20-city test below relies on this.

Example 2: rebuilding the route

Follow the rebuild for the answer above. The program picked last city 1, because it was the first of the two tied totals it found. The rebuild starts from the full set standing at city 1, and each step reads the stored parent, removes the current city from the set, and moves to that parent:

1. Full set {0, 1, 2, 3}, standing at 1. The stored parent is 3, which came from {0, 2, 3} standing at 3. Add 1 to the route. Remove 1 from the set, leaving {0, 2, 3}.
2. Standing at 3 with set {0, 2, 3}. The stored parent is 2, which came from {0, 2} standing at 2. Add 3. Remove 3, leaving {0, 2}.
3. Standing at 2 with set {0, 2}. The stored parent is 0. Add 2. Remove 2, leaving {0}.
4. Standing at 0 with set {0}. The stored parent is -1, which marks the start. Add 0. The loop stops.

The list now holds 1, 3, 2, 0. Reversing it gives 0, 2, 3, 1, and adding city 0 at the end closes the loop. This matches the program's output, route: [0, 2, 3, 1, 0]. Each step needs only one lookup in the table, so the rebuild takes one step per city.

Example 3: 20 cities

The next program measures the method at the size the title promises. Distances are generated from a formula, so the same numbers come out every time. The formula gives every pair of cities a distance between 10 and 99. Save this file as big.py in the same folder as tsp.py:

import time
 
from tsp import solve
 
n = 20
dist = [[0] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if i != j:
            a = min(i, j)
            b = max(i, j)
            dist[i][j] = (a * 31 + b * 17) % 90 + 10
 
start = time.perf_counter()
cost, route = solve(dist)
ms = (time.perf_counter() - start) * 1000
print("cities:", n)
print("best cost:", cost)
print("route length (cities listed):", len(route))
print("first 6 cities:", route[:6])
print("elapsed ms:", round(ms))

Run it with python3 big.py. On the machine used to test this lesson, with Python 3.14.4, the output was:

cities: 20
best cost: 364
route length (cities listed): 21
first 6 cities: [0, 16, 12, 8, 18, 5]
elapsed ms: 7549

The elapsed time changes from run to run and between machines. The route lists 21 entries because the start city 0 appears again at the end. The route[:6] in the code is a slice, which means the first six items of the list.

The memory cost is the part to plan for. For 20 cities the table has 2^20 * 20, which is 20,971,520 slots. Each slot in a Python list holds one 8-byte reference, so one list of that size takes 167,772,160 bytes, about 160 MiB. The program uses two such lists, best and parent. Each stored total is also a separate integer object, which adds more memory on top of the list. The total depends on the machine and on the Python build.

The Java version of this lesson, on the same problem and the same 20 cities, finished in about 0.4 seconds. Python does the same steps in an interpreter, so it is much slower. That trade is the reason to know the method before choosing the language for a large job.

Common mistakes

Starting the table at 0 instead of infinity. Unreachable entries must start at infinity, so that they never look like cheap routes. If the table starts at 0, every entry looks reachable with cost 0. The program then prints an answer that is too small and gives no error. Changing the table line to best = [0] * (full * n) and running the same 4-city example prints:

best cost: 10
route: [1, 0]

The true answer is 80. Test the code with a case you can work out on paper.

Sizing the table with full instead of full * n. The index for each entry is mask * n + last, so the table needs full * n slots. A copy with only full slots fails on the first lookup past the end:

  File "tsp_size.py", line 27, in solve
    if candidate < best[idx]:
                   ~~~~^^^^^
IndexError: list index out of range

The traceback names the line that reads the table. The file name in your own traceback will be the name of your file.

Making a list of lists with *. Writing grid = [[0] * 2] * 3 does not make three separate rows. It makes three references to one row, so changing one row changes all of them. After grid[0][1] = 5, Python 3.14 prints grid:

[[0, 5], [0, 5], [0, 5]]

The correct way is a list comprehension, which builds a new row each time: [[0] * 2 for _ in range(3)]. With that version, the same change prints [[0, 5], [0, 0], [0, 0]]. This lesson avoids the problem by using one flat list.

Adding a cost to an unreachable entry. Adding to math.inf gives inf, so the value stays unreachable. Python integers never wrap around, so there is no overflow risk as there is in a 32-bit language. The program still checks for inf before it adds, because the check also skips the work of looking at the entry.

Mixing up the set and the city. The table entry is about a set and a city together. A common slip is to store a cost per set alone, which loses the information about where the salesman is standing. The same set with a different last city can have a different cost, and the future route depends on the last city.

Counting sets in the wrong order. The program fills a set only from smaller sets. Adding a city always makes the number larger, because mask | bit is bigger than mask when the bit was not set. Since the loop counts up from 0, every smaller set is finished before a bigger one reads it. A loop that counts down would read entries that are not yet filled.

Practice

Exercise 1. With 4 cities numbered 0 to 3, what is the bitmask for the set of cities 1 and 3? Write the answer in binary and in decimal.

Show the answer

Bit 1 has value 2 and bit 3 has value 8. The binary number is 1010, and 2 + 8 = 10, so the bitmask is 10 in decimal.

Exercise 2. The bitmask is 22, which is 10110 in binary. Which cities are in the set? The cities are numbered from 0.

Show the answer

Bits 1, 2 and 4 are set, since 22 = 16 + 4 + 2. The set contains cities 1, 2 and 4.

Exercise 3. How many routes are there for 5 cities that start and end at city 0, when a route and its reverse count as two different routes?

Show the answer

Fix city 0 at the start and the end. The other 4 cities can be ordered in 4!, which is 4 * 3 * 2 * 1 = 24 ways.

Exercise 4. For 4 cities, count the pairs (set, last city) where the set contains city 0, the last city is not 0, and the last city is in the set. The pair ({0, 1}, 1) counts. The pair ({0, 1}, 2) does not.

Show the answer

The set of other cities is a subset of {1, 2, 3}. A subset with k cities gives k choices for the last city. Over all subsets, that sums to 12, because each of the three cities appears as a chosen city in 4 of the 8 subsets. In the worked example, all 12 pairs have a finite cost.

Exercise 5. How many bytes does one list of the table take for 18 cities? Use 8 bytes per slot, and ignore the integer objects.

Show the answer

The table has 2^18 * 18 = 262,144 * 18 = 4,718,592 slots. At 8 bytes each, that is 37,748,736 bytes, or about 36 MiB for one list. The program uses two lists, so about 72 MiB before the integer objects.

Summary

• A set of cities can be stored as one integer, with bit c set when city c is in the set.
• The table entry for (set, last city) holds the cheapest route that starts at city 0, visits exactly that set, and ends at the last city.
• Only the cheapest entry for each (set, last city) pair needs to be kept, because the rest of the trip depends only on the set and the current city.
• The parent list records the previous city, so the route can be rebuilt from the end with a list used as a stack.
• The method does about 2^n * n * n steps and needs about 2^n * n slots per list, which is practical up to about 20 cities.