I am trying to implement the Held-Karp algorithm for the Traveling Salesman Problem by following this pseudocode:

(which I found here: https://en.wikipedia.org/wiki/Held–Karp_algorithm#Example.5B4.5D )

I can do the algorithm by hand but am having trouble actually implementing it in code. It would be great if someone could provide an easy-to-follow explanation.

I also don't understand this:

I thought this part was for setting the distance from the starting city to it's connected cities. If that was the case, wouldn't it be it C({1}, k) := d1,k and not C({k}, k) := d1,k? Am I just completely misunderstanding this?

I have also heard that this algorithm does not perform very well past about 15-20 cities so for around 40 cities, what would be a good alternative?

CodePudding user response：

Held-Karp is a dynamic programming approach.

In dynamic programming, you break the task into subtasks and use "dynamic function" to solve larger subtasks using already computed results of smaller subtasks, until you finally solve your task.

To understand a DP algorithm it's imperative to understand how it defines subtask and dynamic function.

In the case of Held-Karp, the subtask is following:

For a given set of vertices S and a vertex k   (1 ∉ S, k ∈ S)

C(S,k) is the minimal length of the path that starts with vertex 1, traverses all vertices in S and ends with the vertex k.

Given this subtask definition, it's clear why initialization is:

C({k}, k) := d(1,k)

The minimal length of the path from 1 to k, traversing through {k}, is just the edge from 1 to k.

Next, the "dynamic function".

A side note, DP algorithm could be written as top-down or bottom-up. This pseudocode is bottom-up, meaning it computes smaller tasks first and uses their results for larger tasks. To be more specific, it computes tasks in the order of increasing size of the set S, starting from |S|=1 and going up to |S| = n-1 (i.e. S containing all vertices, except 1).

Now, consider a task, defined by some S, k. Remember, it corresponds to path from 1, through S, ending in k.

We break it into a:

• path from 1, through all vertices in S except k (S\k), which ends in the vertex m   (m ∈ S, m ≠ k):  C(S\k, m)
• an edge from m to k

It's easy to see, that if we look through all possible ways to break C(S,k) like this, and find the minimal path among them, we'll have the answer for C(S, k).

Finally, having computed all C(S, k) for |S| = n-1, we check all of them, completing the cycle with the missing edge from k to 1:  d(1,k). The minimal cycle is the final result.

Regarding:

I have also heard that this algorithm does not perform very well past about 15-20 cities so for around 40 cities, what would be a good alternative?

Held-Karp has algorithmic complexity of θ(n²2ⁿ). 40² * 2⁴⁰ ≈ 1.75 * 10¹⁵ which, I would say, is unfeasible to compute on a single machine in reasonable time.

As David Eisenstat suggested, there are approaches using mixed integer programming that can solve this problem fast enough for N=40.

For example, see this blog post, and this project that builds upon it.