我正在嘗試按照以下偽代碼為旅行商問題實作 Held-Karp 演算法：
（我在這里找到：https : //en.wikipedia.org/wiki/Held–Karp_algorithm#Example.5B4.5D）
我可以手動完成演算法，但在代碼中實際實作它時遇到了麻煩。如果有人可以提供易于理解的解釋，那就太好了。
我也不明白這個：
我認為這部分是用于設定從起始城市到其連接城市的距離。如果是這樣的話，C({1}, k) := d1,k不是C({k}, k) := d1,k嗎？我只是完全誤解了這一點嗎？
我也聽說這個演算法在大約 15-20 個城市后表現不佳，所以對于大約 40 個城市，什么是一個好的選擇？
uj5u.com熱心網友回復：
Held-Karp 是一種動態規劃方法。
在動態編程中，您將任務分解為子任務，并使用“動態函式”使用較小子任務的已計算結果解決較大的子任務，直到最終解決您的任務。
要理解 DP 演算法，必須了解它如何定義子任務和動態函式。
在 Held-Karp 的情況下，子任務如下：
對于給定的一組頂點
S和一個頂點k(1 ? S,k ∈ S)
C(S,k)是從 vertex 開始1，遍歷所有頂點S并以該 vertex 結束的路徑的最小長度k。
鑒于此子任務定義，很明顯為什么初始化是：
C({k}, k) := d(1,k)
從路徑的最小長度1來k，穿越通過{k}，僅僅是從邊緣1到k。
接下來是“動態函式”。
附帶說明，DP 演算法可以寫為自頂向下或自底向上。這個偽代碼是自底向上的，這意味著它首先計算較小的任務，然后將它們的結果用于較大的任務。更具體地說，它按照集合大小的增加順序計算任務S，從開始|S|=1到到|S| = n-1（即S包含所有頂點，除了1）。
現在，考慮一個由 some 定義的任務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).
最后，在計算完所有C(S, k)for 后|S| = n-1，我們檢查所有這些，用缺失的邊 from kto 1: 完成回圈d(1,k)。最小周期是最終結果。
關于：
我也聽說這個演算法在大約 15-20 個城市后表現不佳，所以對于大約 40 個城市，什么是一個好的選擇？
Held-Karp 的演算法復雜度為 θ(n22 n )。402 * 2 40 ≈ 1.75 * 10 15，我想說，在合理的時間內在一臺機器上計算是不可行的。
正如 David Eisenstat 所建議的那樣，有一些使用混合整數規劃的方法可以足夠快地解決 N=40 的問題。
例如，請參閱此博客文章以及基于它構建的此專案。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/355676.html