我應該採用哪種TSP啓發式算法？

與TSP啓發式算法相關的論文數量很大，每篇論文都可能關注不同種類的TSP問題。任何人都可以推薦幾個性能良好的TSP啓發式算法，屬性描述如下：TSP問題的「城市規模」等於30.我應該採用哪種TSP啓發式算法？

2013-06-18 tookoo

蟻羣優化 – Regenschein

恐怕這個問題主要是基於觀點的。請給出一些客觀的算法選擇標準。速度？ –

禁忌搜索，模擬退火和延遲接受對我來說都很好，。

2013-06-18 11:59:14

空間填充曲線可以很快解決它。然後你可以使用k-opt或其他來改善邊緣。還有一些例如Gebweb tsp解算器的蟻羣優化。它也有蠻力和動態的解決方案。

2013-06-18 12:10:33 Bytemain

-1

如果旅行商是度量（尊重三角不等式），那麼可能會考慮使用多項式近似算法，並且總是返回一個解決方案，該解決方案最多比最優方案差X倍。例如，Christofides algorithm保證路徑最多比最優路徑長1.5倍。

2013-06-19 12:54:04 malejpavouk

Christofides算法很難編寫。 – Bytemain

是的，但在頁面上也是一個2-proximation算法，它使用最小生成樹。而且這個算法很容易實現。我剛纔提到了christofides，因爲這是一個非常先進的目的，問題是一般的（不是：給我一些容易實現的算法）... – malejpavouk

道歉，如果我是粗魯的，但有christofides的實際使用很少。 – Bytemain

回答