導航軟件是如何規劃路線的？

路痴baby

作為一個路痴，我離了手機導航軟件簡直沒法活啊！每次用的時候都在想，它是怎麼幫我規劃出這麼完美的路線的呢？

包包

路徑規劃，這可是門大學問。包包找到北京理工大學宇航學院副院長龍騰為我們解答這個問題。

龍老師

路徑規劃無論在民用還是軍用領域都應用廣泛，汽車行駛需要路徑規劃，導彈、無人機等飛行器也需要進行航路（或航跡）規劃，它們的底層算法是相通的，隻不過汽車路徑規劃相對簡單隻需要在二維平面進行，而且對規劃環境以及反應速度等方面的要求沒有飛行器那麼高。本質上說，底層算法包括兩大類。

第一種是數值優化算法。它在起點和終點之間布設一系列路徑點，使用坐標值表述路徑點位置，讓汽車沿著這些點行駛。在選擇路徑點時，就需要定義目標函數，例如路徑長度最短。規劃過程中還需考慮一些約束條件，比如對咱們日常駕駛的汽車來說，必須要求路徑點都位於已有道路上。然后，借鑒一些現代數值優化算法（比如粒子群算法，它是模擬鳥群、魚群捕食過程的全局搜索算法），不斷地對可能布設路徑點的區域進行探索，最終確定使得目標函數最優（如路徑長度最低）的路徑點。

但總體來說，如果路徑點規模較大時，使用數值優化算法求解路徑規劃時，問題的維度將急劇增加，導致規劃過程所需時間較長，難以滿足導航軟件的時效性要求。如今非常具有實用性的是第二種算法——啟發式算法。

啟發式算法，以我們導航上常用的“A*算法”“Dijikstra算法”等為代表，它從起始點開始，以一定的步長為單位，進行節點擴展。選取代價值（如路徑長度）最小的節點作為擴展節點，擴展過程中需要考慮一些約束，比如轉彎半徑的限制以及對風險障礙的規避等等，這就使擴展角度不可能總是全方位的。如此一步步擴展，直到當某個擴展節點到達目標終點時，再從終點倒過來回溯到起點，這樣，把過程中的各個節點串起來，就成為了一條規劃的路徑。這類規劃算法的效率比較高。（劉歲?）