沒有三角形不等式的TSP求解器

我對解決（小）網格圖的TSP感興趣。任何類型的圖書館都會爲我做，但這似乎比預期的更難。我嘗試了一些我在那裏找到的求解器（包括協調器），但是當三角不等式不成立時，它們似乎都有問題。沒有三角形不等式的TSP求解器

例如，我想在求解以輸出遊（0，1，2，1，4，3），用於下面的曲線圖（與單元邊緣權重）：

0-1-2 
| | 
3-4

在這個特定的我告訴協調人，邊緣（2,4）的重量爲1000，協調人立即產生了成本爲1004的旅程（0,1,2,4,3）。這顯然不是我正在尋找的。理想情況下，Java中會有一些簡單的（可能是蠻力的）實現，但任何有效的實現都會實現。任何人都可以指向我的代碼，或者我真的必須自己去實現這個工具嗎？

編輯：另外，重要的是我得到一個確切的解決方案，而不是一些近似值。

Edit2：確實，這似乎不是TSP。我試圖找到的是一個訪問所有頂點的最短閉合步行。

2012-02-28 Dino

您確定您正確應用Concorde？它應該是對稱TSP問題的一個*精確解* ... – 2012-02-28 09:07:41

@ Li-aungYip：協和實際上是在給出最優的TSP解決方案。問題在於OP期待的解決方案不是有效的TSP旅程。詳情請參閱我的回答。 – NPE 2012-02-28 09:09:03

我明白了。事實上，考慮到這個圖，我不認爲有任何其他閉環週期訪問所有節點。（關鍵詞：關閉。2-1-0-3-4重4，並且訪問所有節點，但沒有關閉。） – 2012-02-28 09:12:50

你的困難不是三角形的不平等。難度與您預期的解決方案不適用於TSP之旅有關。

TSP尋求Hamiltonian cycle;也就是說，一次只訪問每個頂點的循環。你的解決方案，(0, 1, 2, 1, 4, 3)，訪問頂點1兩次。

如果這是您尋求的解決方案，那麼您試圖解決的問題不是旅行推銷員問題。

2012-02-28 09:00:07 NPE

感謝您指出了這一點！所以我想我應該首先計算圖中所有頂點之間的距離矩陣，然後求解TSP。這應該給我一個在我的網格中最佳旅程的長度。正確？ – Dino 2012-02-28 09:14:31

@Duh：坦率地說，我不明白這將如何幫助您將問題轉化爲TSP。無論如何，我認爲有用的第一步是找出你正在尋找的是什麼（訪問每個頂點的最短週期*至少*一次？） – NPE 2012-02-28 09:18:28

是的，那正是我正在尋找的。在這種情況下，將問題轉移到精確距離的完整圖表可以解決問題： - 很容易證明最佳解決方案的長度是相等的 - 根據最佳方法很容易構建巡視TSP巡視在完整的圖表中 – Dino 2012-02-28 09:22:39

回答