2
A
回答
11
不,它被認爲是NP-Hard。
如果你找到一個,告訴我(當然在祕密的),我們會共同富裕:-)
我知道維基百科可以經常出錯,但你會發現在TSP有趣的頁面:
4
大概不會。它是NP-hard。
3
如果NP = P那麼答案是肯定的,可以用多項式時間完成。如果NP ≠ P,那麼答案是否定的,它不能在多項式時間內完成。 NP = P與NP ≠ P是一個懸而未決的問題,但我懷疑你會發現,那些對這個問題非常熟悉的代表性樣本將會有更多的人相信NP = P的人。
2
不!!,以多項式時間。
是的,有一個確切的算法。
相關問題
- 1. 旅行推銷員問題
- 2. 使用A *解決旅行推銷員
- 3. 旅行推銷員
- 4. 哪裏可以找到一套硬旅行推銷員問題(已知解決方案/近似值)?
- 5. Neo4J - 旅行推銷員
- 6. 旅行推銷員:矩陣和旅遊
- 7. 旅行推銷員啓發式
- 8. 關於旅行推銷員問題和測試集的競爭
- 9. 旅行推銷員的提示
- 10. F#旅行推銷員的表現
- 11. 旅行推銷員的交叉算法?
- 12. 旅行推銷員使用Pyomo
- 13. 索引出差旅行推銷員
- 14. 簡體中文Prolog旅行推銷員
- 15. 旅行推銷員,包括通過城市旅行
- 16. 解決旅行推銷員一旦你知道最短路線的距離
- 17. 最優和有效的方法來解決多旅行推銷員的一個非常簡單的變種
- 18. 二次公式解決方案問題
- 19. 使用旅行推銷員求解器來確定哈密頓路徑
- 20. 蠻力旅行推銷員:爲什麼Haskell比C慢得多?
- 21. 使用Neo4j解決TSP問題
- 22. 使用backtracking解決TSP問題
- 23. 純CSS解決方案來推動的3項中間向下
- 24. 命名空間問題,單個解決方案中的多個項目
- 25. 在多項目中鏈接問題Visual Studio 2005解決方案
- 26. 爲golang旅遊的簡單解決方案的WebCrawler行使
- 27. 運行VS2008解決方案時運行時錯誤;解決方案是建立精細
- 28. 最佳解決TSP問題的最快方法
- 29. 並行動態規劃旅行推銷員
- 30. 並行旅行推銷員計劃使用分支和綁定
不要問,你可能已經讀過維基百科文章的第一句話。 – Tim 2011-03-25 14:23:30
這可能應該移動到http://cstheory.stackexchange.com/ – Ither 2011-03-25 14:23:35
@ther:Nope。關於cstheory的話題。 – 2011-03-25 16:06:55