地圖提供商（例如Google或Yahoo! Maps）如何建議方向？我的意思是，他們可能具有某種形式的現實世界數據，當然包括距離，還可能包括行車速度，人行道的存在，火車時刻表等。但是，假設數據的格式更簡單，則表示一個很大的有向圖邊緣權重反映距離。我希望能夠快速計算從一個任意點到另一點的方向。有時，這些點會彼此靠近（在一個城市內），而有時它們會相距較遠（越野）。像Dijkstra的算法這樣的圖算法將無法工作，因為圖非常大。幸運的是，像A *這樣的啟發式算法可能會起作用。但是，我們的數據非常結構化，也許某種分層方法可能有效？（例如，存儲相距很遠的某些“關鍵”點之間的預先計算的方向以及一些本地方向。然后，兩個遙遠點的方向將涉及到關鍵點的本地方向，到另一個關鍵點的全局方向，然后是本地再次指示。）實際上實際使用哪些算法？PS。這個問題是由在網上制圖方向上找到古怪之處引起的。與三角形不等式相反，有時Google Maps認為XZ比使用XYZ中的中間點花費更長的時間并且更遠。但是也許他們的步行方向也針對另一個參數進行了優化？PPS。這是對三角形不等式的另一種違反，對我而言，這暗示了他們使用某種分層方法：XZ與XYZ。前者似乎使用了著名的塞巴斯托波爾大道，盡管有點偏離。編輯：這些示例似乎都不工作了，但在原始帖子發布時都可以。
3 回答
慕萊塢森
TA貢獻1810條經驗 獲得超4個贊
以在地圖公司工作了18個月的人的身份發言，其中包括研究路由算法...是的，Dijkstra確實可以工作，但有一些修改：
您無需從源頭到目標都進行一次Dijkstra的操作，而應從兩端開始，并擴展雙方直到中間相遇。這消除了大約一半的工作（2 * pi *（r / 2）^ 2 vs pi * r ^ 2）。
為了避免探索源與目的地之間每個城市的后巷，您可以使用幾層地圖數據：僅包含高速公路的“高速公路”層，僅包含次要街道的“次級”層，依此類推。然后，您僅瀏覽更詳細層的較小部分，并根據需要進行擴展。顯然，此描述省略了很多細節，但是您可以理解。
沿著這些路線進行修改，您甚至可以在非常合理的時間范圍內進行越野路線選擇。
智慧大石
TA貢獻1946條經驗 獲得超3個贊
近年來，這個問題一直是研究的活躍領域。主要思想是對圖形進行一次預處理，以加快所有后續查詢的速度。利用這些附加信息，可以非?？焖俚赜嬎阈谐獭１M管如此，Dijkstra的算法仍是所有優化的基礎。
Arachnid描述了基于分層信息的雙向搜索和邊緣修剪的用法。這些加速技術效果很好，但是最新的算法在所有方面都優于這些技術。使用當前的算法，在大陸公路網絡上，最短路徑的計算時間可少于一毫秒。Dijkstra的未修改算法的快速實現大約需要10秒。
《工程快速路線規劃算法》一書概述了該領域的研究進展。有關更多信息，請參見該文件的參考。
已知最快的算法不會在數據中使用有關道路分層狀態的信息，即公路是公路還是本地道路。取而代之的是，它們在預處理步驟中計算自己的層次結構，并對其進行優化以加快路線規劃。然后可以使用這種預計算來簡化搜索：在Dijkstra算法中，無需考慮遠離起點和目的地的慢行道路。好處是非常好的性能和結果的正確性保證。
第一個優化的路線規劃算法僅處理靜態道路網絡，這意味著圖中的邊具有固定的成本值。實際上，這不是真的，因為我們要考慮動態信息，例如交通擁堵或與車輛相關的限制條件。最新的算法也可以解決此類問題，但仍有許多問題需要解決，并且研究正在進行中。
如果您需要最短的路徑距離來為TSP計算解決方案，那么您可能會對包含源與目標之間的所有距離的矩陣感興趣。為此，您可以考慮使用高速公路層次結構計算多對多最短路徑。請注意，在過去的兩年中，這已經通過更新的方法得到了改善。
添加回答
舉報
0/150
提交
取消