是否有一種算法可以在多項式時間內找到k-tsp（旅行商）的最優值？

我讀this文章，它建議（第1025頁最後一段）有一個多項式時間算法來找到使用二分搜索的最優k-tsp問題。使用二進制搜索將建議存在一個算法，用於檢查解決方案是否存在與cost<X和此算法用於二進制搜索。我爲此搜索了一下，我發現的唯一算法是非確定性算法（這非常不重要），但顯然我正在尋找確定性算法。是否有一種算法可以在多項式時間內找到k-tsp（旅行商）的最優值？

我有興趣在此學習之用，

任何幫助/鏈接將不勝感激。

編輯

我指的是尋找最佳解決方案的價值，而不是要找到解決方案本身。

來源

2011-12-22 Daniel

TSP不是一個k-TSP的特例，其中k =圖中節點的數量？ – soulcheck 2011-12-22 09:31:42

@soulcheck：是的，這是真的 – Daniel 2011-12-22 09:37:07

由於TSP是k-TSP的特例，其中k =圖中節點的數量。如果您有關於圖的大小的多項式「什麼是最便宜的k-TSP路線」的解決方案，那麼您將有一個多項式解決方案來解決TSP的決策問題版本，這意味着P = NP。

所以答案是否定的。針對決策問題和優化版本的確定性多項式算法（它們本質上是相同的）k-TSP不存在（還）。

來源

2011-12-22 09:41:13 soulcheck

我在詢問如何找到最佳解決方案的價值，而不是找到實際的最佳解決方案。所以你的論點不適用於此。 – Daniel 2011-12-22 11:25:03

@Daniel這是TSP的決策問題版本。如果您對「圖表中最便宜的TSP路線是什麼」這個問題有了答案，那麼您可以回答「是否存在比x便宜的TSP路線」。編輯答案以更好地反映它。 – soulcheck 2011-12-22 11:37:37

這是真的。但相反不是（除非我失去了一些東西），如果我知道最佳解決方案的價值是什麼，並不意味着我知道實際的解決方案。 – Daniel 2011-12-22 20:26:58

您提到的論文提出了一個多項式時間近似算法爲定向k-TSP問題。

近似算法是那些保證產生解決方案與最佳解決方案價值有限的偏差。有NP-Hard問題的多項式時間近似算法的例子：在時間O（n 3）中，Christofides Algorithm產生度量TSP問題的解，其值至多是最優解的值的3/2。

來源

2016-09-16 15:45:45

是否有一種算法可以在多項式時間內找到k-tsp（旅行商）的最優值？

回答

相關問題