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