摘? 要: 介紹單車輛路徑規劃的有關算法，針對車載導航儀的應用，對雙向啟發式搜索算法進行了改進和優化，提出了可靠有效的搜索終止條件和搜索切換標準，給出了改進算法的流程。最后給出了四種算法的實際測試和比較結果。結果表明改進的雙向啟發式搜索算法快速高效。
關鍵詞: 路徑規劃 啟發式搜索算法 雙向搜索算法
?
車載導航儀也稱為車載定位和導航系統(Vehicle Location and Navigation System )。它的主要功能是利用全球定位系統(GPS)獲取定位信息并與電子地圖進行匹配，以決定車輛的當前位置并用圖形化方式顯示;按要求規劃從出發地到目的地的最優駕駛路線;按照預先設定的路線，自動根據車輛的位置向駕駛員提供操作指令引導駕駛;提供與電子地圖相關的集成信息服務;提供無線通信服務等。車載導航儀把先進的全球衛星定位技術、地理信息技術、數據庫技術、多媒體技術和現代通信技術綜合在一起，能夠實時、高效地向駕駛員提供多種重要信息，具有很強的實用價值和廣闊的市場前景。
路徑規劃是車載導航儀的重要功能模塊。在開發車載導航儀過程中，為了實現路徑規劃模塊，對單車輛路徑規劃算法進行了研究。
1 路徑規劃算法
所謂路徑規劃，就是在路網中找到任意給定兩點之間的最優路徑。最優的標準是旅行費用最小或最大。旅行費用可以是距離、時間或速度等因素。路徑規劃主要算法有:迪杰斯特拉(Dijkstra)算法及其改進算法、啟發式搜索算法、雙向搜索算法和雙向啟發式搜索算法等。
迪杰斯特拉算法是解決兩點之間最短距離的有效算法。算法的思想是：從原節點開始，算法每前進一步，都找到一個與原節點之間費用(距離)最小的節點，直至找到所有節點離原節點的最小費用。該算法的特點是：只要各段路徑的費用非負，一定可以找到從原節點到各節點的最優解。缺點是需遍歷所有節點。算法的運行時間為O(slogn)[1]，其中n、s分別為路徑節點和路段的總數。單車導航沒有必要找到所有節點到原節點的最優路徑。改進的迪杰斯特拉算法在找到目標節點的最優路徑后，算法停止。其運行時間為O(bd)，其中b是各節點的平均后繼節點數，d為算法的搜索深度，即遍歷樹的層數。
啟發式搜索算法引入啟發式估價函數f’(n)=g(n)+h’(n)，其中g(n)表示從原節點到當前節點n的實際費用，h’(n)為當前節點n到目標節點的估計費用。啟發式搜索算法基本同于改進的迪杰斯特拉算法，唯一不同的是前者的費用是f’(n)，而后者為g(n)。估計費用h’(n)能引導算法優先搜索接近目標節點的節點，因此比改進的迪杰斯特拉算法有更快的速度。其運行時間為O(bd)。注意這里的d要比改進的迪杰斯特拉算法中的d要小。若路網中任意兩點之間存在最優路徑，而且估計費用滿足可納性，即h’(n)小于從節點n到目標節點之間的實際費用，那么通過該算法一定可以找到一條最優路徑。
前面兩種算法都是從原節點到目標節點沒單一方向進行搜索的算法。雙向搜索算法的思想是:不僅進行從原節點到目標節點的前向搜索，而且進行從目標節點到原節點的后向搜索。在單CPU硬件平臺條件下，兩個方向的搜索交替進行。成功實現雙向搜索有兩個條件，即合適的搜索停止條件和前向后向搜索切換標準。其算法時間為O(bd/2)。若雙向搜索算法中加入估計費用函數，便是更快的雙向啟發式搜索算法[1]。
2 雙向啟發式搜索算法的改進和實現
2.1 算法的優化與改進
通過對雙向啟發式搜索算法的仔細分析，發現算法主要圍繞兩個表進行操作，即OPEN表和CLOSE表。前者用于存放已經搜索但尚未確定最小費用的節點，稱labbled節點;后者用于存放已經搜索且最小費用已知的節點，稱scanned節點。后者也用于存放路徑回朔指針等。對OPEN表的主要操作有插入一個i節點insert(i)，刪除費用值最小的節點delete()和減小其中某個節點i的費用decrease(i)。算法對OPEN表的操作極為頻繁。若用高效的數據結構來實現該表及其操作，可以提高算法的效率和速度。最后用有高效算法的最小堆[4]實現了OPEN表及其操作，優化了算法。具體實現的函數如下:void filter_down(int START， int ENDOFHEAP)；//由起點START從上而下排列堆;void decrease(int NODE)；//更新(減少)堆中節點NODE的費用f’值;void filter_up(int START)；//由起點START從下而上排列堆;void heap_create(int MAXSIZE)；//創建堆;void heap_destructor()；//析構函數;int insert(int NODE)；//把節點NODE插入堆;int remove_min(int &iMinNode)；//刪除堆中最小費用f’值的節點。
在實際的路網中，路段有不同的屬性，如高速公路、收費路段、單行路段等。有些路段可能因修建或發生交通故障而暫時封閉。因此在進行路徑規劃時，算法應該考慮路網中路段的屬性，才能進行符合實際的規劃，否則理論上規劃出來的最優路徑可能是不通的。為此，對算法進行了改進。增加一個變量紀錄各路段的屬性，算法每搜索一新的路段，都要檢查該路段的屬性，若是限制的路段，算法不做任何處理。同時路徑規劃算法入口參數中應說明限制的內容。這樣就能根據用戶的意愿或實時交通信息，避免走某些特定的路段。
2.2 搜索停止條件、搜索切換標準和估計費用函數
前面提到，成功實現雙向搜索算法必須有合適的搜索停止條件和切換標準。兩個標準沒有現成的理論依據。經過對車載導航儀實際應用的分析和反復試驗，終于找到可靠有效的標準。其中停止條件為:(1)搜索到這樣一個節點iNODEmin，它在前向后向搜索過程中均被標為scanned節點;(2)g1(iNODEmin)+g2(iNODEmin)確實是最小的，其中g1(iNODEmin)表示從原節點到iNODEmin的最小費用，g2(iNODEmin)表示從目標節點到iNODEmin的最小費用。如果只滿足第一個條件就停止搜索，找到的最優路徑不一定是最優的。只有加上第二個條件，才能確保找到最優的路徑，但付出的代價是要多搜索幾十個點。具體的搜索停止條件如圖1所示。此外，經過實驗發現，如前向搜索的步數和后向搜索的步數不同，則算法的總的搜索節點數增加。因此兩個方向上的搜索步數應相同，然后切換。但搜索步距過小或過大，也會增加總搜索量。最后定下的切換標準是，每個方向搜索20步后切換方向。此外，前向搜索估計費用函數h1’(n)定義為從當前節點n到終點的歐氏距離，后向估計費用函數h2’(n)定義為從n到原節點的歐氏距離。由于這兩個距離均小于從n到目標節點或原節點的路徑的實際距離，因此h1’(n)和h2’(n)滿足可納性。
?
?
2.3 算法流程
改進的雙向啟發式搜索算法主要流程如下:
(1)把原節點移入前向CLOSE表，即令flag1(原節點)=scanned，其費用g1(原節點)=0，其它節點的費用為無窮。
(2)對原節點所有后繼節點i進行如下操作:
·判斷路徑(原節點，i)是否限制路段，是處理下一個后繼節點，否則繼續;
·計算i的費用f1(i)=g1(i)+h1’(i);
·置i的搜索狀態flag1(i)=labbled;
·把i的后向指針指向原節點，即link1(i)=原節點;
·把i插入OPEN1表，即insert1(i)。
(3)判斷OPEN1表是否為空，若為空提示出錯，算法停止;否則從OPEN1表中移出費用值f1最小的節點iNODEmin，令節點i的搜索狀態flag1(iNODEmin)=scanned，判斷iNODEmin是否滿足搜索終止條件。若滿足跳轉至(7)，否則對iNODEmin的所有后繼節點i進行如下操作:
·判斷路徑(iNODEmin，i)是否限制路段，是處理下一節點，否則繼續;
????·計算i的費用f1(i)=g1(i)+h1’(i);
????·若節點i的搜索狀態flag1(i)=unlabbled，則令其費用f1(i)=g1(i)+h1’(i)，link1(i)=iNODEmin，insert1(i);
????·如果節點i的flag1(i)=labbled，計算節點i新的費用g1’(i)=g1(iNODEmin)+從iNODEmin到i的實際費用，若g1’(i) ????·若flag1(i)=scanned，計算g1’(i)=g1(iNODEmin)+從iNODEmin到i的實際費用，若g1’(i) ????·判斷前向搜索是否進行了20步，是跳轉至(4)(第一次切換)或(6)(第二次以后的切換)，否則跳轉至(3)。 ????(4)同(1)，只是對CLOSE2操作; ????(5)同(2)，只是對OPEN2和CLOSE2操作; ????(6)同(3)，只是對OPEN2和CLOSE2操作，切換時跳轉至(3); ????(7)計算最優路徑的費用，分別從搜索停止節點到原節點和從搜索停止節點到目標節點回朔，報告解路徑。上述流程中(1～3)步為前向搜索，(4～6)為后向搜索。 3 試驗結果及結論 作者用C語言實現了雙向啟發式搜索算法和其它三種算法，并用約有10000個節點的美國紐約地圖進行了大量路徑規劃試驗。試驗的部分數據如表1所示。表中的數據除起止節點外，為相關算法的搜索節點數，括弧中數據為一次測試中該算法的搜索點數少于改進的迪杰斯特拉算法的搜索點數的百分比。大量試驗統計表明，啟發式搜索算法的搜索空間比改進的迪杰斯特拉算法少1.5%，雙向搜索算法的搜索空間比改進的迪杰斯特拉算法減少26.6%，雙向啟發式搜索算法的搜索空間比改進的迪杰斯特拉算法少28.0%。算法運算時間與搜索點數成正比。雙向搜索的效果較好，啟發式的效果較差。主要原因是試驗地圖數據庫給出的節點坐標是經緯度，估計費用直接用兩點的經緯度算出，其值很小，所以引導的效果不好。進行坐標變換后，啟發式的效果應有比較大的改善，雙向啟發式搜索算法的速度會更快。 ? ? 算法程序全部用C語言編寫，所用功能模塊均以函數的形式給出，以便移植到基于WindowCE的硬件平臺。總之改進的雙向啟發式搜索算法快速高效，已經成功用于正在開發的車載導航儀。 ? 參考文獻 1 [美]趙亦林.車輛定位與導航系統，北京:電子工業出版社 2?RAVINDA K.AHUJA.Faster Algorithms for the Shortest Path Problem.Journal of the Association for Computing ? Machinery， 1990;37(2) 3 Y.Zhao and T.E.Weymouth.“An adaptive Route-Guidance Algorithm for Intelligent Vehicle-Highway System” ? Proc.American Control Conference， June 1991:2568～2573 4 殷人昆.數據結構.北京:清華大學出版社 5 [美]Greg Perry.C++程序設計教程，北京:清華大學出版社