The Travel 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 of cities and return to their starting point, aiming to minimize the total travel distance. This, in essence, is the core of the Travel Salesman Problem. This article delves deep into understanding the TSP, exploring various approaches to solve it, and focusing on the efficient dynamic programming solution.
Understanding the Travel Salesman Problem (TSP)
At its heart, the Traveling 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?”.
It’s crucial to distinguish TSP from the Hamiltonian Cycle problem. While a Hamiltonian cycle simply asks if a tour exists that visits every city exactly once, TSP goes a step further. TSP assumes a Hamiltonian tour exists (especially in a complete graph where every city is connected to every other city) and seeks to find the minimum cost Hamiltonian Cycle among potentially many.
Let’s consider a couple of examples to solidify our understanding:
Example 1:
Imagine only two cities with the following costs:
cost = [[0, 111],
[112, 0]]Here, the salesman starts at city 0, visits city 1, and returns to city 0. The total cost is 111 (from city 0 to 1) + 112 (from city 1 to 0) = 223.
Example 2:
Now, consider three cities with these costs:
cost = [[0, 1000, 5000],
[5000, 0, 1000],
[1000, 5000, 0]]One optimal route is 0 -> 1 -> 2 -> 0, with a cost of 1000 + 1000 + 1000 = 3000. This is the minimum cost to visit all cities and return to the starting point.
Brute-Force Approach: Exploring All Permutations
One straightforward, albeit inefficient, way to solve the TSP is to try every possible route. Since we need to visit each city exactly once, we can generate all permutations of the cities. For ‘n’ cities, there are (n-1)! possible routes (since we start and end at the same city, city 0 in this case, we fix the starting point and permute the rest).
For each permutation, we calculate the total cost of the tour. By comparing the costs of all permutations, we can identify the route with the minimum cost.
However, this brute-force approach has a time complexity of O(n!), which grows incredibly fast with the number of cities. For even a moderate number of cities, this approach becomes computationally infeasible. This highlights the need for more efficient algorithms.
Dynamic Programming Solution: Recursion and Bitmasking
To overcome the exponential time complexity of the brute-force method, we can employ dynamic programming. Dynamic programming excels at solving problems with overlapping subproblems and optimal substructure, and TSP fits this description perfectly.
Our dynamic programming approach will utilize recursion and bitmasking to efficiently explore possible routes and store intermediate results.
Defining the State
We define a function tsp(curr, mask) which represents the minimum cost to complete a tour starting from curr city, having already visited the cities represented by the mask. Here:
curr: Indicates the current city the salesman is in.mask: A bitmask representing the set of cities already visited. If the i-th bit of the mask is set to 1, it means city ‘i’ has been visited.
Recurrence Relation
The core of our dynamic programming solution lies in the recurrence relation:
tsp(curr, mask) = min(cost[curr][i] + tsp(i, mask | (1 << i))) for all cities i that have not yet been visited (i.e., the i-th bit in mask is 0).
Explanation:
To calculate tsp(curr, mask), we consider all possible next cities i that haven’t been visited yet. For each unvisited city i, we:
- Calculate the cost of traveling from the
currcity to cityi:cost[curr][i]. - Recursively calculate the minimum cost to complete the tour starting from city
i, with cityinow marked as visited in the mask:tsp(i, mask | (1 << i)). The(mask | (1 << i))operation sets the i-th bit in the mask, indicating that cityiis now visited. - We take the minimum of these costs over all possible next cities
i. This gives us the minimum costtsp(curr, mask).
Base Case
The base case for our recursion is when all cities have been visited. This occurs when the mask represents all cities visited. If we have ‘n’ cities, this condition is met when mask == ((1 << n) - 1). In this situation, the tour is almost complete. We just need to return to the starting city (city 0).
tsp(curr, mask) = cost[curr][0] when mask == ((1 << n) - 1).
This base case returns the cost of traveling from the curr city back to the starting city (city 0), completing the tour.
Optimization with Memoization (Top-Down DP)
The recursive solution described above still involves redundant calculations. We might encounter the same subproblem tsp(curr, mask) multiple times in different recursive paths. To optimize this, we use memoization.
Memoization is a technique where we store the results of expensive function calls and reuse the stored result when the same inputs occur again. In our TSP problem, the state is defined by (curr, mask). We can use a 2D array, memo[curr][mask], to store the results of tsp(curr, mask). Before computing tsp(curr, mask), we check if memo[curr][mask] already has a computed value. If it does, we directly return the stored value; otherwise, we compute it, store it in memo[curr][mask], and then return it. We initialize the memo table with a value (like -1) to indicate that the subproblem has not yet been computed.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int totalCost(int mask, int curr, int n, vector<vector<int>>& cost, vector<vector<int>>& memo) {
if (mask == ((1 << n) - 1)) {
return cost[curr][0];
}
if (memo[curr][mask] != -1) {
return memo[curr][mask];
}
int ans = INT_MAX;
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) == 0) {
ans = min(ans, cost[curr][i] + totalCost((mask | (1 << i)), i, n, cost, memo));
}
}
return memo[curr][mask] = ans;
}
int tsp(vector<vector<int>>& cost) {
int n = cost.size();
vector<vector<int>> memo(n, vector<int>(1 << n, -1));
return totalCost(1, 0, n, cost, memo);
}
int main() {
vector<vector<int>> cost = {{0, 10, 15, 20},
{10, 0, 35, 25},
{15, 35, 0, 30},
{20, 25, 30, 0}};
int res = tsp(cost);
cout << res << endl;
return 0;
}import java.util.Arrays;
class GfG {
static int totalCost(int mask, int curr, int n, int[][] cost, int[][] memo) {
if (mask == ((1 << n) - 1)) {
return cost[curr][0];
}
if (memo[curr][mask] != -1) {
return memo[curr][mask];
}
int ans = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) == 0) {
ans = Math.min(ans, cost[curr][i] + totalCost(mask | (1 << i), i, n, cost, memo));
}
}
return memo[curr][mask] = ans;
}
static int tsp(int[][] cost) {
int n = cost.length;
int[][] memo = new int[n][1 << n];
for (int i = 0; i < n; i++) {
Arrays.fill(memo[i], -1);
}
return totalCost(1, 0, n, cost, memo);
}
public static void main(String[] args) {
int[][] cost = {{0, 10, 15, 20},
{10, 0, 35, 25},
{15, 35, 0, 30},
{20, 25, 30, 0}};
int res = tsp(cost);
System.out.println(res);
}
}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)using System;
using System.Collections.Generic;
class GfG {
static int totalCost(int mask, int curr, int n, List<List<int>> cost, List<List<int>> memo) {
if (mask == ((1 << n) - 1)) {
return cost[curr][0];
}
if (memo[curr][mask] != -1) {
return memo[curr][mask];
}
int ans = int.MaxValue;
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) == 0) {
ans = Math.Min(ans, cost[curr][i] + totalCost(mask | (1 << i), i, n, cost, memo));
}
}
memo[curr][mask] = ans;
return ans;
}
static int tsp(List<List<int>> cost) {
int n = cost.Count;
List<List<int>> memo = new List<List<int>>();
for (int i = 0; i < n; i++) {
List<int> row = new List<int>();
for (int j = 0; j < (1 << n); j++) {
row.Add(-1);
}
memo.Add(row);
}
return totalCost(1, 0, n, cost, memo);
}
static void Main() {
List<List<int>> cost = new List<List<int>>() {
new List<int> {0, 10, 15, 20},
new List<int> {10, 0, 35, 25},
new List<int> {15, 35, 0, 30},
new List<int> { 20, 25, 30, 0 }
};
int res = tsp(cost);
Console.WriteLine(res);
}
}function totalCost(mask, curr, n, cost, memo) {
if (mask === ((1 << n) - 1)) {
return cost[curr][0];
}
if (memo[curr][mask] !== -1) {
return memo[curr][mask];
}
let ans = Number.MAX_VALUE;
for (let i = 0; i < n; i++) {
if ((mask & (1 << i)) === 0) {
ans = Math.min(ans, cost[curr][i] + totalCost(mask | (1 << i), i, n, cost, memo));
}
}
memo[curr][mask] = ans;
return ans;
}
function tsp(cost) {
const n = cost.length;
const memo = Array.from({ length: n }, () => Array((1 << n)).fill(-1));
return totalCost(1, 0, n, cost, memo);
}
const cost = [
[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30],
[20, 25, 30, 0]
];
const res = tsp(cost);
console.log(res);Time and Space Complexity
The time complexity of the dynamic programming solution with memoization is O(n2 2n). This is because we have n 2n possible states (combinations of curr and mask), and for each state, we iterate through at most ‘n’ cities in the loop.
The space complexity is O(n * 2n) to store the memoization table.
While still exponential, this is a significant improvement over the O(n!) complexity of the brute-force approach, making it feasible for a larger number of cities.
Real-World Applications of TSP
Despite being a theoretical problem, the Traveling Salesman Problem has numerous applications in the real world, especially in optimization and logistics:
- Logistics and Transportation: Optimizing delivery routes for trucks, planning routes for airplanes, and scheduling transportation networks.
- Manufacturing: Optimizing the path of a robot arm in a manufacturing process to minimize time and material waste.
- DNA Sequencing: Finding the most efficient way to assemble DNA fragments.
- Circuit Board Drilling: Determining the shortest path for drilling holes on a circuit board.
Conclusion
The Travel Salesman Problem is a fascinating problem that showcases the power of dynamic programming. By using recursion, bitmasking, and memoization, we can significantly reduce the computational complexity compared to brute-force methods. While TSP remains NP-hard, dynamic programming provides a practical and efficient solution for a reasonable number of cities, making it a valuable tool for various optimization challenges across different industries.
This exploration of the Travel Salesman Problem and its dynamic programming solution provides a solid foundation for understanding and tackling complex algorithmic problems. Further exploration into approximation algorithms and heuristics can provide solutions for even larger instances of the TSP when exact solutions become computationally prohibitive.
