如何獲得的近似解得到的最短路徑經過的所有節點會

是否有人知道的算法或東西做如何獲得的近似解得到的最短路徑經過的所有節點會

所以我有一個弧形的連接節點，我必須找到一個解決方案，以找到一個近似最短路徑覆蓋所有節點。（我只能訪問他們一次）

它必須是一個近似的路徑，因爲它會採取太多的時間來獲得的最短路徑

謝謝您的回答:)

（我必須這樣做在Java）

來源

2012-11-24 Lol Pallau

這被稱爲[旅行推銷員問題]（http://en.wikipedia.org/wiki/Travelling_salesman_problem） –

@JanDvorak - 它可能實際上是[哈密爾頓路徑問題]（https：//en.wikipedia .ORG /維基/ Hamiltonian_path_problem）;他從不說他需要回到原始節點。 –

這些問題統稱爲_Graph Theory_，並且存在大量問題，其中包括衆所周知的解決方案。這已經介紹給你了嗎？ –

是的，有。該方法被稱爲「遺傳優化」，其步驟如下 1.找到解決方案，即訪問每個節點一次的路徑。 2.選擇K的靠近節點隨機：N1，N2..Nk：X-> N1 - > .. NK->ý 3.檢查以查看是否有從X到Y使用節點N1..Nk較短的路徑 4.更換路徑X - 通過較短的溶液*>ý 5.轉到2

ķ必須小（5或更小），這樣就可以很容易地找到較短的組合

的好處約您可以隨時停止並使用現有的解決方案。一個改進是隨機選擇一個更大的k。

來源

2012-11-24 12:23:58 alzaimar

這與遺傳學有什麼關係？你所描述的是K-opt（它本身並不是一個壞算法） –

或者它的一個不好的版本。如果你總是選擇K _adjanced_節點，那麼你不能做很多優化 –

我知道這個解決方案來自delphi。作者稱其爲「使用遺傳算法進行優化」。如果我谷歌它，我覺得這種類型的解決方案。如果你把它稱爲'K-opt'（或者它甚至是唯一合法的官方名稱）好。然後我學到了一些新東西。 – alzaimar

這就是所謂的Travelling Salesman Problem和一個合理和快速的近似是總是訪問最近的未訪問的節點，然後重試幾個其他的起始位置相同。通常情況下，這會讓您非常接近最佳解決方案。

另一種算法是首先構造圖的最小生成樹，然後刪除重複的節點。這保證了次優性的某個上限（在歐幾里德情況下不超過兩倍）

另一種算法是從前三個節點開始，然後以某種順序添加下一個節點（最初，按x座標排序，按照距離中心的距離排序......），同時保持路徑儘可能短，通過分割現有邊（或在最後添加新的邊）。

一旦你有一個解決方案（哪怕是個壞），你可以通過K-選擇改進：反覆挑選ķ隨機邊緣，完全刪除它們，找到重新連接新的端點的最佳途徑。 K-opt的一個變體是Lin-Kerningham啓發式方法，該方法以三步選擇步驟（以某種順序）交替執行2選擇步驟，其中三個邊中的兩個總是相鄰的。

如果最邊緣的丟失或很長（兩個節點之間的distaces沒有形成指標），那麼你有問題。我們只是說它是NP完全的，確定如果這樣的路徑甚至存在，如果有缺失的邊緣。

來源

2012-11-24 12:28:24

一個非常快速的近似是訂購沿空間填充曲線的頂點。空間填充曲線減小了維度並保留了一些空間信息。嘗試旅行商推銷員問題的摩爾曲線，因爲它是4條希爾伯特曲線的副本，因此起點和終點彼此相鄰。但繪製起來要貴一些。

enter image description here

來源

2012-11-24 14:17:04 Bytemain

+1。不過，不確定它實際上比最接近的第一快。 –

用希爾伯特曲線更新一些tsp的例子。綠色的形狀基本上是一個茶匙。 – Bytemain

@JanDvorak：你的意思是http://en.wikipedia.org/wiki/Nearest_neighbour_algorithm？我總是把這與http://en.wikipedia.org/wiki/Closest_pair_of_points_problem混淆。這不是這個消費者嗎？ – Bytemain

如果你沒有自己實現算法所需的信息，你可能想看看JGraphT。它有一個算法實現Hamiltonian Cycles。

來源

2012-11-24 14:58:22

太糟糕了，當鏈接失效時，這個答案將毫無用處。僅鏈接答案應該是評論。 –

如何獲得的近似解得到的最短路徑經過的所有節點會

回答

相關問題