algorithm - 您能帮忙解释一下这个 Held-Karp TSP 伪代码吗？

Question

我正在尝试通过以下伪代码实现旅行商问题的 Held-Karp 算法:

(我在这里找到:https://en.wikipedia.org/wiki/Held%E2%80%93Karp_algorithm#Example.5B4.5D)

我可以手动执行该算法，但在代码中实际实现它时遇到困难。如果有人可以提供易于理解的解释，那就太好了。

---

我也不明白这个:

我认为这部分是为了设置从起始城市到它所连接的城市的距离。如果是这样的话，那不是 C({1}, k) := d1,k 而不是 C({k}, k) := d1,k ？我完全误解了这一点吗？

我还听说该算法在超过大约 15-20 个城市时表现不佳，因此对于大约 40 个城市，什么是一个好的替代方案？

Answer 1

Held-Karp 是 dynamic programming方法。

在动态编程中，您将任务分解为子任务，并使用“动态函数”使用较小子任务的已计算结果来解决较大的子任务，直到最终解决您的任务。

要理解 DP 算法，必须了解它如何定义子任务和动态函数。

对于 Held-Karp，子任务如下:

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.

鉴于此子任务定义，初始化的原因很清楚:

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

从 1 到 k(穿过 {k})的路径的最小长度就是从 1 开始的边 到 k。

---

接下来是“动态函数”。

附注，DP算法可以写成top-down or bottom-up 。该伪代码是自下而上的，这意味着它首先计算较小的任务，然后将其结果用于较大的任务。更具体地说，它按照集合 S 大小递增的顺序计算任务，从 |S|=1 开始一直到 |S| = n-1(即 S 包含除 1 之外的所有顶点)。

现在，考虑一个由一些 S, k 定义的任务。请记住，它对应于从 1 到 S、以 k 结尾的路径。

我们将其分解为:

• 从 1 出发，经过 S 中除 k (S\k) 之外的所有顶点的路径，结束在顶点 m 中(m ∈ S, m ≠ k):C(S\k, m)
• 从m到k的边

很容易看出，如果我们像这样检查所有可能的破坏C(S,k)的方法，并找到其中的最小路径，我们就会得到C(S，k)。

---

最后，计算出 |S| 的所有 C(S, k) = n-1，我们检查所有这些，完成从 k 到 1 的缺失边的循环:  d(1,k) 。最小周期即为最终结果。

---

关于:

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 的算法复杂度为 θ(n²2ⁿ)。 40² * 2⁴⁰ ≈ 1.75 * 10¹⁵ 我想说，在合理的时间内在单台机器上计算是不可行的。

正如 David Eisenstat 所建议的，有一些方法使用 mixed integer programming对于 N=40 来说可以足够快地解决这个问题。

例如，请参阅this blog post ，和this project建立在它的基础上。