旅行時間最小化算法

我正在尋找創建算法的指導，以最小化一組旅行者到達一組固定目的地的總旅行時間。旅客並不都是在同一個地方開始的，但是每個旅行目的地都必須由旅行者訪問才能被認爲是完整的（類似於TSP）。（x，y）的值是從開始位置x到目的地y的移動距離，然後執行某種矩陣運算/算法選擇值使得每行/列只有一個值從中選擇，並且這些值的總和被最小化。有沒有人有這種事情的算法的背景？根據意見旅行時間最小化算法

澄清：

每個目標必須通過一個旅客參觀。所有旅客不必訪問所有的目的地。
如果有比遊客更多的目的地，旅客應只需瞄準擊中每一個（仍減少旅行時間）任意一個目的地，然後重複這個問題，但是有兩個少目的地。
目的地和旅客的最大數量應該在30個目的地和10個旅客，所以不是一個龐大的數字。我想儘可能避免純粹的暴力。

來源

2013-04-30 alexgerst

因此，每個旅行者都必須前往每個目的地（這對所有旅客來說都很普遍）？ – unkulunkulu 2013-04-30 23:38:32

你的用例是什麼？它需要達到多少最佳？什麼時間複雜，什麼空間複雜？您需要處理的旅客和目的地的最大數量是多少？所有這些將會改變算法需要如何'花哨' – Patashu 2013-04-30 23:39:28

試圖將標題編輯爲'時間旅行最小化算法'... – Undo 2013-04-30 23:43:41

看看在Floyd-Warshall algorithm和Merge Sort algorithm。

考慮到訪問地點數（頂點數）爲V且旅客人數爲T，如果應用Floyd-Warshall算法，它應該爲您提供圖中頂點對之間的最短路徑，其中O （V^3）複雜性。

然後，您可以按升序對最短路徑的長度進行排序，這將成爲具有O（V lg V）複雜度的操作。

由於您按順序應用這些算法，因此您仍然處於O（V^3）的整體複雜度。

因爲在第一次迭代中，您會訪問T個頂點，但是V大於T，所以您將不得不執行第二個K階次，其中K是天花板（V/T）訪問。在下一次迭代中，您將從計算中移除已訪問頂點並對剩餘距離（您在上一步中已經找到的）進行排序，然後繼續從T旅行者的新位置訪問它們。

您可能通過爲每個頂點選擇最小距離來獲得更好的結果，因此您選擇的下一個頂點是最接近的頂點。因此，您的整體複雜性將開始看起來像O（V^3）+ K x O（V lg V），我認爲這往往趨近於O（V^3）。

這些只是一些想法，讓你開始。

來源

2013-05-01 00:06:03

Floyd-Warshall是一個很酷的算法！ – Patashu 2013-05-01 00:22:51

+ 1 for floyd。雖然令人着迷，但我不認爲合併排序會有很大幫助。 – glh 2013-05-02 12:15:42

我添加了合併排序以允許選擇下一個最小距離。關於第二個想法，使用[min-heap]（http://en.wikipedia.org/wiki/Heap_（data_structure））來存儲每個頂點的距離將同樣適用，並且可能會簡化算法的整體結構，同時保留複雜性一樣。 – 2013-05-03 07:22:31

如果我明白你的問題，我懷疑旅客的數量與快速找到解決方案有關。所以我們通過一些啓發式解決基本的旅行推銷員問題，然後在這個週期內移動旅行者。

有各種建設性的方法和各種迭代改進方法記錄。幾個例子如下（從學術界到漂亮的動畫實例）：

來源

2013-05-01 00:02:56

你是說你的方法是1）像TSP一樣解決2）對於你的路徑上的每個最高成本邊緣，當你仍然有旅行者時，通過在遠節點上放置一個旅行者'交叉'它並讓它繼續路徑？因爲這會忽略利用能夠忽略N個最高成本邊緣的解決方案，對嗎？（雖然它會很好） – Patashu 2013-05-01 00:04:52

由於旅行推銷員問題運行在階乘複雜度上，因此它可能會迅速超出在CPY上運行的明智度。幸運的是，新款電腦都配備了完美的圖形卡，可以運行比CPU快幾百倍的問題。

我發佈了一個相當簡單的TSP here解決方案的分析和比較，其中包括運行在NVIDIA圖形卡上的C＃代碼。還需要下載CUDAfy庫以直接運行代碼。

使用我的Quad i7,16GB筆記本電腦和NVIDIA GEFORCE GT圖形卡，我報告了11個城市的性能提升，幾乎大約70倍（14.7秒到0.2秒），將問題從單個CPU內核移植到GPU。

CUDA Tuning項目中的代碼是MIT許可證下的，因此免費使用歸因。

來源

2013-05-01 02:21:08

旅行時間最小化算法

回答

相關問題