Branch and Bound: Travelling Salesman Problem
Solve the Travelling Salesman Problem by exploring partial tours in a state-space tree, bounding each branch, and pruning the ones that cannot beat the best tour found so far.
The Travelling Salesman Problem (TSP)
A salesman must visit every city exactly once and then return to the city he started from. Each pair of cities is a known distance apart. The goal is to find the route with the smallest total distance.
We will use a small example with 4 cities (0, 1, 2, 3). Here is the distance table — the number in row i, column j is the distance between city i and city j:
0 1 2 3
0 [ 0 10 15 20 ]
1 [ 10 0 35 25 ]
2 [ 15 35 0 30 ]
3 [ 20 25 30 0 ]
Why not just try every route? A tour starting at city 0 can visit the other cities in any order, so there are (n − 1)! possible tours. For 4 cities that is only 3! = 6 tours — easy. But the number explodes fast: 10 cities give 9! = 362,880 tours, and 15 cities give 14! ≈ 87 billion. Brute force quickly becomes impossible.
The Branch and Bound Idea
Branch and bound is a smart way to search without trying every tour. It has three parts:
- Branch: Build tours step by step. Start at city 0, then pick the next city, then the next, and so on. Each choice creates a new branch in a state-space tree of partial tours.
- Bound: For each partial tour, compute a lower bound — a number that can never be larger than the cost of any complete tour that grows out of this partial tour.
- Prune: Keep track of the best complete tour found so far. If a partial tour's lower bound is greater than or equal to the best complete tour, then no tour from this branch can beat it. So we prune (skip) the whole branch and never explore it.
Because one good bound can throw away thousands of routes at once, branch and bound usually explores far fewer tours than brute force.
The Lower Bound We Use
Our bound is simple and always safe (it never overestimates):
bound = cost so far + (cheapest edge leaving the current last city) + (cheapest edge leaving each city not yet visited)
Why is this safe? In any complete tour, every city must leave along some edge. We replace each of those real edges with the cheapest possible edge from that city. The real tour can only cost the same or more, so our estimate never goes over the true cost. An estimate that never overestimates is called admissible, and that is exactly what lets us prune without ever throwing away the real best tour.
Small calculation. Take the partial path 0 → 1 (cost so far = 10). The last city is 1, and cities 2 and 3 are still unvisited.
- cost so far = 10
- cheapest edge leaving city 1 (to an unvisited city or back to start): min(10 to 0, 35 to 2, 25 to 3) = 10
- cheapest edge leaving city 2: min(15 to 0, 30 to 3) = 15
- cheapest edge leaving city 3: min(20 to 0, 25 to 1, 30 to 2) = 20
bound = 10 + 10 + 15 + 20 = 55. So no tour beginning 0 → 1 can ever cost less than 55.
Step-by-Step Visualization
Watch branch and bound build the tour. Cyan edges show the current partial path. The panel on the right shows the best complete tour found so far in green. When a branch's bound cannot beat the best tour, it is pruned (shown in red) and skipped.
Pseudocode
We do a depth-first search over partial tours. At each step we compute the bound and prune when it cannot beat the best tour found so far.
1BRANCH-AND-BOUND-TSP(dist, start)2 best = +infinity3 bestPath = empty4 DFS(path = [start], cost = 0)5 return bestPath, best67DFS(path, cost)8 last = last city in path9 if path contains all cities10 total = cost + dist[last][start] // close the tour11 if total < best12 best = total13 bestPath = path + [start]14 return15 for each city next not in path16 newCost = cost + dist[last][next]17 bound = LOWER-BOUND(path + [next], newCost)18 if bound >= best19 continue // prune this branch20 DFS(path + [next], newCost)2122LOWER-BOUND(path, cost)23 b = cost24 b += cheapest edge leaving the last city of path25 for each city c not in path26 b += cheapest edge leaving c27 return b
Complexity Analysis
In the worst case branch and bound still examines an exponential number of tours, so the time is O(n!). The recursion only stores the current path, so the extra space is O(n). The key point: a good lower bound prunes most branches, so in practice the algorithm explores far fewer tours than the full (n − 1)! brute-force search.
Complexity Analysis
Time Complexity
O(n!) worst case
Space Complexity
O(n)
Branch and bound still has exponential worst case, but a good lower bound prunes most branches, so in practice it explores far fewer than all (n-1)! tours.
Growth Rate Comparison
Interactive Playground
Step through the full search at your own pace. Use the controls to play, pause, and move forward or backward through every explore, prune, and backtrack step.