Solving the Travelling Salesman Problem with Dynamic Programming

The Travelling Salesman Problem (TSP) is a classic algorithmic challenge that, despite its seemingly simple premise, holds significant complexity and real-world relevance. Imagine a salesman needing to visit a set number of cities and return to their starting point, all while minimizing the total distance travelled. This, in essence, is the TSP. Finding the most efficient route is not just a matter of academic curiosity; it has profound implications for logistics, transportation, and various optimization problems across industries.

This article delves into how dynamic programming, a powerful algorithmic technique, can be employed to solve the Travelling Salesman Problem effectively. We will explore the core concepts, the step-by-step approach, and the implementation details, making this complex problem accessible and understandable.

Understanding the Travelling Salesman Problem

At its heart, the Travelling Salesman Problem asks: “Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?”.

To illustrate, consider a salesman based in city A who needs to visit cities B, C, and D before returning to A. There are several possible routes, such as A-B-C-D-A, A-C-B-D-A, A-D-C-B-A, and so on. The challenge lies in finding the route with the minimum total distance.

While for a small number of cities, one could manually evaluate all possible routes, this approach quickly becomes computationally infeasible as the number of cities increases. For ‘n’ cities, there are (n-1)! possible routes, making a brute-force approach exponentially complex and impractical for even moderately sized problems.

This is where dynamic programming steps in as a more efficient solution.

Dynamic Programming: A Smarter Approach to TSP

Dynamic programming is an algorithmic technique that solves complex problems by breaking them down into smaller, overlapping subproblems, solving each subproblem only once, and storing their solutions to avoid redundant computations. This approach is particularly well-suited for problems exhibiting optimal substructure and overlapping subproblems, both of which are characteristics of the Travelling Salesman Problem.

In the context of TSP, dynamic programming allows us to build up the solution incrementally. Instead of calculating the cost of complete tours from scratch, we calculate and store the minimum costs to reach each city having visited a subset of cities.

Formulating the Dynamic Programming Solution

To apply dynamic programming to the Travelling Salesman Problem, we need to define a state and a recurrence relation.

State Definition:

Let tsp(curr, mask) represent the minimum cost to complete a tour starting from city curr, having already visited the cities represented by the mask. Here, curr is the current city the salesman is in, and mask is a bitmask representing the set of cities already visited. Each bit in the mask corresponds to a city; if the i-th bit is set, it means city ‘i’ has been visited.

Recurrence Relation:

The core idea is to decide which city to visit next from the current city curr. We want to explore all unvisited cities and choose the one that leads to the minimum total cost. The recurrence relation can be defined as:

tsp(curr, mask) = min { cost[curr][i] + tsp(i, mask | (1 << i)) }

for all cities i that have not been visited yet (i.e., the i-th bit in mask is not set).

Here:

curr is the current city.
mask represents the set of already visited cities.
cost[curr][i] is the cost (distance) to travel from city curr to city i.
tsp(i, mask | (1 << i)) is the minimum cost to complete the tour starting from city i, after adding city i to the set of visited cities (updated mask).

We take the minimum of these values over all possible next cities i to find the optimal path.

Base Case:

The base case occurs when all cities have been visited. This is indicated when the mask has all bits set, which can be checked by mask == (1 << n) - 1, where ‘n’ is the total number of cities. When all cities are visited, the salesman must return to the starting city (city 0). Therefore, the base case is:

tsp(curr, mask) = cost[curr][0]  if mask == (1 << n) - 1

Memoization for Efficiency:

The recursive relation tsp(curr, mask) exhibits overlapping subproblems. The same subproblems (same values of curr and mask) are calculated multiple times in different recursive branches. To avoid these redundant calculations and significantly improve efficiency, we use memoization.

Memoization involves storing the results of computed subproblems in a table (or a memoization table). Before computing tsp(curr, mask), we first check if the result for this state is already present in the memoization table. If it is, we directly return the stored value; otherwise, we compute it, store it in the table, and then return it.

This top-down dynamic programming approach with memoization reduces the time complexity drastically.

Step-by-Step Algorithm

Initialization: Create a memoization table memo[n][2^n] and initialize all entries to -1 (or some other indicator of “not computed”).
Base Case: If mask == (1 << n) - 1, return cost[curr][0].
Memoization Check: If memo[curr][mask] is not -1, return memo[curr][mask].
Recursive Calculation: Initialize ans = infinity. Iterate through all cities i from 0 to n-1.
- If city i is not visited (check the i-th bit in mask), calculate ans = min(ans, cost[curr][i] + tsp(i, mask | (1 << i))).
Store and Return: Store the calculated minimum cost in memo[curr][mask] = ans and return ans.
Initial Call: Start the TSP tour from city 0 with no cities visited initially (mask = 1, as city 0 is the starting city and considered visited in the initial state). Call tsp(0, 1, n, cost, memo).

Python Code Implementation

import sys

def totalCost(mask, curr, n, cost, memo):
    if mask == (1 << n) - 1:
        return cost[curr][0]

    if memo[curr][mask] != -1:
        return memo[curr][mask]

    ans = sys.maxsize
    for i in range(n):
        if (mask & (1 << i)) == 0:
            ans = min(ans, cost[curr][i] + totalCost(mask | (1 << i), i, n, cost, memo))

    memo[curr][mask] = ans
    return ans

def tsp(cost):
    n = len(cost)
    memo = [[-1] * (1 << n) for _ in range(n)]
    return totalCost(1, 0, n, cost, memo)

cost = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]
res = tsp(cost)
print(res) # Output: 80

This Python code demonstrates the dynamic programming approach to solving the Travelling Salesman Problem. It utilizes memoization to store and reuse the results of subproblems, significantly optimizing the computation.

Complexity Analysis

Time Complexity: O(n^2 2^n). There are n 2^n possible states (combinations of curr and mask). For each state, we iterate through at most ‘n’ cities to find the minimum cost.
Space Complexity: O(n * 2^n). This is due to the memoization table memo[n][2^n] used to store the results of subproblems.

Conclusion

Dynamic programming provides a significant improvement over naive brute-force approaches to solve the Travelling Salesman Problem. By breaking down the problem into smaller, overlapping subproblems and utilizing memoization, we achieve a much more efficient solution with a time complexity of O(n^2 * 2^n).

While TSP remains an NP-hard problem, dynamic programming offers a practical and powerful approach for solving it for a moderate number of cities. Understanding and applying dynamic programming to the Travelling Salesman Problem not only solves a classic computer science puzzle but also provides valuable insights into optimization techniques applicable across various fields, from logistics and supply chain management to circuit board design and beyond.