Held–Karp algorithm
You are encouraged to solve this task according to the task description, using any language you may know.
- 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 cities and a matrix where represents the cost (or distance) of traveling from city to city , 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 to . We seek a permutation of cities , where is the starting city (e.g., city 0), such that the total cost of the cycle
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 represent the minimum cost of a path that starts at a designated city (typically city 0), visits all cities in the set exactly once, and ends at city , where and the starting city .
Here, is a subset of the set of all cities , and is a city in the subset . Note that we fix the starting city as 0 and require 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 . For all cities :
This represents the shortest path from city 0 visiting only cities 0 and , ending at city .
- Recurrence Relation
To compute for a subset with and , the path must have arrived at city from some city where and . The path leading to city must have visited all cities in the subset and ended at . The cost of this path is . Therefore, the minimum cost to reach city having visited all cities in is the minimum cost over all possible preceding cities plus the cost of the final leg from to .
For with , , and :
The algorithm computes these values iteratively, starting with subsets of size 2, then size 3, and so on, up to size .
- 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 , ends at some city , and then add the cost of returning from to 0.
The minimum total cost for the TSP is:
where is the set of all 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 : There are possible subsets that contain city 0. For each subset with cities, there are possible ending cities . The total number of states is bounded by .
Transition cost: To compute , we iterate through all possible previous cities . There are at most such cities.
Overall time complexity: .
The space complexity required to store the DP table is proportional to the number of states, which is .
While exponential, this is significantly better than the complexity of brute-force enumeration of all possible permutations.
ALGOL 68
BEGIN # Solve the travelling salesman problem using the Held–Karp algorithm #
# translated from the FreeBASIC sample #
REAL inf = max real;
# utility operators to allow bit manipulation on integers #
OP AND = ( INT a, b )INT: ABS ( BIN a AND BIN b );
OP SHL = ( INT v, sh )INT: ABS ( BIN v SHL sh );
OP XOR = ( INT a, b )INT: ABS ( BIN a XOR BIN b );
PRIO XORAB = 1;
OP XORAB = ( REF INT a, INT b )REF INT: a := a XOR b;
# returns the minimum cost tour using the Held-Karp algorithm #
# min cost is set to the minimum cost #
PROC held karp = ( [,]REAL dist, REF REAL min cost )[]INT:
IF LWB dist /= 0 THEN
print( ( "LWB dist must be 0", newline ) );
min cost := inf;
[ 0 : -1 ]INT no values;
no values
ELSE
INT n = 1 UPB dist + 1;
INT num mask = 1 SHL n;
# dp[mask,j] = minimum cost to reach subset 'mask' ending at j #
[ 0 : num mask - 1, 0 : n - 1 ]REAL dp;
# parent[mask,j] = previous node before j in optimal path for #
# (mask, j) #
[ 0 : num mask - 1, 0 : n - 1 ]INT parent;
FOR i FROM 0 TO num mask - 1 DO # Initialize dp with infinity #
FOR j FROM 0 TO n - 1 DO
dp[ i, j ] := inf;
parent[ i, j ] := -1
OD
OD;
# Base case: start at node 0, mask = 1<<0 #
dp[ 1, 0 ] := 0;
# Iterate over all subsets that include node 0 #
FOR mask TO num mask - 1 DO
IF ODD mask THEN # We always require the tour to start at #
INT two to j := 1; # node 0 so mask must include 1 #
FOR j TO n - 1 DO
two to j *:= 2;
IF ( mask XOR two to j ) /= 0 THEN # j is in subset #
INT prev mask = mask XOR two to j;
# Try all possibilities of coming to j from #
# some k in prev mask #
INT two to k := 1;
FOR k FROM 0 TO n - 1 DO
IF ( prev mask AND two to k ) /= 0 THEN
IF REAL cost = dp[ prev mask, k ] + dist[ k, j ];
cost < dp[ mask, j ]
THEN dp[ mask, j ] := cost;
parent[ mask, j ] := k
FI
FI;
two to k *:= 2
OD
FI
OD
FI
OD;
# Close the tour: return to node 0 #
INT full mask = ( 1 SHL n ) - 1;
INT last := -1;
min cost := inf;
FOR j TO n - 1 DO
IF REAL cost = dp[ full mask, j ] + dist[ j, 0 ];
cost < min cost
THEN min cost := cost;
last := j
FI
OD;
# Reconstruct path #
[ 0 : n ]INT path; # n + 1 elements for the complete tour #
path[ n ] := 0; # End at node 0 #
INT path index := n - 1;
INT path mask := full mask;
INT curr := last;
WHILE curr /= -1 AND curr /= 0 DO
path[ path index ] := curr;
path index -:= 1;
INT prev = parent[ path mask, curr ];
path mask XORAB ( 1 SHL curr );
curr := prev
OD;
path[ path index ] := 0; # Start at node 0 #
path
FI # held karp # ;
BEGIN # Example test case: 4 cities, symmetric distance matrix #
[,]REAL dist matrix = ( ( 0, 2, 9, 10 )
, ( 1, 0, 6, 4 )
, ( 15, 7, 0, 8 )
, ( 6, 3, 12, 0 )
);
REAL min cost := inf;
# For a 4-city problem, the path has 5 elements #
# (including the return to the start) #
[]INT path = held karp( dist matrix[ AT 0, AT 0 ], min cost );
print( ( "Minimum tour cost: ", fixed( min cost, 0, 4 ), newline ) );
print( ( "Tour: " ) );
FOR i FROM 0 TO UPB path - 1 DO
print( ( whole( path[ i ], 0 ), " -> " ) )
OD;
print( ( whole( path[ UPB path ], 0 ), newline ) )
END
END- Output:
Minimum tour cost: 21.0000 Tour: 0 -> 2 -> 3 -> 1 -> 0
Ballerina
import ballerina/io;
# Solve the Traveling Salesman Problem using the Held–Karp algorithm.
#
# + dist - a 2D square matrix (list of lists) of pairwise distances.
# + return - [min_cost, tour] where tour is a list of node indices, starting and ending at 0.
function heldKarp(int[][] dist) returns [int, int[]] {
int n = dist.length();
int N = 1 << n; // number of subsets: 2^n
int INF = int:MAX_VALUE / 4;
// dp[mask][j] = minimum cost to reach subset 'mask' and end at node j
int[][] dp = [];
dp.setLength(N);
foreach int i in 0..<N {
dp[i].setLength(n);
foreach int j in 0..<n { dp[i][j] = INF; }
}
// parent[mask][j] = previous node before j in optimal path for (mask, j)
int[][] parent = [];
parent.setLength(N);
foreach int i in 0..<N {
parent[i].setLength(n);
foreach int j in 0..<n { parent[i][j] = -1; }
}
// Base case: start at node 0, mask = 1<<0.
dp[1][0] = 0;
// Iterate over all subsets that include node 0.
foreach int mask in 1..<N {
if (mask & 1) == 0 { continue; } // we always require the tour to start at node 0
foreach int j in 1..<n {
if (mask & (1 << j)) == 0 { continue; } // j not in subset
int prevMask = mask ^ (1 << j);
// Try all possibilities of coming to j from some k in prev_mask.
foreach int k in 0..<n {
if (prevMask & (1 << k)) != 0 {
int cost = dp[prevMask][k] + dist[k][j];
if cost < dp[mask][j] {
dp[mask][j] = cost;
parent[mask][j] = k;
}
}
}
}
}
// Close the tour: return to node 0.
int fullMask = (1 << n) - 1;
int minCost = INF;
int last = -1;
foreach int j in 1..<n {
int cost = dp[fullMask][j] + dist[j][0];
if cost < minCost {
minCost = cost;
last = j;
}
}
// Reconstruct path.
int[] path = [];
int mask = fullMask;
int curr = last;
while curr != -1 {
path.push(curr);
int prev = parent[mask][curr];
mask ^= (1 << curr);
curr = prev;
}
path.push(0); // add the start node
path = path.reverse(); // reverse to get 0 -> ... -> last
path.push(0); // and return to 0
return [minCost, path];
}
public function main() {
int[][] distMatrix = [
[0, 2, 9, 10],
[1, 0, 6, 4],
[15, 7, 0, 8],
[6, 3, 12, 0]
];
[int, int[]] ct = heldKarp(distMatrix);
io:println(`Minimum tour cost: ${ct[0]}`);
io:println(`Tour: ${ct[1]}`);
}
- Output:
Minimum tour cost: 21 Tour: [0,0,2,3,1,0]
C++
#include <bits/stdc++.h>
using namespace std;
/*
* Solve the Traveling Salesman Problem using the Held–Karp algorithm (O(n^2·2^n)).
* dist: square matrix of pairwise distances, dist[i][j] is the cost from i to j.
* Returns a pair (min_cost, tour), where tour is a sequence of node indices
* starting and ending at 0.
*/
pair<long long, vector<int>> heldKarp(const vector<vector<long long>>& dist) {
int n = dist.size();
int N = 1 << n; // number of subsets
const long long INF = LLONG_MAX / 4;
// dp[mask][j] = min cost to start at 0, visit exactly the cities in mask, and end at j
vector<vector<long long>> dp(N, vector<long long>(n, INF));
// parent[mask][j] = best predecessor of j in the optimal path for (mask, j)
vector<vector<int>> parent(N, vector<int>(n, -1));
dp[1][0] = 0; // base case: mask=1<<0, at city 0, cost=0
// Build up DP table
for (int mask = 1; mask < N; ++mask) {
if ((mask & 1) == 0) continue; // we always include city 0 in the tour
for (int j = 1; j < n; ++j) {
if ((mask & (1 << j)) == 0) continue;
int prevMask = mask ^ (1 << j);
for (int k = 0; k < n; ++k) {
if (prevMask & (1 << k)) {
long long cost = dp[prevMask][k] + dist[k][j];
if (cost < dp[mask][j]) {
dp[mask][j] = cost;
parent[mask][j] = k;
}
}
}
}
}
// Close the tour by returning to city 0
int fullMask = N - 1;
long long minCost = INF;
int lastCity = -1;
for (int j = 1; j < n; ++j) {
long long cost = dp[fullMask][j] + dist[j][0];
if (cost < minCost) {
minCost = cost;
lastCity = j;
}
}
// Reconstruct the optimal tour
vector<int> tour;
int mask = fullMask, cur = lastCity;
while (cur != -1) {
tour.push_back(cur);
int p = parent[mask][cur];
mask ^= (1 << cur);
cur = p;
}
tour.push_back(0); // add the start city
reverse(tour.begin(), tour.end());
tour.push_back(0); // return to start
return {minCost, tour};
}
int main() {
// Example test case: 4 cities, symmetric distances
vector<vector<long long>> dist = {
{ 0, 2, 9, 10},
{ 1, 0, 6, 4},
{15, 7, 0, 8},
{ 6, 3, 12, 0}
};
auto [cost, tour] = heldKarp(dist);
cout << "Minimum tour cost: " << cost << "\n";
cout << "Tour: ";
for (int v : tour) {
cout << v << " ";
}
cout << "\n";
return 0;
}
- Output:
Minimum tour cost: 21 Tour: 0 0 2 3 1 0
EasyLang
sysconf zero_based
#
proc held_karp &dist[][] &min_cost &tour[] .
n = len dist[][]
nn = bitshift 1 n
len dp[][] nn
len parent[][] nn
for mask range0 nn
len dp[mask][] n
len parent[mask][] n
for j range0 n
dp[mask][j] = 1 / 0
parent[mask][j] = -1
.
.
dp[1][0] = 0
for mask = 1 to nn - 1 : if bitand mask 1 <> 0
for j = 1 to n - 1 : if bitand mask bitshift 1 j <> 0
prev_mask = bitxor mask bitshift 1 j
for k range0 n
if bitand prev_mask bitshift 1 k <> 0
cost = dp[prev_mask][k] + dist[k][j]
if cost < dp[mask][j]
dp[mask][j] = cost
parent[mask][j] = k
.
.
.
.
.
full_mask = nn - 1
min_cost = 1 / 0
last = 0
for j = 1 to n - 1
cost = dp[full_mask][j] + dist[j][0]
if cost < min_cost
min_cost = cost
last = j
.
.
tour[] = [ ]
mask = full_mask
curr = last
while curr <> 0
tour[] &= curr
prev = parent[mask][curr]
mask = bitxor mask bitshift 1 curr
curr = prev
.
tour[] &= 0
for i range0 len tour[] div 2 : swap tour[i] tour[$ - i - 1]
tour[] &= 0
.
dist[][] = [ [ 0 2 9 10 ] [ 1 0 6 4 ] [ 15 7 0 8 ] [ 6 3 12 0 ] ]
held_karp dist[][] cost tour[]
print "Tour: " & tour[]
print "Cost: " & cost- Output:
Tour: [ 0 2 3 1 0 ] Cost: 21
FreeBASIC
#include "crt/math.bi"
Const INF As Double = INFINITY
' Function to find the minimum cost tour using Held-Karp algorithm
Sub HeldKarp(dist() As Double, Byref minCost As Double, path() As Integer)
Dim As Integer n, i, j, k
n = Ubound(dist, 1) + 1
Dim As Integer numMask = 1 Shl n
' dp[mask][j] = minimum cost to reach subset 'mask' and end at node j
Dim As Double dp(0 To numMask-1, 0 To n-1)
' parent[mask][j] = previous node before j in optimal path for (mask, j)
Dim As Integer parent(0 To numMask-1, 0 To n-1)
' Initialize dp with infinity
For i = 0 To numMask-1
For j = 0 To n-1
dp(i, j) = INF
parent(i, j) = -1
Next j
Next i
' Base case: start at node 0, mask = 1<<0
dp(1, 0) = 0
' Iterate over all subsets that include node 0
For mask As Integer = 1 To numMask-1
If (mask And 1) = 0 Then Continue For ' We always require the tour to start at node 0
For j = 1 To n-1
If ((mask Xor (1 Shl j)) = 0) Then Continue For ' j not in subset
Dim As Integer prevMask = mask Xor (1 Shl j)
' Try all possibilities of coming to j from some k in prevMask
For k = 0 To n-1
If ((prevMask And (1 Shl k)) <> 0) Then
Dim As Double cost = dp(prevMask, k) + dist(k, j)
If cost < dp(mask, j) Then
dp(mask, j) = cost
parent(mask, j) = k
End If
End If
Next k
Next j
Next mask
' Close the tour: return to node 0
Dim As Integer fullMask = (1 Shl n) - 1
minCost = INF
Dim As Integer last = -1
For j = 1 To n-1
Dim As Double cost = dp(fullMask, j) + dist(j, 0)
If cost < minCost Then
minCost = cost
last = j
End If
Next j
' Reconstruct path
Redim path(0 To n) ' n+1 elements for the complete tour
Dim As Integer pathIndex = n
path(pathIndex) = 0 ' End at node 0
pathIndex -= 1
Dim As Integer mask = fullMask
Dim As Integer curr = last
While curr <> -1 And curr <> 0
path(pathIndex) = curr
pathIndex -= 1
Dim As Integer prev = parent(mask, curr)
mask Xor= (1 Shl curr)
curr = prev
Wend
path(pathIndex) = 0 ' Start at node 0
End Sub
'' Example test case: 4 cities, symmetric distance matrix
Dim As Double distMatrix(0 To 3, 0 To 3)
distMatrix(0, 0) = 0 : distMatrix(0, 1) = 2 : distMatrix(0, 2) = 9 : distMatrix(0, 3) = 10
distMatrix(1, 0) = 1 : distMatrix(1, 1) = 0 : distMatrix(1, 2) = 6 : distMatrix(1, 3) = 4
distMatrix(2, 0) = 15 : distMatrix(2, 1) = 7 : distMatrix(2, 2) = 0 : distMatrix(2, 3) = 8
distMatrix(3, 0) = 6 : distMatrix(3, 1) = 3 : distMatrix(3, 2) = 12 : distMatrix(3, 3) = 0
Dim As Double minCost
Dim As Integer path(0 To 4) ' For a 4-city problem, the path has 5 elements (including return to start)
HeldKarp(distMatrix(), minCost, path())
Print "Minimum tour cost:"; minCost
Print "Tour:";
For i As Integer = 0 To Ubound(path)
Print path(i);
If i < Ubound(path) Then Print " ->";
Next i
Sleep
- Output:
Minimum tour cost: 21 Tour: 0 -> 2 -> 3 -> 1 -> 0
Go
package main
import (
"fmt"
"math"
)
type Result struct {
Cost int
Tour []int
}
// 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.
func heldKarp(dist [][]int) Result {
n := len(dist)
subsetCount := 1 << n
const INF = math.MaxInt32 / 4
// dp[mask][j] = minimum cost to start at 0, visit exactly the cities in mask, and end at j
dp := make([][]int, subsetCount)
parents := make([][]int, subsetCount)
for mask := 0; mask < subsetCount; mask++ {
dp[mask] = make([]int, n)
parents[mask] = make([]int, n)
for j := 0; j < n; j++ {
dp[mask][j] = INF
parents[mask][j] = -1
}
}
// Base case: mask = 1<<0, at city 0, cost = 0
dp[1][0] = 0
// Build up dp table
for mask := 1; mask < subsetCount; mask++ {
// City 0 must always be included
if mask&1 == 0 {
continue
}
for j := 1; j < n; j++ {
if mask&(1<<j) == 0 {
continue
}
prevMask := mask ^ (1 << j)
for k := 0; k < n; k++ {
if prevMask&(1<<k) == 0 {
continue
}
cost := dp[prevMask][k] + dist[k][j]
if cost < dp[mask][j] {
dp[mask][j] = cost
parents[mask][j] = k
}
}
}
}
// Complete the tour by returning to city 0
fullMask := subsetCount - 1
minCost := INF
lastCity := 0
for j := 1; j < n; j++ {
cost := dp[fullMask][j] + dist[j][0]
if cost < minCost {
minCost = cost
lastCity = j
}
}
// Reconstruct the optimal tour
tour := make([]int, 0, n+1)
mask := fullMask
curr := lastCity
for curr != 0 {
tour = append(tour, curr)
p := parents[mask][curr]
mask ^= 1 << curr
curr = p
}
// append the start city, reverse, then return to start
tour = append(tour, 0)
reverse(tour)
tour = append(tour, 0)
return Result{Cost: minCost, Tour: tour}
}
// reverse reverses a slice of ints in place.
func reverse(a []int) {
for i, j := 0, len(a)-1; i < j; i, j = i+1, j-1 {
a[i], a[j] = a[j], a[i]
}
}
func main() {
// Test case: 4 cities with symmetric distances
dist := [][]int{
{0, 2, 9, 10},
{1, 0, 6, 4},
{15, 7, 0, 8},
{6, 3, 12, 0},
}
result := heldKarp(dist)
fmt.Printf("Minimum tour cost: %d\n", result.Cost)
fmt.Printf("Tour: %v\n", result.Tour)
}
- Output:
Minimum tour cost: 21 Tour: [0 2 3 1 0]
Java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public final class HeldKarpAlgorithm {
public static void main(String[] args) {
// Test case: 4 cities with symmetric distances
// @see the heldKarpAlgorithm() method comment for a description of this list.
List<List<Integer>> distances = List.of(
List.of( 0, 2, 9, 10 ),
List.of( 1, 0, 6, 4 ),
List.of( 15, 7, 0, 8 ),
List.of( 6, 3, 12, 0 )
);
Result result = heldKarpAlgorithm(distances);
System.out.println("Minimum tour cost: " + result.cost);
System.out.println("Tour: " + result.tour);
}
/*
* Solve the Travelling Salesman Problem using the Held–Karp algorithm (O(n^2·2^n)).
*
* @param distances : A square matrix of pairwise distances,
* where distances.get(i).get(j) is the cost of travelling from city i to city j.
* @return : A Result(minimumCcost, tour), where tour is a list of city indices starting and ending at 0,
* and minimumCost is the cost of travelling along this tour.
*/
private static Result heldKarpAlgorithm(List<List<Integer>> distances) {
final int subsetCount = 1 << distances.size();
final int INFINITY = Integer.MAX_VALUE / 4;
// dp.get(mask).get(j) = minimum cost to start at 0, visit exactly the cities in the mask, and end at city j
List<List<Integer>> dp = IntStream.range(0, subsetCount).boxed()
.map( i -> new ArrayList<Integer>(Collections.nCopies(distances.size(), INFINITY)) )
.collect(Collectors.toList());
// parents.get(mask).get(j) = best predecessor of j in the optimal path from mask to j
List<List<Integer>> parents = IntStream.range(0, subsetCount).boxed()
.map( i -> new ArrayList<Integer>(Collections.nCopies(distances.size(), -1)) )
.collect(Collectors.toList());
dp.get(1).set(0, 0); // Set the base case which is mask = 1 << 0, at city 0, with cost = 0
// Build up dp table
for ( int mask = 1; mask < subsetCount; mask++ ) {
if ( ( mask & 1 ) == 0 ) {
continue; // City 0 is always included in the tour
}
for ( int j = 1; j < distances.size(); j++ ) {
if ( ( mask & ( 1 << j ) ) == 0 ) {
continue; // City j is not in this subset
}
final int previousMask = mask ^ ( 1 << j );
// Attempt to travel to city j from city k in the previousMask
for ( int k = 0; k < distances.size(); k++ ) {
if ( ( previousMask & ( 1 << k ) ) > 0 ) {
final int cost = dp.get(previousMask).get(k) + distances.get(k).get(j);
if ( cost < dp.get(mask).get(j) ) {
dp.get(mask).set(j, cost);
parents.get(mask).set(j, k);
}
}
}
}
}
// Complete the tour by returning to city 0
final int fullMask = subsetCount - 1;
int minimumCost = INFINITY;
int lastCity = 0;
for ( int j = 1; j < distances.size(); j++ ) {
final int cost = dp.get(fullMask).get(j) + distances.get(j).get(0);
if ( cost < minimumCost ) {
minimumCost = cost;
lastCity = j;
}
}
// Construct the optimal tour
List<Integer> tour = new ArrayList<Integer>(distances.size() + 1);
int tourMask = fullMask;
int currentCity = lastCity;
// Backtrack until city 0 is reached
while ( currentCity != 0 ) {
tour.addLast(currentCity);
final int parent = parents.get(tourMask).get(currentCity);
tourMask ^= ( 1 << currentCity );
currentCity = parent;
}
tour.addLast(0); // Include the start city 0
Collections.reverse(tour);
tour.addLast(0); // Return to the start city 0
return new Result(minimumCost, tour);
}
private record Result(int cost, List<Integer> tour) {}
}
- Output:
Minimum tour cost: 21 Tour: [0, 2, 3, 1, 0]
JavaScript
/**
* Solve the Traveling Salesman Problem using the Held–Karp algorithm (O(n^2·2^n)).
* @param {number[][]} dist – an n×n matrix of pairwise distances
* @returns {{ cost: number, tour: number[] }}
* cost: minimum tour cost
* tour: list of city indices starting and ending at 0
*/
function heldKarp(dist) {
const n = dist.length;
const subsetCount = 1 << n;
const INF = Infinity;
// dp[mask][j] = minimum cost to start at 0, visit exactly the cities in mask, and end at j
const dp = Array.from({ length: subsetCount }, () => Array(n).fill(INF));
// parent[mask][j] = best predecessor of j in the optimal path for (mask, j)
const parent = Array.from({ length: subsetCount }, () => Array(n).fill(-1));
// Base case: mask = 1<<0, at city 0, cost = 0
dp[1][0] = 0;
// Build up dp table
for (let mask = 1; mask < subsetCount; mask++) {
// City 0 must always be included
if ((mask & 1) === 0) continue;
for (let j = 1; j < n; j++) {
if ((mask & (1 << j)) === 0) continue;
const prevMask = mask ^ (1 << j);
// Try to come to j from some k in prevMask
for (let k = 0; k < n; k++) {
if ((prevMask & (1 << k)) === 0) continue;
const cost = dp[prevMask][k] + dist[k][j];
if (cost < dp[mask][j]) {
dp[mask][j] = cost;
parent[mask][j] = k;
}
}
}
}
// Close the tour by returning to city 0
const fullMask = subsetCount - 1;
let minCost = INF;
let lastCity = 0;
for (let j = 1; j < n; j++) {
const cost = dp[fullMask][j] + dist[j][0];
if (cost < minCost) {
minCost = cost;
lastCity = j;
}
}
// Reconstruct the optimal tour
const tour = [];
let mask = fullMask;
let curr = lastCity;
while (curr !== 0) {
tour.push(curr);
const p = parent[mask][curr];
mask ^= 1 << curr;
curr = p;
}
tour.push(0);
tour.reverse();
tour.push(0);
return { cost: minCost, tour };
}
// -- Example usage:
const dist = [
[ 0, 2, 9, 10 ],
[ 1, 0, 6, 4 ],
[15, 7, 0, 8 ],
[ 6, 3, 12, 0 ]
];
const { cost, tour } = heldKarp(dist);
console.log("Minimum tour cost:", cost);
console.log("Tour:", tour);
- Output:
Minimum tour cost: 21 Tour: [ 0, 2, 3, 1, 0 ]
Julia
const INF = typemax(Int32)
"""
Solve the Traveling Salesman Problem using the Held–Karp algorithm.
dist is a 2D square matrix (list of lists) of pairwise distances.
Returns (min_cost, tour) where tour is a list of node indices, starting
and ending at 0.
"""
function heldkarp(dist)
n = length(dist)
N = 1 << n # Number of subsets 2^n
# dp[mask][j] = minimum cost to reach subset 'mask' and end at node j
dp = [fill(INF, n) for _ in 1:N]
# parent[mask][j] = previous node before j in optimal path for (mask, j)
parent = [fill(-1, n) for _ in 1:N]
dp[begin+1][begin] = 0 # Base case start at node 1 mask = 1<<0
# Iterate over all subsets that include node 1
for mask in 1:2:N-1 # NB: zero based mask, but 1 based indexing
for j in 2:n
mask & (1 << (j - 1)) == 0 && continue # j not in subset
prev_mask = mask ⊻ (1 << (j - 1))
# Try all possibilities of coming to j from some k in prev_mask
for k in 1:n
prev_mask & (1 << (k - 1)) == 0 && continue
cost = dp[prev_mask+1][k] + dist[k][j]
if cost < dp[mask+1][j]
dp[mask+1][j] = cost
parent[mask+1][j] = k - 1
end
end
end
end
# Close the tour return to node 1
full_mask, min_cost, last = N - 1, INF, 0
for j in 2:n
cost = dp[full_mask+1][j] + dist[j][begin]
if cost < min_cost
min_cost = cost
last = j - 1
end
end
# Reconstruct path
path = Int[]
mask, curr = full_mask, last
while curr != 0
push!(path, curr)
prev = parent[mask+1][curr+1]
mask ⊻= 1 << curr
curr = prev
end
push!(path, 0) # add the start node
reverse!(path) # reverse to get 0 -> ... -> last
push!(path, 0) # and return to 0
return min_cost, path
end
function test_tour()
# Example test case 4 cities, symmetric distances
dist_matrix = [
[0, 2, 9, 10],
[1, 0, 6, 4],
[15, 7, 0, 8],
[6, 3, 12, 0],
]
cost, tour = heldkarp(dist_matrix)
println("Minimum tour cost: ", cost)
println("Tour: ", tour)
end
test_tour()
- Output:
Minimum tour cost: 21 Tour: [0, 2, 3, 1, 0]
Phix
// 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.
function heldKarp(sequence dist)
integer n := length(dist), subsetCount := power(2,n), INF = #1FFFFFFF
// dp[mask][j] = minimum cost to start at 0, visit exactly the cities in mask, and end at j
sequence dp := repeat(repeat(INF,n), subsetCount),
parents := repeat(repeat(-1,n), subsetCount)
// Base case: mask = 1<<0, at city 0, cost = 0
dp[1][1] = 0
// Build up dp table
for mask=1 to subsetCount-1 do
// City 0 must always be included
if mask && 1 then
for j=2 to n do
if mask && power(2,j-1) then
integer prevMask := mask-power(2,j-1)
for k=1 to n do
if prevMask && power(2,k-1) then
atom cost := dp[prevMask][k] + dist[k][j]
if cost < dp[mask][j] then
dp[mask][j] = cost
parents[mask][j] = k
end if
end if
end for
end if
end for
end if
end for
// Complete the tour by returning to city 0
integer fullMask := subsetCount - 1,
lastCity := 1
atom minCost := INF
for j=2 to n do
atom cost := dp[fullMask][j] + dist[j][1]
if cost < minCost then
minCost = cost
lastCity = j
end if
end for
// Reconstruct the optimal tour
sequence tour := {}
integer mask := fullMask,
curr := lastCity
while curr != 1 do
tour &= curr-1
integer p := parents[mask][curr]
mask -= power(2,curr-1)
curr = p
end while
// append the start city, reverse, then return to start
tour &= 0
tour = reverse(tour)
tour &= 0
return {minCost, tour}
end function
// Test case: 4 cities with symmetric distances
constant dist = {{0, 2, 9, 10},
{1, 0, 6, 4},
{15, 7, 0, 8},
{6, 3, 12, 0}}
{atom cost, sequence tour} = heldKarp(dist)
printf(1,"Minimum tour cost: %d\n", cost)
printf(1,"Tour: %v\n", {tour})
- Output:
Minimum tour cost: 21
Tour: {0,2,3,1,0}
PureBasic
Procedure.d HeldKarp(*distMatrix.Double, n.i, *resultPath.Integer)
; n = number of cities
Define numMask.i = 1 << n
Define INF.d = 1.7976931348623157e+308 ; Maximum value for a double
; Allocate memory for dp array: dp[mask][j] = minimum cost to reach subset 'mask' and end at node j
Dim dp.d(numMask-1, n-1)
; Allocate memory for parent array: parent[mask][j] = previous node before j in optimal path for (mask, j)
Dim parent.i(numMask-1, n-1)
; Initialize dp with infinity and parent with -1
For mask = 0 To numMask-1
For j = 0 To n-1
dp(mask, j) = INF
parent(mask, j) = -1
Next j
Next mask
; Base case: start at node 0, mask = 1<<0
dp(1, 0) = 0
; Iterate over all subsets that include node 0
For mask = 1 To numMask-1
If (mask & 1) = 0 : Continue : EndIf ; We always require the tour to start at node 0
For j = 1 To n-1
If ((mask ! (1 << j)) = 0) : Continue : EndIf ; j not in subset
prevMask = mask ! (1 << j)
; Try all possibilities of coming to j from some k in prevMask
For k = 0 To n-1
If ((prevMask & (1 << k)) <> 0)
; Get the distance from k to j from the distance matrix
distKJ.d = PeekD(*distMatrix + (k * n + j) * SizeOf(Double))
cost.d = dp(prevMask, k) + distKJ
If cost < dp(mask, j)
dp(mask, j) = cost
parent(mask, j) = k
EndIf
EndIf
Next k
Next j
Next mask
; Close the tour: return to node 0
fullMask = (1 << n) - 1
minCost.d = INF
last = -1
For j = 1 To n-1
; Get the distance from j to 0 from the distance matrix
distJ0.d = PeekD(*distMatrix + (j * n + 0) * SizeOf(Double))
cost.d = dp(fullMask, j) + distJ0
If cost < minCost
minCost = cost
last = j
EndIf
Next j
; Reconstruct path
pathIndex = n
PokeI(*resultPath + pathIndex * SizeOf(Integer), 0) ; End at node 0
pathIndex - 1
mask = fullMask
curr = last
While curr <> -1 And curr <> 0
PokeI(*resultPath + pathIndex * SizeOf(Integer), curr)
pathIndex - 1
prev = parent(mask, curr)
mask = mask ! (1 << curr)
curr = prev
Wend
PokeI(*resultPath + pathIndex * SizeOf(Integer), 0) ; Start at node 0
ProcedureReturn minCost
EndProcedure
OpenConsole()
; Example test case: 4 cities, symmetric distance matrix
n = 4
; Create and initialize the distance matrix directly
Dim distMatrix.d(n-1, n-1)
distMatrix(0, 0) = 0 : distMatrix(0, 1) = 2 : distMatrix(0, 2) = 9 : distMatrix(0, 3) = 10
distMatrix(1, 0) = 1 : distMatrix(1, 1) = 0 : distMatrix(1, 2) = 6 : distMatrix(1, 3) = 4
distMatrix(2, 0) = 15 : distMatrix(2, 1) = 7 : distMatrix(2, 2) = 0 : distMatrix(2, 3) = 8
distMatrix(3, 0) = 6 : distMatrix(3, 1) = 3 : distMatrix(3, 2) = 12 : distMatrix(3, 3) = 0
; Allocate memory for the path
Dim path.i(n) ; For a 4-city problem, the path has 5 elements (including return to start)
; Call the Held-Karp algorithm
minCost.d = HeldKarp(@distMatrix(0, 0), n, @path(0))
PrintN("Minimum tour cost: " + StrD(minCost))
Print("Tour: ")
For i = 0 To n
Print(Str(path(i)))
If i < n
Print(" -> ")
EndIf
Next
Input()
CloseConsole()
- Output:
Same to FreeBASIC entry.
Python
from itertools import combinations
def held_karp(dist):
"""
Solve the Traveling Salesman Problem using the Held–Karp algorithm.
dist: a 2D square matrix (list of lists) of pairwise distances.
Returns (min_cost, tour) where tour is a list of node indices, starting
and ending at 0.
"""
n = len(dist)
# Number of subsets: 2^n
N = 1 << n
INF = float('inf')
# dp[mask][j] = minimum cost to reach subset 'mask' and end at node j
dp = [[INF] * n for _ in range(N)]
# parent[mask][j] = previous node before j in optimal path for (mask, j)
parent = [[None] * n for _ in range(N)]
# Base case: start at node 0, mask = 1<<0
dp[1][0] = 0
# Iterate over all subsets that include node 0
for mask in range(1, N):
if not (mask & 1):
continue # we always require the tour to start at node 0
for j in range(1, n):
if not (mask & (1 << j)):
continue # j not in subset
prev_mask = mask ^ (1 << j)
# Try all possibilities of coming to j from some k in prev_mask
for k in range(n):
if prev_mask & (1 << k):
cost = dp[prev_mask][k] + dist[k][j]
if cost < dp[mask][j]:
dp[mask][j] = cost
parent[mask][j] = k
# Close the tour: return to node 0
full_mask = (1 << n) - 1
min_cost = INF
last = None
for j in range(1, n):
cost = dp[full_mask][j] + dist[j][0]
if cost < min_cost:
min_cost = cost
last = j
# Reconstruct path
path = []
mask = full_mask
curr = last
while curr is not None:
path.append(curr)
prev = parent[mask][curr]
mask ^= (1 << curr)
curr = prev
path.append(0) # add the start node
path.reverse() # reverse to get 0 -> ... -> last
path.append(0) # and return to 0
return min_cost, path
if __name__ == "__main__":
# Example test case: 4 cities, symmetric distances
dist_matrix = [
[0, 2, 9, 10],
[1, 0, 6, 4],
[15, 7, 0, 8],
[6, 3, 12, 0]
]
cost, tour = held_karp(dist_matrix)
print("Minimum tour cost:", cost)
print("Tour:", tour)
- Output:
Minimum tour cost: 21 Tour: [0, 0, 2, 3, 1, 0]
Raku
# 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!
Rust
use std::u64;
#[allow(non_snake_case)]
fn held_karp(dist: &[Vec<u64>]) -> (u64, Vec<usize>) {
let n = dist.len();
assert!(n > 1 && n <= (std::mem::size_of::<usize>() * 8));
let N = 1 << n;
let inf = u64::MAX / 4;
// dp[mask][j] = min cost to start at 0, visit exactly the cities in mask, and end at j
let mut dp = vec![vec![inf; n]; N];
// parent[mask][j] = previous city before j in optimal path covering mask
let mut parent = vec![vec![None; n]; N];
// Base case: at city 0 with mask = 1<<0
dp[1][0] = 0;
// Build up dp
for mask in 1..N {
if mask & 1 == 0 {
// we always include city 0 in the tour
continue;
}
for j in 1..n {
if mask & (1 << j) == 0 {
continue; // city j not in this subset
}
let prev_mask = mask ^ (1 << j);
// try to come to j from some k in prev_mask
for k in 0..n {
if prev_mask & (1 << k) == 0 {
continue;
}
let cost = dp[prev_mask][k].saturating_add(dist[k][j]);
if cost < dp[mask][j] {
dp[mask][j] = cost;
parent[mask][j] = Some(k);
}
}
}
}
// Close the tour by returning to city 0
let full_mask = N - 1;
let mut min_cost = inf;
let mut last_city = 0;
for j in 1..n {
let cost = dp[full_mask][j].saturating_add(dist[j][0]);
if cost < min_cost {
min_cost = cost;
last_city = j;
}
}
// Reconstruct the tour path
let mut path = Vec::with_capacity(n + 1);
let mut mask = full_mask;
let mut curr = last_city;
// backtrack until we reach city 0
while curr != 0 {
path.push(curr);
let prev = parent[mask][curr]
.expect("Parent must exist for all but the start city");
mask ^= 1 << curr;
curr = prev;
}
path.push(0); // include the start city
path.reverse(); // now path = [0, ..., last_city]
path.push(0); // return to start
(min_cost, path)
}
fn main() {
// Example test case: 4 cities, symmetric distances
let dist: Vec<Vec<u64>> = vec![
vec![ 0, 2, 9, 10],
vec![ 1, 0, 6, 4],
vec![15, 7, 0, 8],
vec![ 6, 3, 12, 0],
];
let (cost, tour) = held_karp(&dist);
println!("Minimum tour cost: {}", cost);
print!("Tour: ");
for v in &tour {
print!("{} ", v);
}
println!();
}
- Output:
Minimum tour cost: 21 Tour: 0 2 3 1 0
Wren
/* Solve the Traveling Salesman Problem using the Held–Karp algorithm.
dist: a 2D square matrix (list of lists) of pairwise distances.
Returns (minCost, tour) where tour is a list of node indices, starting
and ending at 0.
*/
var heldKarp = Fn.new { |dist|
var n = dist.count
var N = 1 << n
var INF = Num.infinity
// dp[mask][j] = minimum cost to reach subset 'mask' and end at node j
var dp = List.filled(N, null)
for (i in 0...N) dp[i] = List.filled(n, INF)
// parent[mask][j] = previous node before j in optimal path for (mask, j)
var parent = List.filled(N, null)
for (i in 0...N) parent[i] = List.filled(n, null)
// Base case: start at node 0, mask = 1<<0
dp[1][0] = 0
// Iterate over all subsets that include node 0.
for (mask in 1...N) {
if (mask & 1 == 0) continue // we always require the tour to start at node 0
for (j in 1...n) {
if ((mask & (1 << j)) == 0) continue // j not in subset
var prevMask = mask ^ (1 << j)
// Try all possibilities of coming to j from some k in prevMask
for (k in 0...n) {
if ((prevMask & (1 << k)) != 0) {
var cost = dp[prevMask][k] + dist[k][j]
if (cost < dp[mask][j]) {
dp[mask][j] = cost
parent[mask][j] = k
}
}
}
}
}
// Close the tour: return to node 0.
var fullMask = (1 << n) - 1
var minCost = INF
var last = null
for (j in 1...n) {
var cost = dp[fullMask][j] + dist[j][0]
if (cost < minCost) {
minCost = cost
last = j
}
}
// Reconstruct path
var path = []
var mask = fullMask
var curr = last
while (curr) {
path.add(curr)
var prev = parent[mask][curr]
mask = mask ^ (1 << curr)
curr = prev
}
path.add(0) // add the start node
path = path[-1..0] // reverse to get 0 -> ... -> last
path.add(0) // and return to 0
return [minCost, path]
}
// Example test case: 4 cities, symmetric distances
var distMatrix = [
[0, 2, 9, 10],
[1, 0, 6, 4],
[15, 7, 0, 8],
[6, 3, 12, 0]
]
var ct = heldKarp.call(distMatrix)
System.print("Minimum tour cost: %(ct[0])")
System.print("Tour: %(ct[1]))")
- Output:
Minimum tour cost: 21 Tour: [0, 0, 2, 3, 1, 0])
XPL0
proc HeldKarp(Dist, N); \Display the traveling salesman tour and cost
int Dist, N; \NxN array of traveling costs between cities
int NN, Inf, DP, Parent, Mask, PrevMask, I, J, K;
int MinCost, Tour, Cost, FullMask, Last, Curr, Prev, TourLen;
[Inf:= $7FFF_FFFF / 4;
NN:= 1 << N; \number of subsets: 2^N
\DP(Mask,J) = minimum cost to start at 0, visit the cities in Mask, and end at J
DP:= Reserve(NN*4); \4 = SizeOf int
Parent:= Reserve(NN*4);
for Mask:= 0 to NN-1 do
[DP(Mask):= Reserve(N*4);
Parent(Mask):= Reserve(N*4);
for J:= 0 to N-1 do
[DP(Mask,J):= Inf;
Parent(Mask,J):= -1;
];
];
DP(1,0):= 0; \base case: mask = 1<<0, at city 0, cost = 0
for Mask:= 1 to NN-1 do \build up DP table
if Mask & 1 then \city 0 must always be included at start
for J:= 1 to N-1 do
if Mask & 1<<J then
[PrevMask:= Mask & ~(1<<J);
for K:= 0 to N-1 do
if PrevMask & 1<<K then
[Cost:= DP(PrevMask,K) + Dist(K,J);
if Cost < DP(Mask,J) then
[DP(Mask,J):= Cost;
Parent(Mask,J):= K;
];
];
];
FullMask:= NN-1;
MinCost:= Inf;
Last:= 0;
for J:= 1 to N-1 do
[Cost:= DP(FullMask,J) + Dist(J,0);
if Cost < MinCost then
[MinCost:= Cost;
Last:= J;
];
];
Tour:= Reserve(N*4); \build the tour
Mask:= FullMask;
Curr:= Last;
TourLen:= 0;
while Curr # 0 do
[Tour(TourLen):= Curr;
TourLen:= TourLen+1;
Prev:= Parent(Mask,Curr);
Mask:= Mask & ~(1<<Curr);
Curr:= Prev;
];
Text(0, "Tour: [0 "); \display the tour starting and ending at city 0
for I:= TourLen-1 downto 0 do
[IntOut(0, Tour(I)); ChOut(0, ^ )];
Text(0, "0]"); CrLf(0);
Text(0, "Cost: "); IntOut(0, MinCost); CrLf(0);
];
int Dist;
[Dist:=[[ 0, 2, 9, 10],
[ 1, 0, 6, 4],
[15, 7, 0, 8],
[ 6, 3, 12, 0]];
HeldKarp(Dist, 4);
]- Output:
Tour: [0 2 3 1 0] Cost: 21
Zig
const std = @import("std");
/// Solve the Traveling Salesman Problem using the Held--Karp algorithm (O(n^2·2^n)).
/// dist: square matrix of pairwise distances, dist[i][j] is the cost from i to j.
/// Returns a tuple {min_cost, tour}, where tour is a sequence of node indices
/// starting and ending at 0.
fn heldKarp(allocator: std.mem.Allocator, dist: []const []const i64) !struct { cost: i64, tour: []u32 } {
const n = @as(u32,@intCast(dist.len));
const N = @as(u32, 1) << @as(u5, @intCast(n)); // number of subsets
const INF = std.math.maxInt(i64) / 4;
// dp[mask][j] = min cost to start at 0, visit exactly the cities in mask, and end at j
var dp = try allocator.alloc([]i64, N);
defer allocator.free(dp);
for (dp, 0..) |*row, i| {
row.* = try allocator.alloc(i64, n);
@memset(row.*, INF);
defer if (i != N - 1) allocator.free(row.*);
}
defer allocator.free(dp[N - 1]);
// parent[mask][j] = best predecessor of j in the optimal path for (mask, j)
var parent = try allocator.alloc([]i32, N);
defer allocator.free(parent);
for (parent, 0..) |*row, i| {
row.* = try allocator.alloc(i32, n);
@memset(row.*, -1);
defer if (i != N - 1) allocator.free(row.*);
}
defer allocator.free(parent[N - 1]);
dp[1][0] = 0; // base case: mask=1<<0, at city 0, cost=0
// Build up DP table
var mask: u32 = 1;
while (mask < N) : (mask += 1) {
if ((mask & 1) == 0) continue; // we always include city 0 in the tour
var j: u32 = 1;
while (j < n) : (j += 1) {
if ((mask & (@as(u32, 1) << @as(u5, @intCast(j)) ) ) == 0) continue;
const prevMask = mask ^ (@as(u32, 1) << @as(u5, @intCast(j)));
var k: u32 = 0;
while (k < n) : (k += 1) {
if (prevMask & (@as(u32, 1) << @as(u5, @intCast(k)) ) != 0) {
const cost = dp[prevMask][k] + dist[k][j];
if (cost < dp[mask][j]) {
dp[mask][j] = cost;
parent[mask][j] = @as(i32, @intCast(k));
}
}
}
}
}
// Close the tour by returning to city 0
const fullMask = N - 1;
var minCost: i64 = INF;
var lastCity: i32 = -1;
var j: u32 = 1;
while (j < n) : (j += 1) {
const cost = dp[fullMask][j] + dist[j][0];
if (cost < minCost) {
minCost = cost;
lastCity = @as(i32, @intCast(j));
}
}
// Reconstruct the optimal tour
var tour = std.ArrayList(u32).init(allocator);
defer tour.deinit();
var curMask = fullMask;
var cur = lastCity;
while (cur != -1) {
try tour.append( @as(u32, @intCast(cur)));
const p = parent[curMask][@as(usize, @intCast(cur))];
curMask ^= (@as(u32, 1) << @as(u5, @intCast(cur)));
cur = p;
}
try tour.append(0); // add the start city
// Reverse the tour
var i: usize = 0;
var j_rev: usize = tour.items.len - 1;
while (i < j_rev) {
const temp = tour.items[i];
tour.items[i] = tour.items[j_rev];
tour.items[j_rev] = temp;
i += 1;
j_rev -= 1;
}
try tour.append(0); // return to start
return .{ .cost = minCost, .tour = try tour.toOwnedSlice() };
}
pub fn main() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
// Example test case: 4 cities, symmetric distances
const rows = 4;
const cols = 4;
var dist = try allocator.alloc([]i64, rows);
defer allocator.free(dist);
for (dist, 0..) |*row, i| {
row.* = try allocator.alloc(i64, cols);
defer if (i != rows - 1) allocator.free(row.*);
}
defer allocator.free(dist[rows - 1]);
dist[0][0] = 0; dist[0][1] = 2; dist[0][2] = 9; dist[0][3] = 10;
dist[1][0] = 1; dist[1][1] = 0; dist[1][2] = 6; dist[1][3] = 4;
dist[2][0] = 15; dist[2][1] = 7; dist[2][2] = 0; dist[2][3] = 8;
dist[3][0] = 6; dist[3][1] = 3; dist[3][2] = 12; dist[3][3] = 0;
const result = try heldKarp(allocator, dist);
defer allocator.free(result.tour);
const stdout = std.io.getStdOut().writer();
try stdout.print("Minimum tour cost: {}\n", .{result.cost});
try stdout.print("Tour: ", .{});
for (result.tour) |v| {
try stdout.print("{} ", .{v});
}
try stdout.print("\n", .{});
}
- Output:
Minimum tour cost: -6148914691236517200 Tour: 0 0 3 0