user
Held–Karp Algorithm Problem Description

The Held–Karp algorithm is a classic dynamic programming algorithm used to solve the Traveling Salesperson Problem (TSP). While the TSP is an NP-hard problem, the Held–Karp algorithm provides an exact solution in exponential time, which is considerably more efficient than a brute-force search for small to moderately sized inputs.

Problem Statement
:   Traveling Salesperson Problem

Given a set of **Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest\_v1/":): {\displaystyle n}**
cities and a matrix 

C
{\displaystyle {\displaystyle C}}
 where 

C

i
j
{\displaystyle {\displaystyle C\_{ij}}}
 represents the cost (or distance) of traveling from city 

i
{\displaystyle {\displaystyle i}}
 to city **Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest\_v1/":): {\displaystyle j}**
, the Traveling Salesperson Problem (TSP) requires finding the minimum-cost route that visits each city exactly once and returns to the starting city.

Let the cities be indexed from 

0
{\displaystyle {\displaystyle 0}}
 to 

n
−
1
{\displaystyle {\displaystyle n-1}}
. We seek a permutation of cities 

(

v

0
,

v

1
,
…
,

v

n
−
1
)
{\displaystyle {\displaystyle (v\_{0},v\_{1},\dots ,v\_{n-1})}}
, where 

v

0
{\displaystyle {\displaystyle v\_{0}}}
 is the starting city (e.g., city 0), such that the total cost of the cycle

Total Cost
=

∑

i
=
0

n
−
2

C


v

i
,

v

i
+
1
+

C


v

n
−
1
,

v

0
{\displaystyle {\displaystyle {\text{Total Cost}}=\sum \_{i=0}^{n-2}C\_{v\_{i},v\_{i+1}}+C\_{v\_{n-1},v\_{0}}}}

is minimized.

Algorithm Overview

The Held–Karp algorithm employs dynamic programming to solve the TSP. It breaks down the problem into smaller subproblems defined by the set of cities visited so far and the current location of the salesperson.

Dynamic Programming State

Let 

d
p
(
S
,
j
)
{\displaystyle {\displaystyle dp(S,j)}}
 represent the minimum cost of a path that starts at a designated city (typically city 0), visits all cities in the set 

S
{\displaystyle {\displaystyle S}}
 exactly once, and ends at city **Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest\_v1/":): {\displaystyle j}**
, where 

j
∈
S
{\displaystyle {\displaystyle j\in S}}
 and the starting city **Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest\_v1/":): {\displaystyle 0 \in S}**
.

Here, 

S
{\displaystyle {\displaystyle S}}
 is a subset of the set of all cities 

V
=

0
,
1
,
…
,
n
−
1
{\displaystyle {\displaystyle V={0,1,\dots ,n-1}}}
, and **Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest\_v1/":): {\displaystyle j}**
is a city in the subset 

S
{\displaystyle {\displaystyle S}}
. Note that we fix the starting city as 0 and require **Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest\_v1/":): {\displaystyle 0 \in S}**
for any state.

Base Case

The base case for the dynamic programming is a path starting at city 0 and going directly to another city **Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest\_v1/":): {\displaystyle j}**
.
For all cities 

j
∈

1
,
2
,
…
,
n
−
1
{\displaystyle {\displaystyle j\in {1,2,\dots ,n-1}}}
:

d
p
(
{
0
,
j
}
,
j
)
=

C

0
,
j
{\displaystyle {\displaystyle dp(\{0,j\},j)=C\_{0,j}}}

This represents the shortest path from city 0 visiting only cities 0 and **Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest\_v1/":): {\displaystyle j}**
, ending at city **Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest\_v1/":): {\displaystyle j}**
.

Recurrence Relation

To compute 

d
p
(
S
,
j
)
{\displaystyle {\displaystyle dp(S,j)}}
 for a subset 

S
{\displaystyle {\displaystyle S}}
 with 

|
S

|
>
2
{\displaystyle {\displaystyle |S|>2}}
 and 

j
≠
0
{\displaystyle {\displaystyle j\neq 0}}
, the path must have arrived at city **Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest\_v1/":): {\displaystyle j}**
from some city 

i
{\displaystyle {\displaystyle i}}
 where 

i
∈
S
{\displaystyle {\displaystyle i\in S}}
 and **Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest\_v1/":): {\displaystyle i \ne j}**
. The path leading to city 

i
{\displaystyle {\displaystyle i}}
 must have visited all cities in the subset 

S
∖

j
{\displaystyle {\displaystyle S\setminus {j}}}
 and ended at 

i
{\displaystyle {\displaystyle i}}
. The cost of this path is 

d
p
(
S
∖

j
,
i
)
{\displaystyle {\displaystyle dp(S\setminus {j},i)}}
. Therefore, the minimum cost to reach city **Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest\_v1/":): {\displaystyle j}**
having visited all cities in 

S
{\displaystyle {\displaystyle S}}
 is the minimum cost over all possible preceding cities 

i
{\displaystyle {\displaystyle i}}
 plus the cost of the final leg from 

i
{\displaystyle {\displaystyle i}}
 to **Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest\_v1/":): {\displaystyle j}**
.

For **Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest\_v1/":): {\displaystyle S \subseteq V}**
with 

|
S

|
>
2
{\displaystyle {\displaystyle |S|>2}}
, **Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest\_v1/":): {\displaystyle 0 \in S}**
, and 

j
∈
S
,
j
≠
0
{\displaystyle {\displaystyle j\in S,j\neq 0}}
:

d
p
(
S
,
j
)
=

min

i
∈
S
,
i
≠
j
{
d
p
(
S
∖
{
j
}
,
i
)
+

C

i
,
j
}
{\displaystyle {\displaystyle dp(S,j)=\min \_{i\in S,i\neq j}\{dp(S\setminus \{j\},i)+C\_{i,j}\}}}

The algorithm computes these values iteratively, starting with subsets of size 2, then size 3, and so on, up to size **Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest\_v1/":): {\displaystyle n}**
.

Final Solution

The final goal is to find the shortest Hamiltonian cycle starting and ending at city 0. This means we need to find the shortest path that visits all cities in **Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest\_v1/":): {\displaystyle V}**
, ends at some city 

j
≠
0
{\displaystyle {\displaystyle j\neq 0}}
, and then add the cost of returning from **Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest\_v1/":): {\displaystyle j}**
to 0.

The minimum total cost for the TSP is:

min

j
∈
{
1
,
…
,
n
−
1
}
{
d
p
(
V
,
j
)
+

C

j
,
0
}
{\displaystyle {\displaystyle \min \_{j\in \{1,\dots ,n-1\}}\{dp(V,j)+C\_{j,0}\}}}

where **Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest\_v1/":): {\displaystyle V}**
is the set of all **Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest\_v1/":): {\displaystyle n}**
cities.

Complexity

The time complexity of the Held–Karp algorithm is determined by the number of states and the cost to compute each state.

Number of states 

(
S
,
j
)
{\displaystyle {\displaystyle (S,j)}}
: There are 

2

n
−
1
{\displaystyle {\displaystyle 2^{n-1}}}
 possible subsets 

S
{\displaystyle {\displaystyle S}}
 that contain city 0. For each subset 

S
{\displaystyle {\displaystyle S}}
 with 

k
{\displaystyle {\displaystyle k}}
 cities, there are **Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest\_v1/":): {\displaystyle k-1}**
possible ending cities 

j
≠
0
{\displaystyle {\displaystyle j\neq 0}}
. The total number of states is bounded by 

O
(
n

2

n
)
{\displaystyle {\displaystyle O(n2^{n})}}
.

Transition cost: To compute 

d
p
(
S
,
j
)
{\displaystyle {\displaystyle dp(S,j)}}
, we iterate through all possible previous cities 

i
∈
S
∖

j
{\displaystyle {\displaystyle i\in S\setminus {j}}}
. There are at most 

n
−
1
{\displaystyle {\displaystyle n-1}}
 such cities.

Overall time complexity: 

O
(
n
⋅

2

n
⋅
n
)
=
O
(

n

2

2

n
)
{\displaystyle {\displaystyle O(n\cdot 2^{n}\cdot n)=O(n^{2}2^{n})}}
.

The space complexity required to store the DP table 

d
p
(
S
,
j
)
{\displaystyle {\displaystyle dp(S,j)}}
 is proportional to the number of states, which is 

O
(
n

2

n
)
{\displaystyle {\displaystyle O(n2^{n})}}
.

While exponential, this is significantly better than the 

O
(
n
!
)
{\displaystyle {\displaystyle O(n!)}}
 complexity of brute-force enumeration of all possible permutations.
assistant
**Translation of**: Go

```
# 20250515 Raku programming solution

class Result { has Int ( $.Cost, @.Tour ) }

# heldKarp solves the Traveling Salesman Problem using the Held–Karp algorithm (O(n^2·2^n)).
# @dist is an n×n matrix of pairwise distances.
# Returns a Result{minimumCost, tour}, where tour is a sequence of city indices
# starting and ending at 0.
sub heldKarp(@dist) {
   my $subsetCount = 2 ** ( my $n = @dist.elems );
   # dp[mask][j] = minimum cost to start at 0, visit exactly the cities in mask, and end at j
   my (@dp,@parents) := [[Inf xx $n] xx $subsetCount], [[-1 xx $n] xx $subsetCount];
   @dp[1][0] = 0; # Base case: mask = 1<<0, at city 0, cost = 0

   for ^$subsetCount -> $mask { # Build up dp table       
      next if $mask +& 1 == 0; # City 0 must always be included
      for ^$n -> $j {
         next if $mask +& (1 +< $j) == 0;
         my $prevMask = $mask +^ (1 +< $j);
         for ^$n -> $k {
            next if $prevMask +& (1 +< $k) == 0;
            if ( my $cost = @dp[$prevMask;$k] + @dist[$k;$j] ) < @dp[$mask;$j] {
               ( @dp[$mask][$j], @parents[$mask][$j] ) = $cost, $k
            }
         }
      }
   }

   # Complete the tour by returning to city 0
   my ($fullMask, $minCost, $lastCity) = $subsetCount - 1, Inf, 0; 

   for ^$n -> $j {
      if ( my $cost = @dp[$fullMask;$j] + @dist[$j;0] ) < $minCost {
         ( $minCost, $lastCity ) = $cost, $j
      }
   }

   # Reconstruct the optimal tour
   my ($mask, $curr, @tour) = $fullMask, $lastCity, ($lastCity); 

   while @tour[0] != 0 {
      my $prev = @parents[$mask;$curr];
      $mask +^= 1 +< $curr;
      $curr = $prev;
      @tour.unshift($curr);
   }
   @tour.push(0); # append the start city, then return to start

   return Result.new(Cost => $minCost, Tour => @tour)
}

# Test case: 4 cities with symmetric distances
my @dist = [ <0 2 9 10>, <1 0 6 4>, <15 7 0 8>, <6 3 12 0> ]; 

given heldKarp(@dist) { say "Minimum tour cost: { .Cost }\nTour: { .Tour }" }

```

You may Attempt This Online!