旅行商TSP：蠻力算法改進

根據wiki將需要（N-1）！計算與N個城市的遊覽。我發現了一個更好的方法來做到這一點，但我無法用數學來計算我改進了多少。我可以告訴你，在我的家用電腦上，我能夠在不到1個小時內解決20個城市的地圖。 20！ = 2.43290200e + 18。這是我做的：旅行商TSP：蠻力算法改進

當使用brout算法搜索N個城市的路線時（讓我們給他們一個名字：City（1），City（2），City（3）... City（N））（1），城市（2），城市（3），城市（4）...城市（N）以及之後的一段時間，這個城市（1），城市（3）），城市（2），城市（4）...城市（N）。我聲稱第二次計算是不必要的。如果我只計算City（4）... City（N）的最短路線，我可以用它來進行第二次計算，並確定哪條路線更好。

使用這個技巧，我可以通過下列方法減少我爲K城市做的計算次數：（N - k）這是可以讓誰成爲第一個城市的選項數量，乘以（N - K - 1）！這是我必須選擇其餘城市的選項的數量，並且減去第一次，我需要執行完整的計算。所以它會是（N - K）！你需要將所有K的總和從k = 3到k = N - 2加起來。

這就是我去的地方（這不是很遠）......我希望你能夠幫我計算一下。

來源

2013-10-09 Ilya_Gazman

我覺得這是一個已知的伎倆，以提高茶匙，以便它可以處理1名或2個以上的城市進行比較的爲O（n^2 * 2^n）算法。介意在這裏發佈你的代碼？ – noooooooob

@noooooooob也發佈它[這裏]（http://cs.stackexchange.com/questions/16076/traveling-salesman-heldkarp-algorithm-big-improvement） –

存儲和重複使用已經計算的結果是動態規劃背後的基本思想，因爲TSP有動態編程算法，運行時間爲O[(N^2)*(2^N)]，這會比您的算法產生更快的結果（您將能夠解決分鐘內25個頂點...）問題

參見：Dynamic Programming for the TSP

來源

2013-10-09 14:57:24

我不認爲這是解決20個頂點與O [（ N^2）*（2^N）]是可能的。 2^20 * 20 * 20 =〜400M。當我使用我的算法時，20個頂點小於100K，並且需要幾乎小時。我知道它少於100K，因爲我計算了城市間比較的次數。 –

在一臺普通計算機上執行400M基本操作應該只需不到一秒鐘，您只能執行100K操作，並且需要將近一個小時，因此您應該檢查運行時計算。 –

是的，但比較城市並沒有什麼基礎。當然，原子動作可以在不同的算法之間有所不同，但我認爲用你提供的算法去20是不可能的。 –

旅行商TSP：蠻力算法改進

回答

相關問題