我正在嘗試為旅行商問題實作 Dijkstra 演算法的一個版本，我找到了這篇論文：https : //www.researchgate.net/figure/Dijkstras-algorithm-for-many-targets-with-a-pruning-heuristic -An-upper-bound-B-for-d-v_fig2_257428759
我理解演算法，但我對這個偽代碼中“免費”的含義感到困惑。誰能給我解釋一下？
即在以下幾行中：
如果你有空，那么 STOP fl
如果 v 是空閑的，那么 B = min{c, b} fl
多目標 Dijkstra 演算法的啟發式演算法（偽代碼）
uj5u.com熱心網友回復：
您鏈接到的論文似乎沒有處理旅行商問題，而是有二分匹配：
該問題的兩個版本都可以通過在派生圖中求解 n,n=max(|A|,|B|)、單源多目標最短路徑 (SSMTSP) 問題來解決，參見第 4 節。
甲free節點指的是沒有與在二分圖的任何其他節點相匹配的節點。這在鏈接論文的第 4 節（頁面標簽 87）中有所說明，腳注5：
如果 M 中沒有邊與該節點相關，則該節點是空閑的。
M 定義為需要在上一頁計算的匹配。
這個演算法似乎只對這個匹配問題有用，這需要你多次運行它。這只是對二分匹配的這些多次運行的改進，它不是一個獨立的演算法。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/353915.html
上一篇：展開樹洗掉