A *搜索爪哇 - TSP

可能重複：
Implementation of A Star (A*) Algorithm in Java A *搜索爪哇 - TSP

對於一個任務，我必須執行，以解決旅行商問題的一些搜索算法，我明白的問題並且我理解算法是如何工作的，但我根本不知道如何實現它（我的Java不是很好），但這應該是非常簡單的部分，但不幸的是，我對Java的瞭解還不足以應用我所知道的關於算法。

因此，我想知道是否有人可以提供一些提示或提示如何開始使用這個或甚至一些好的鏈接來閱讀，如果有一個更容易啓動，我也必須實現一些其他算法與id很高興去那個！我已經看過這裏了，但似乎無法找到任何有關的東西：/

任何幫助，非常感謝！謝謝

來源

2012-12-07 thrash

有多少個節點？ – nhahtdh

基本的java教程並不難或者特別冗長，並且與一個類似JUNG的庫或類似的庫一起幫助您處理事物（節點，邊緣等）的圖形對象方面，您應該快速啓動和運行。尋找專注於數據結構和算法的教程，您應該看到很多示例來幫助您。 – Quetzalcoatl

我想我需要使用各種節點才能比較所有的算法，我已經給出了一些文本文件來測試。哦，我在這裏看到了關於A *的其他東西，但沒有一個與TSP似乎相關，或者如果它是那麼我不知道如何實現它在TSP上工作 – thrash

我不是專家，但我不認爲A *可以用來解決旅行商問題。我相信你知道TSP是NP難的，所以確切的解決方案相當複雜，並不適用於每種情況。我知道（並用於）近似解決方案的最簡單方法是所謂的「模擬退火」，它是一種隨機方法（即隨機！）。

這個想法很簡單。您將這些點組織成一個列表，這個列表表示所有節點之間的路徑（這稱爲「遊覽」）。計算遊覽時間並保存長度。然後您選擇一個隨機子列表並簡單地將其顛倒。計算新的長度。如果新的列表較短，則保留它，否則丟棄它。只需重複這些步驟100/1,000/10,000,000次（取決於點的數量），你就會有一個合理的近似值。

實施例，想象有5個點（僞碼）...

List tour = [e, b, a, d, c] 
int len = tourLength(tour) 
List newTour = [e, b] + [d, a] + [c] // a and d have been reversed 
int newLen = tourLength(newTour) 
if(newLen < len) { 
    tour = newTour 
}

對於10分，100次迭代應產生了良好的效果。

來源

2012-12-07 17:13:33 Zutty

有少量節點的確切解決方案DP。 – nhahtdh

好點。編輯我的答案。 – Zutty

我可以問問爲什麼a和d是相反的嗎？ – thrash

A *搜索爪哇 - TSP

回答

相關問題