Travelling Salesman Problem
The Travelling Salesman Problem (TSP) involves finding the shortest possible route that visits each city exactly once and returns to the origin city. In this blog post, we’ll solve the TSP using the Held-Karp algorithm, which is based on dynamic programming.
We’ve already discussed a O(n2) time complexity greedy solution for the travelling salesman problem in this post – Travelling Salesman Problem using Nearest Neighbour Algorithm
Held-Karp Algorithm
The Held-Karp algorithm is an efficient dynamic programming approach for solving the Travelling Salesman Problem (TSP). It works by breaking down the problem into smaller subproblems and solving them recursively. The algorithm builds up a table to store the optimal cost of visiting subsets of cities, gradually building up to the optimal solution for the entire set of cities.
Some important points regarding Held-Karp Algorithm:
- Optimal Solution: It guarantees to find the optimal solution to the TSP, i.e., the shortest possible tour that visits each city exactly once and returns to the starting city.
- Complexity: The time complexity of the Held-Karp algorithm is O(n2 * 2n), where n is the number of cities. While this is exponential, it is more efficient than brute-force search for moderate-sized instances of the problem. Since, brute-force involves calculating
n!permutations. - Memory Usage: It requires storing a table of size O(2n * n), which can be memory-intensive for large values of n.
Approach
1. Initialization: Initialize a dynamic programming table dp[][] with dimensions 2n × n, where n is the number of cities. The table stores the minimum cost of visiting a subset of cities, ending at a specific city.
2. Base Case: Set dp[{1}][0] = 0, where {1} represents the set containing only the starting city 0. Here, dp[{1}][0] represents the minimum cost of visiting all the vertices in set {1} once and ending the tour at vertex 0.
3. Dynamic Programming Iterations: For each subset S of cities (with total number of subsets be 2n) containing the starting city 0 and each destination city j in S, compute the minimum cost of reaching j from any city i in S, where i != j.
4. Optimal Substructure: The optimal cost of visiting a subset S of cities ending at j can be calculated as: dp[S][j] = min(dp[S][j], dp[S-{j}][i] + graph[i][j]), where {j} is the set containing only city j, and graph[i][j] represents the cost of traveling from city i to city j.
Here, dp[S-{j}][i] represents the minimum cost of visiting all the vertices in the set S - {j} once and ending the tour at vertex i.
5. Solution: The minimum cost of visiting all cities and returning to the starting city (0) is the minimum value of dp[{all cities}][j] + graph[j][0] for all destination cities j.
6. Path: To reconstruct the optimal tour, backtrace through the table from the final solution, selecting the cities that contribute to the minimum cost.
Note: We’ll be using Bitmasking for iterating over all the subsets of cities. Bitmasking is discussed in detail in this post – Bitmasking. Here’re some key points regarding the step – “Dynamic Programming Iterations”:
- For each iteration, we’ll be considering only those vertices that are part of the current subset, represented by the variable
mask. - At any iteration,
dp[mask][j]represents the minimum cost of visiting all vertices in the subset represented bymask, with the last visited vertex beingvertex j. - For each combination of
iandj, we check if bothvertices i and jare in the current subset, using:(mask & (1 << i)),(mask & (1 << j))
Ifvertex i or vertex jis not in the current subset, we skip to the next iteration. Otherwise, we update the dynamic programming table entrydp[mask][j]. - Updating the table entry requires considering the cost of reaching
vertex jfromvertex iand the cost of traversing currentsubset (mask)excluding thevertex j, ending atvertex i(ie. {mask - {j}}, represented by:.mask ^ (1 << j))
Here’s the required code:dp[mask][j] = min(dp[mask][j], dp[mask ^ (1 << j)][i] + graph[i][j]) - The use of bitwise
XOR (^)helps removevertex jfrom the current subsetmask.
Example
The following graph and Adjacency Matrix G represent distances between cities, where graph[i][j] denotes the distance from city i to city j.
Let the tour start at vertex 1. The path P has edge <1, k> for some k ∈ V (set of vertices of Graph G) - {1}. And then the path from k to 1 is: going through all vertices in V - {1, k} exactly once.
Let g(i, s) = length of shortest path from node i and going through all vertices in subset s (subset of vertices of graph G) and terminating at vertex 1. Thus, g(i, V - {1}) is the optimal length tour such that:
g(1, V - {1}) = min (2 <= j <= n) {E1j + g(j, V - {1, j})}, where
E1j is the length of the edge from node 1 to node j.
Generally we need to solve g(1, V - {1}), such that at a time,
for any i ∉ s (subset of vertices) and j ∈ s
g(i, s) = min (j ∈ s) {Eij + g(j, s - {1, j})}
Let's evaluate the TSP path for the above graph G in the bottom-up manner (using g(i, s), subset s and Eij):
|s| = 0 (empty subset)
g(2, φ) = E21 = 5,
g(3, φ) = E31 = 6,
g(4, φ) = E41 = 8
|s| = 1 (subset of size 1)
g(2, {3}) = E23 + g(3, φ) = 9 + 6 = 15,
g(2, {4}) = E24 + g(4, φ) = 10 + 8 = 18,
g(3, {2}) = E32 + g(2, φ) = 13 + 5 = 18,
g(3, {4}) = E34 + g(4, φ) = 12 + 8 = 20,
g(4, {2}) = E42 + g(2, φ) = 8 + 5 = 13,
g(4, {3}) = E43 + g(3, φ) = 9 + 6 = 15,
|s| = 2 (subset of size 2)
g(2, {3, 4}) = min { E23 + g(3, {4}),
E24 + g(4, {3})}
= min {9+20, 10+15} = 25
g(3, {2, 4}) = min { E32 + g(2, {4}),
E34 + g(4, {2})}
= min {13+18, 12+13} = 25
g(4, {2, 3}) = min { E42 + g(2, {3}),
E43 + g(3, {2})}
= min {8+15, 9+18} = 23
Final tour length:
g(1, {2, 3, 4}) = min { E12 + g(2, {3, 4}),
E13 + g(3, {2, 4}),
E14 + g(4, {2, 3})}
= min {35, 40, 43}
= 35
Hence, the optimal tour length is 35.
To reconstruct the optimal path, backtrace through the final solution, selecting the vertices that contributed to the minimum cost during the path evaluation process:
J(1, {2, 3, 4}): 2
J(2, {3, 4}): 4
J(4, {3}): 3
Hence, the resulting tour is:
1 -> 2 -> 4 -> 3 -> 1
Pseudocode
function tspHeldKarp(graph):
n = size(graph)
dp[2n][n]
dp[{1}][0] = 0
for each subset S of size k containing the starting city 0:
for each destination city j in S:
if j != 0:
dp[S][j] = INF
for each city i in S, i != j:
dp[S][j] = min(dp[S][j], dp[S-{j}][i] + graph[i][j])
minCost = INF
for each destination city j:
if j != 0:
minCost = min(minCost, dp[all cities][j] + graph[j][0])
return minCost
Code Implementation
//
// main.cpp
// Travelling Salesman Problem Held-Karp
//
// Created by Himanshu on 01/03/24.
//
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
const int MAX_EDGE = 25; // Maximum possible value of an edge
const int INF = INT_MAX - MAX_EDGE; // To prevent integer overflow
int tspHeldKarp(vector<vector<int>>& graph, vector<vector<int>>& path) {
int n = (int) graph.size();
vector<vector<int>> dp(1 << n, vector<int>(n, INF));
dp[1][0] = 0;
for (int mask = 1; mask < (1 << n); mask++) {
for (int i = 0; i < n; i++) {
if (!(mask & (1 << i))) continue;
for (int j = 0; j < n; j++) {
if (!(mask & (1 << j)) || i == j) continue;
if (dp[mask ^ (1 << j)][i] + graph[i][j] < dp[mask][j]) {
dp[mask][j] = dp[mask ^ (1 << j)][i] + graph[i][j];
path[mask][j] = i; // Store the parent node for constructing the path
}
}
}
}
int minCost = INF;
int lastNode = -1;
for (int i = 1; i < n; i++) {
if (dp[(1 << n) - 1][i] + graph[i][0] < minCost) {
minCost = dp[(1 << n) - 1][i] + graph[i][0];
lastNode = i;
}
}
// Reconstruct the path
vector<int> tour;
int mask = (1 << n) - 1;
tour.push_back(0); // Add the starting city to the path
while (lastNode != 0) {
tour.push_back(lastNode);
int prevNode = path[mask][lastNode];
mask ^= (1 << lastNode);
lastNode = prevNode;
}
tour.push_back(0); // Add the starting city to complete the tour
// Print the path
cout << "Path: ";
for (int i = (int) tour.size() - 1; i >= 0; i--) {
cout << tour[i];
if (i > 0) {
cout << " -> ";
}
}
cout << endl;
return minCost;
}
int main() {
vector<vector<int>> graph = {
{0, 10, 15, 20},
{5, 0, 9, 10},
{6, 13, 0, 12},
{8, 8, 9, 0}
};
int n = (int) graph.size();
vector<vector<int>> path(1 << n, vector<int>(n, -1)); // To store the parent nodes for path reconstruction
int minCost = tspHeldKarp(graph, path);
cout << "Minimum Cost: " << minCost << endl;
return 0;
}
Output
Path: 0 -> 1 -> 3 -> 2 -> 0
Minimum Cost: 35
The output is the sequence of cities visited (with 0-based indexing), representing the shortest possible route that visits each city exactly once and returns to the original city.
The time complexity of the Held-Karp algorithm is O(n2 * 2n), where n is the number of cities.
Explanation:
Dynamic Programming Table Initialization: Initializing the dynamic programming table requires O(n * 2n) operations, as it involves creating a table of size 2n x n where each cell is initialized to infinity.
Dynamic Programming Iterations: For each subset S of cities, we compute the minimum cost of reaching destination city j from any city i in S where i != j. This process requires iterating over all subsets of cities and all pair of cities within each subset, resulting in a total time complexity of O(n2 * 2n).
Minimum Cost Calculation: After filling the dynamic programming table, we find the minimum cost tour by iterating over all possible last cities in the tour, which takes O(n) time.
Path Reconstruction: Reconstructing the minimum cost tour also takes O(n) time.
The overall time complexity of the algorithm is thus O(n2 * 2n).
Reference: Programming Interview – Travelling Salesman Problem