常用的導航/路徑規劃軟體都用到哪些演算法？

01-08

昨晚睡前在看吳軍先生的數學之美，在其12章中提到導航軟體採用的演算法是動態規劃。
感覺DP解路徑規劃問題劃分一直是個大麻煩，相對於經典的路徑規劃演算法，也沒體現出巨大優勢。
早上在cnki下了一些相關論文（只討論主幹方法，因為學術界喜歡在演算法上做優化以及幾種演算法的橋接，比如基於dijkstra與遺傳免疫演算法的XX研究當做為dijkstra）

1.對於靜態路徑規劃，大多採用dijkstra，A，floyd，dp等
2.對於NP難問題，如TSP及變形（物流配送等），則採用遺傳演算法，蟻群演算法，模擬退火，神經網路等
問題：

1.在實際的商業應用中，採用的是哪些演算法或者理論呢？
2.路徑規劃是提前規劃好以後存儲（像網頁的索引），還是收到請求後實時規劃的結果？

明確一點，基本的圖搜索演算法dijkstra是無法滿足互聯網地圖檢索實時響應這種性能要求，所以各家公司都有各自的預處理方法：分層或者預計算。具體採用何種方式，這取決於採取的加速演算法相關。在2008年前後，以KIT（http://algo2.iti.kit.edu/routeplanning.php）為主的研究院產出了多個路徑規劃加速演算法，其中以contraction hierarchies 和 highway hierarchies較出名，加之微軟研究院提出的Customizable Route Planning，與傳統的A-star，基本上支撐了目前工業界地圖產品的路徑規劃服務。

A-star：https://en.wikipedia.org/wiki/A*_search_algorthm

CH：http://algo2.iti.kit.edu/schultes/hwy/contract.pdf

HH：http://algo2.iti.kit.edu/documents/routeplanning/esa06HwyHierarchies.pdf

CRP：http://research.microsoft.com/pubs/145688/crp-sea.pdf

一般都是分層做的。譬如說你要從廣州到北京，開車怎麼走，當然不可能直接在路上規劃吧，這樣計算量太大了。比較理想的方法是，我先知道到底要經過多少城市，從每一個城市到下一個城市之間如何走才能用高速連接起來，你需要訪問的數據就小得多。當最後約束到一個區那麼大的地方的時候，直接上DP還是可以在可接受的時間內做出來的。

題主提到的那些主要是路徑規劃最基礎的演算法，在實際商業運用中，這些公司會在它們的基礎上作一些改進，下面簡單補充兩點。

由於請求量巨大，一些比較經典的路徑規劃請求（如天安門-鳥巢）就沒有必要再實時規劃，而是直接使用別的用戶請求過的、已經存儲好的規劃結果。（典型的空間換時間，為了用戶的響應速度，google等公司是捨得花這點硬碟錢的）

再考慮一下路徑的優化問題。由於現實中的道路情況還要考慮路況、環境等更多的因素，基礎演算法單純基於圖得到的「最優」路徑，往往不一定是用戶最想要的。這時候導航提供商可能會給出一些次優的路徑，加入到檢索結果中，供給用戶選擇。再通過用戶的反饋進行學習，從而得到更加符合用戶需求的路徑規劃結果。一個例子是，google map會同時給出不同的幾條線路，供給用戶選擇，其中包含了路徑最短、換乘最少等等。還有，google map中得到檢索結果後，用戶可以在地圖上「拖動」路線，以得到更合適的路線，這些用戶「拖動」的信息，都是會發送到伺服器的（吧？）。

Efficient Point-to-Point Shortest
Path Algorithms

http://www.cs.princeton.edu/courses/archive/spr06/cos423/Handouts/EPP%20shortest%20path%20algorithms.pdf

Dijkstra是一種非常經典的方法，這種方法已經很成熟。通過對權值的計算，可以一次性計算出所有出發點到目的地的所有路徑信息，目前在一個城市裡，基本使用這種方法已經足夠。但是，實現路徑規劃只是基本的，想要將導航做的精確，需要對行駛在路段上的車輛進行統計，故障路段進行判斷，並實時調整路徑。