**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(n^{2}) 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(n^{2}* 2^{n}), 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(2^{n}* n), which can be memory-intensive for large values of n.

**Approach**

1. Initialization: Initialize a dynamic programming table dp[][] with dimensions 2^{n}× 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 2^{n}) 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 by`mask`

, with the last visited vertex being`vertex j`

. - For each combination of
`i`

and`j`

, we check if both`vertices i and j`

are in the current subset, using:`(mask & (1 << i))`

,`(mask & (1 << j))`

If`vertex i or vertex j`

is not in the current subset, we skip to the next iteration. Otherwise, we update the dynamic programming table entry`dp[mask][j]`

. - Updating the table entry requires considering the cost of reaching
`vertex j`

from`vertex i`

and the cost of traversing current`subset (mask)`

excluding the`vertex j`

, ending at`vertex 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 remove`vertex j`

from the current subset`mask`

.

**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) {E_{1j}+ g(j, V - {1, j})}, where

E_{1j}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) {E_{ij}+ 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 E_{ij}):

|s| = 0 (empty subset)

g(2, φ) = E_{21}= 5,

g(3, φ) = E_{31}= 6,

g(4, φ) = E_{41}= 8

|s| = 1 (subset of size 1)

g(2, {3}) = E_{23}+ g(3, φ) = 9 + 6 = 15,

g(2, {4}) = E_{24}+ g(4, φ) = 10 + 8 = 18,

g(3, {2}) = E_{32}+ g(2, φ) = 13 + 5 = 18,

g(3, {4}) = E_{34}+ g(4, φ) = 12 + 8 = 20,

g(4, {2}) = E_{42}+ g(2, φ) = 8 + 5 = 13,

g(4, {3}) = E_{43}+ g(3, φ) = 9 + 6 = 15,

|s| = 2 (subset of size 2)

g(2, {3, 4}) = min { E_{23}+ g(3, {4}),

E_{24}+ g(4, {3})}

= min {9+20, 10+15} = 25

g(3, {2, 4}) = min { E_{32}+ g(2, {4}),

E_{34}+ g(4, {2})}

= min {13+18, 12+13} = 25

g(4, {2, 3}) = min { E_{42}+ g(2, {3}),

E_{43}+ g(3, {2})}

= min {8+15, 9+18} = 23

Final tour length:

g(1, {2, 3, 4}) = min { E_{12}+ g(2, {3, 4}),

E_{13}+ g(3, {2, 4}),

E_{14}+ 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[2^{n}][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(n^{2} * 2^{n}), where n is the number of cities.

**Explanation:**

**Dynamic Programming Table Initialization:** Initializing the dynamic programming table requires O(n * 2^{n}) operations, as it involves creating a table of size 2^{n} 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(n^{2} * 2^{n}).

**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(n ^{2} * 2^{n})**.

**Reference:** Programming Interview – Travelling Salesman Problem