谷歌地圖使用算法/方法尋找兩座城市之間的路徑

最近我有一個求職面試，他們問我「谷歌地圖使用哪種方法找到兩個城市之間的最短路徑？」。我沒有回答這個問題，但我猜他們使用「最短路徑算法」尋找路徑，但採訪者說「不」。在那次採訪之後，我搜索了很多，但沒有找到任何方法。請告訴我，如果你有任何關於谷歌地圖如何找到兩個城市之間最短路徑的想法谷歌地圖使用算法/方法尋找兩座城市之間的路徑

來源

2012-12-30 blacktornado

你看看這個主題嗎？ http://stackoverflow.com/questions/430142/what-algorithms-compute-directions-from-point-a-to-point-b-on-a-map –

對不起，我沒有看那個線程。 – blacktornado

你可以閱讀這個谷歌博客http://googleblog.blogspot.com.br/2007/11/road-to-better-path-finding.html和這個偉大的答案：http://stackoverflow.com/a/432854/2516160 – jean

他問過你最短的路徑嗎？那麼你的權利。在這裏閱讀Dijkstra's Algorithm Does not generate Shortest Path?。但也許他意味着最快的路徑？

來源

2012-12-30 14:33:32 Bytemain

我回答了「Dijkstra算法」，但他對我說他不需要Bookish Solution。現在我很確定採訪是讓我感覺「不確定，愚蠢和便宜」。 – blacktornado

我猜它必須涉及'谷歌地圖'而不是普通的'圖理論解決方案'....與解釋地圖有關。我的2美分。 – Bill

我在接受'Dijkstra的算法不生成最短路徑「時有反對意見....這種算法生成給定源節點和目的節點之間的最短路徑。 – Bill

A *怎麼樣？它似乎適用於路徑查找。

來源

2015-01-09 09:20:53

碰巧我剛剛參加了一個關於它的討論。 Dijkstras算法對於谷歌來說太低效了。雖然複雜性n log n很好，但絕對時間很長。

Google使用Contraction Hierarchies的變體。它比Dijkstra更快，因爲網絡是預處理的。即使有更快的算法涉及預處理，CH提供了很大的靈活性。

來源

2017-07-07 14:33:40

谷歌地圖使用算法/方法尋找兩座城市之間的路徑

回答

相關問題