你能帮忙解释一下这个 Held-Karp TSP 伪代码吗？
Can you help explain this Held-Karp TSP Pseudocode?
我正在尝试通过以下伪代码实现旅行商问题的 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 个城市，什么是好的替代方案？
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| = n-1 的所有 C(S, k)，我们检查所有这些，完成从 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²2n)。 40² * 240 ≈ 1.75 * 1015 我想说，在合理的时间内在一台机器上计算是不可行的。
正如 David Eisenstat 所建议的，有一些使用 mixed integer programming 的方法可以足够快地解决 N=40 的问题。
例如，请参阅基于它的 this blog post, and this project。
我正在尝试通过以下伪代码实现旅行商问题的 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 个城市，什么是好的替代方案？
Held-Karp 是一种 dynamic programming 方法。
在动态规划中，您将任务分解为子任务，并使用“动态函数”使用较小子任务的已计算结果来解决较大的子任务，直到最终解决您的任务。
要理解 DP 算法，必须理解它如何定义子任务和动态函数。
对于 Held-Karp，子任务如下：
For a given set of vertices
Sand a vertexk(1 ∉ S,k ∈ S)
C(S,k)is the minimal length of the path that starts with vertex1, traverses all vertices inSand ends with the vertexk.
鉴于此子任务定义，很明显为什么初始化是：
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| = n-1 的所有 C(S, k)，我们检查所有这些，完成从 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²2n)。 40² * 240 ≈ 1.75 * 1015 我想说，在合理的时间内在一台机器上计算是不可行的。
正如 David Eisenstat 所建议的，有一些使用 mixed integer programming 的方法可以足够快地解决 N=40 的问题。
例如，请参阅基于它的 this blog post, and this project。