Travelling Salesman Problem
Problem Statement
Given a set of cities and the distances between every pair of cities, find the shortest possible route that visits every city exactly once and returns to the starting city.
Example:
- Input:
dist[][] = {{0, 10, 15, 20}, {10, 0, 35, 25}, {15, 35, 0, 30}, {20, 25, 30, 0}} - Output:
80(Path: 0 → 1 → 3 → 2 → 0)
Noob-Friendly Explanation
Imagine you're a pizza delivery person. You have a list of houses to deliver pizza to, and you know the distance between every pair of houses. You start from the pizza shop, visit every house exactly once, and come back to the shop. You want to drive the least distance possible.
The brute force way is to try every possible order of visiting houses and pick the shortest one. But that takes forever for many houses! The smarter way uses dynamic programming to remember results so you don't repeat work.
Approach 1: Brute Force
Intuition
Try every possible permutation of cities. For each permutation, calculate the total distance of the tour (including returning to the start). Return the minimum distance found.
Algorithm
- Fix the starting city (city 0).
- Generate all permutations of the remaining cities.
- For each permutation, compute the round-trip distance.
- Track and return the minimum distance.
import java.util.*;
public class TSPBruteForce {
static int n;
static int[][] dist;
static int minCost;
public static int tsp(int[][] distance) {
n = distance.length;
dist = distance;
minCost = Integer.MAX_VALUE;
List<Integer> cities = new ArrayList<>();
for (int i = 1; i < n; i++) {
cities.add(i);
}
permute(cities, 0);
return minCost;
}
static void permute(List<Integer> cities, int start) {
if (start == cities.size()) {
int cost = 0;
int prev = 0;
for (int city : cities) {
cost += dist[prev][city];
prev = city;
}
cost += dist[prev][0]; // return to start
minCost = Math.min(minCost, cost);
return;
}
for (int i = start; i < cities.size(); i++) {
Collections.swap(cities, start, i);
permute(cities, start + 1);
Collections.swap(cities, start, i);
}
}
public static void main(String[] args) {
int[][] distance = {
{0, 10, 15, 20},
{10, 0, 35, 25},
{15, 35, 0, 30},
{20, 25, 30, 0}
};
System.out.println("Minimum cost: " + tsp(distance));
}
}Complexity Analysis
- Time Complexity: O(N!) - we try all permutations of N-1 cities
- Space Complexity: O(N) - recursion stack depth
Approach 2: Optimal (Bitmask DP)
Intuition
Use dynamic programming with bitmasks. A bitmask represents which cities have been visited. dp[mask][i] stores the minimum cost to reach city i having visited exactly the cities in mask. This avoids recomputing overlapping subproblems.
Algorithm
- Create a DP table
dp[2^N][N]initialized to infinity. - Start from city 0:
dp[1][0] = 0(only city 0 visited, cost = 0). - For each bitmask and each city
iin that mask, try extending to unvisited cityj. - The answer is the minimum of
dp[(1<<N)-1][i] + dist[i][0]for alli.
import java.util.*;
public class TSPOptimal {
public static int tsp(int[][] dist) {
int n = dist.length;
int allVisited = (1 << n) - 1;
int[][] dp = new int[1 << n][n];
for (int[] row : dp) {
Arrays.fill(row, Integer.MAX_VALUE / 2);
}
dp[1][0] = 0; // start at city 0, only city 0 visited
for (int mask = 1; mask <= allVisited; mask++) {
for (int u = 0; u < n; u++) {
if ((mask & (1 << u)) == 0) continue; // u not in mask
if (dp[mask][u] == Integer.MAX_VALUE / 2) continue;
for (int v = 0; v < n; v++) {
if ((mask & (1 << v)) != 0) continue; // v already visited
int newMask = mask | (1 << v);
dp[newMask][v] = Math.min(dp[newMask][v], dp[mask][u] + dist[u][v]);
}
}
}
int result = Integer.MAX_VALUE;
for (int i = 1; i < n; i++) {
result = Math.min(result, dp[allVisited][i] + dist[i][0]);
}
return result;
}
public static void main(String[] args) {
int[][] dist = {
{0, 10, 15, 20},
{10, 0, 35, 25},
{15, 35, 0, 30},
{20, 25, 30, 0}
};
System.out.println("Minimum cost: " + tsp(dist));
}
}Complexity Analysis
- Time Complexity: O(N² * 2^N) - for each of 2^N masks, we try N cities and N transitions
- Space Complexity: O(N * 2^N) - for the DP table