算法優化 - 多點之間的最短路徑

問題：我有很多點的集合。這些點中的每一個都有一個列表，其中包含已經計算和存儲的其他點的參考點。我需要確定從原點開始並通過特定數量的點到達任何目的地的最短路線。算法優化 - 多點之間的最短路徑

例如：我正在度假，我住在一個特定的城市。我正在進行一次旅行，以查看任何四個城市，並且我想盡可能以最短的距離旅行。我不能一次訪問同一個城市。

當前解決方案：現在我只是手動迭代每種可能性並存儲最短路徑。這工作，但感覺效率低下。此外，這個問題最終會擴展到包括從多個原點到多個目標點的搜索，所以我認爲這可能會擴大搜索空間。

搜索最短路線的更好方法是什麼？

來源

2009-10-02 Chris Douglass

這是一個定向或雙向圖嗎？我不知道。 –

這裏的一些答案（TSP，Floyd-Warshall，廣度優先，分支和界限）源於對這個問題的非常不一致和矛盾的解釋，所以我傾向於認爲這裏的問題不是很好地表達。 – Juliet

讓我簡單地重述一下：一個例子是我正在度假，而我住在一個城市。我想看到從我的任何四個城市開始，我想盡可能走最短的路程。我不能一次訪問同一個城市。 –

回答更新後的文章，您檢查每種可能性的解決方案是最佳的（至少沒有人發現更好的算法到目前爲止）。是的，這是一個旅行推銷員，他的本質不是觸及每個城市，而是觸摸每個城市一次。如果您不想搜索可能的最佳解決方案，可能會發現使用更快速的啓發式算法很有用，但是可以與理想解決方案的差異有限。

對於未來的回答者：Floyd-Warshall algorithm和弗洛伊德，像所有的變化是不適用在這裏。

來源

2009-10-02 20:34:08

有趣的事實：O（N^5）> O（N！）直到N = 8 :) – Juliet

謝謝。我已經通過找到最短的個人路徑的最終解決方案來優化它，然後向上移動一個級別並搜索，然後移動到另一個級別（等等），我想這是一個深度優先搜索？ –

這可以稱爲深度優先*遍歷*，而不是*搜索*。*搜索*旨在訪問每個*節點*，而您的算法旨在訪問每個*路徑*，因此成本更高。 –

This sounds Traveling Salesman-esque？一種解決方案是使用諸如演化算法之類的優化技術。目前您正在進行詳盡的搜索，搜索速度非常快。但我認爲這幾乎是一個旅行推銷員的問題，如果不是幾個世紀的話，它已經被解決了幾十年，而且這種攻擊有幾種可能的方式。 Google是你的朋友。

來源

2009-10-02 20:19:05 zenna

它不是TSP，因爲你可以通過相同的點，然後一次。 –

我認爲TSP參與知道需要觸及的每一點？在我的情況下，沒有具體的點需要被包括在內，只要是從原點開始的最短路徑的任何點 –

@Shay：有很多TSP的味道，包括允許用戶多次訪問同一個頂點的味道 – Juliet

在一般你應該嚴格壞變種... 我認爲你應該使用Branch_and_bound方法的一些變化 http://en.wikipedia.org/wiki/Branch_and_bound

來源

2009-10-02 20:28:40 Max

++是的，這是一個樹搜索優化問題，所以分支和邊界適用於它，它可以是寬度優先或深度優先。 –

要麼bredth第一搜索作爲norheim.se說還是Dijkstra's algorithm將是我的建議爲好。

來源

2009-10-02 20:28:51

-1

看起來你的圖的邊緣是雙向的。在這種情況下，您要查找的算法是Dijkstra's algorithm。

來源

2009-10-02 20:35:27

也許這就是「通過手動迭代每種可能性並存儲最短路徑」原始海報的含義，但我想我想明確看起來是什麼樣的基準解決方案。

假設您已經有了一個兩點最短路徑算法 - 這對於各種圖形都有經典的解決方案。假設所有的距離都是非負的，並且d（A→B→C）= d（A→B）+ d（B→C）。

的要領是，該路徑始於S端變爲通過中間城市「ABCD」的一個和爲E結束：

例如SabcdE，SacbdE等...

只有4箇中間城市，列舉了所有24個排列組合。對於每個置換使用最短的兩點算法來計算從頭到尾的路徑及其總距離。

然後給出起點和終點，有12個可能性附加到abcd之一，併爲每個內部的兩種可能性。你已經計算出了這些距離，所以你添加了從S到頭部和尾部的距離。選擇最小值。所以一旦你預先計算了一組固定的內部城市的中間距離，你需要爲任何一對開始和結束點做12個兩點最短路徑問題。

隨着越來越多的中等城市數量的增加，我不清楚，除非你對圖結構施加更大的限制（這是否在物理歐幾里德空間？三角不等式中），它可能會更好。

我想的例子：假設城市之間的所有中間距離都是O（1）。沒有對圖表的限制，那麼從S到任何中間城市的距離可能是1000，除了一個是1.尾部相同。所以你可以強迫第一個城市被視爲任何東西。現在，往下走一層，以第一個城市爲「起點」。應用相同的參數：通過操縱圖形中的距離，可以使最佳路徑進入以下任意城市。

因此，似乎複雜性不能沒有額外的假設幫助。

來源

2009-10-04 06:54:24

這是任何人都可以遇到的非常常見和真實的情況.Google地圖用戶界面會以相同的順序爲您提供路徑，您將添加到目標列表中。儘管他們自己的Google地圖API提供瞭解決方案，但它並不能爲您提供最佳路徑。

谷歌地圖API爲此提供瞭解決方案。在找出路徑的請求中，您必須提供標記'optimizeWaypoints：true'。該請求看起來像這樣。

var request = { 
      origin: start, 
      destination: end, 
      waypoints: waypts, 
      optimizeWaypoints: true, 
      travelMode: google.maps.TravelMode.DRIVING 
     };

您可以在視圖源中看到該實用程序的完整代碼，因爲完整的實用程序是在JavaScript和HTML中開發的。

我希望這會有所幫助。

來源

2014-01-10 06:27:06

你的網站是好友，所以是鏈接 – sam

算法優化 - 多點之間的最短路徑

回答

相關問題