摘? 要: 介紹單車輛路徑規(guī)劃的有關(guān)算法，針對車載導航儀的應(yīng)用,，對雙向啟發(fā)式搜索算法進行了改進和優(yōu)化,，提出了可靠有效的搜索終止條件和搜索切換標準，給出了改進算法的流程,。最后給出了四種算法的實際測試和比較結(jié)果,。結(jié)果表明改進的雙向啟發(fā)式搜索算法快速高效。

　　關(guān)鍵詞: 路徑規(guī)劃 啟發(fā)式搜索算法 雙向搜索算法

?

　　車載導航儀也稱為車載定位和導航系統(tǒng)(Vehicle Location and Navigation System ),。它的主要功能是利用全球定位系統(tǒng)(GPS)獲取定位信息并與電子地圖進行匹配,，以決定車輛的當前位置并用圖形化方式顯示;按要求規(guī)劃從出發(fā)地到目的地的最優(yōu)駕駛路線;按照預先設(shè)定的路線，自動根據(jù)車輛的位置向駕駛員提供操作指令引導駕駛;提供與電子地圖相關(guān)的集成信息服務(wù);提供無線通信服務(wù)等,。車載導航儀把先進的全球衛(wèi)星定位技術(shù),、地理信息技術(shù)、數(shù)據(jù)庫技術(shù),、多媒體技術(shù)和現(xiàn)代通信技術(shù)綜合在一起,，能夠?qū)崟r、高效地向駕駛員提供多種重要信息,，具有很強的實用價值和廣闊的市場前景,。

　　路徑規(guī)劃是車載導航儀的重要功能模塊。在開發(fā)車載導航儀過程中,，為了實現(xiàn)路徑規(guī)劃模塊,，對單車輛路徑規(guī)劃算法進行了研究。

1 路徑規(guī)劃算法

　　所謂路徑規(guī)劃,，就是在路網(wǎng)中找到任意給定兩點之間的最優(yōu)路徑,。最優(yōu)的標準是旅行費用最小或最大。旅行費用可以是距離,、時間或速度等因素,。路徑規(guī)劃主要算法有:迪杰斯特拉(Dijkstra)算法及其改進算法、啟發(fā)式搜索算法,、雙向搜索算法和雙向啟發(fā)式搜索算法等,。

　　迪杰斯特拉算法是解決兩點之間最短距離的有效算法。算法的思想是：從原節(jié)點開始,，算法每前進一步,，都找到一個與原節(jié)點之間費用(距離)最小的節(jié)點，直至找到所有節(jié)點離原節(jié)點的最小費用,。該算法的特點是：只要各段路徑的費用非負,，一定可以找到從原節(jié)點到各節(jié)點的最優(yōu)解,。缺點是需遍歷所有節(jié)點。算法的運行時間為O(slogn)^[1],，其中n,、s分別為路徑節(jié)點和路段的總數(shù)。單車導航?jīng)]有必要找到所有節(jié)點到原節(jié)點的最優(yōu)路徑,。改進的迪杰斯特拉算法在找到目標節(jié)點的最優(yōu)路徑后,，算法停止。其運行時間為O(bd),，其中b是各節(jié)點的平均后繼節(jié)點數(shù),，d為算法的搜索深度，即遍歷樹的層數(shù),。

　　啟發(fā)式搜索算法引入啟發(fā)式估價函數(shù)f’(n)=g(n)+h’(n),，其中g(shù)(n)表示從原節(jié)點到當前節(jié)點n的實際費用，h’(n)為當前節(jié)點n到目標節(jié)點的估計費用,。啟發(fā)式搜索算法基本同于改進的迪杰斯特拉算法,，唯一不同的是前者的費用是f’(n)，而后者為g(n),。估計費用h’(n)能引導算法優(yōu)先搜索接近目標節(jié)點的節(jié)點,，因此比改進的迪杰斯特拉算法有更快的速度。其運行時間為O(bd),。注意這里的d要比改進的迪杰斯特拉算法中的d要小,。若路網(wǎng)中任意兩點之間存在最優(yōu)路徑，而且估計費用滿足可納性,，即h’(n)小于從節(jié)點n到目標節(jié)點之間的實際費用，那么通過該算法一定可以找到一條最優(yōu)路徑,。

　　前面兩種算法都是從原節(jié)點到目標節(jié)點沒單一方向進行搜索的算法,。雙向搜索算法的思想是:不僅進行從原節(jié)點到目標節(jié)點的前向搜索，而且進行從目標節(jié)點到原節(jié)點的后向搜索,。在單CPU硬件平臺條件下,，兩個方向的搜索交替進行。成功實現(xiàn)雙向搜索有兩個條件,，即合適的搜索停止條件和前向后向搜索切換標準,。其算法時間為O(bd/2)。若雙向搜索算法中加入估計費用函數(shù),，便是更快的雙向啟發(fā)式搜索算法^[1],。

2 雙向啟發(fā)式搜索算法的改進和實現(xiàn)

2.1 算法的優(yōu)化與改進

　　通過對雙向啟發(fā)式搜索算法的仔細分析，發(fā)現(xiàn)算法主要圍繞兩個表進行操作,，即OPEN表和CLOSE表,。前者用于存放已經(jīng)搜索但尚未確定最小費用的節(jié)點,，稱labbled節(jié)點;后者用于存放已經(jīng)搜索且最小費用已知的節(jié)點，稱scanned節(jié)點,。后者也用于存放路徑回朔指針等,。對OPEN表的主要操作有插入一個i節(jié)點insert(i)，刪除費用值最小的節(jié)點delete()和減小其中某個節(jié)點i的費用decrease(i),。算法對OPEN表的操作極為頻繁,。若用高效的數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)該表及其操作，可以提高算法的效率和速度,。最后用有高效算法的最小堆[4]實現(xiàn)了OPEN表及其操作,，優(yōu)化了算法。具體實現(xiàn)的函數(shù)如下:void filter_down(int START,， int ENDOFHEAP),；//由起點START從上而下排列堆;void decrease(int NODE)；//更新(減少)堆中節(jié)點NODE的費用f’值;void filter_up(int START),；//由起點START從下而上排列堆;void heap_create(int MAXSIZE),；//創(chuàng)建堆;void heap_destructor()；//析構(gòu)函數(shù);int insert(int NODE),；//把節(jié)點NODE插入堆;int remove_min(int &iMinNode),；//刪除堆中最小費用f’值的節(jié)點。

　　在實際的路網(wǎng)中,，路段有不同的屬性,，如高速公路、收費路段,、單行路段等,。有些路段可能因修建或發(fā)生交通故障而暫時封閉。因此在進行路徑規(guī)劃時,，算法應(yīng)該考慮路網(wǎng)中路段的屬性,，才能進行符合實際的規(guī)劃，否則理論上規(guī)劃出來的最優(yōu)路徑可能是不通的,。為此,，對算法進行了改進。增加一個變量紀錄各路段的屬性,，算法每搜索一新的路段,，都要檢查該路段的屬性，若是限制的路段,，算法不做任何處理,。同時路徑規(guī)劃算法入口參數(shù)中應(yīng)說明限制的內(nèi)容。這樣就能根據(jù)用戶的意愿或?qū)崟r交通信息,，避免走某些特定的路段,。

2.2 搜索停止條件,、搜索切換標準和估計費用函數(shù)

　　前面提到，成功實現(xiàn)雙向搜索算法必須有合適的搜索停止條件和切換標準,。兩個標準沒有現(xiàn)成的理論依據(jù),。經(jīng)過對車載導航儀實際應(yīng)用的分析和反復試驗，終于找到可靠有效的標準,。其中停止條件為:(1)搜索到這樣一個節(jié)點iNODEmin,，它在前向后向搜索過程中均被標為scanned節(jié)點;(2)g1(iNODEmin)+g2(iNODEmin)確實是最小的，其中g(shù)1(iNODEmin)表示從原節(jié)點到iNODEmin的最小費用,，g2(iNODEmin)表示從目標節(jié)點到iNODEmin的最小費用,。如果只滿足第一個條件就停止搜索，找到的最優(yōu)路徑不一定是最優(yōu)的,。只有加上第二個條件,，才能確保找到最優(yōu)的路徑，但付出的代價是要多搜索幾十個點,。具體的搜索停止條件如圖1所示,。此外，經(jīng)過實驗發(fā)現(xiàn),，如前向搜索的步數(shù)和后向搜索的步數(shù)不同,，則算法的總的搜索節(jié)點數(shù)增加。因此兩個方向上的搜索步數(shù)應(yīng)相同,，然后切換,。但搜索步距過小或過大，也會增加總搜索量,。最后定下的切換標準是,，每個方向搜索20步后切換方向。此外,，前向搜索估計費用函數(shù)h1’(n)定義為從當前節(jié)點n到終點的歐氏距離,，后向估計費用函數(shù)h2’(n)定義為從n到原節(jié)點的歐氏距離。由于這兩個距離均小于從n到目標節(jié)點或原節(jié)點的路徑的實際距離,，因此h1’(n)和h2’(n)滿足可納性。

?

?

2.3 算法流程

　　改進的雙向啟發(fā)式搜索算法主要流程如下:

　　(1)把原節(jié)點移入前向CLOSE表,，即令flag1(原節(jié)點)=scanned,，其費用g1(原節(jié)點)=0，其它節(jié)點的費用為無窮,。

　　(2)對原節(jié)點所有后繼節(jié)點i進行如下操作:

　　·判斷路徑(原節(jié)點,，i)是否限制路段，是處理下一個后繼節(jié)點,，否則繼續(xù);

　　·計算i的費用f1(i)=g1(i)+h1’(i);

　　·置i的搜索狀態(tài)flag1(i)=labbled;

　　·把i的后向指針指向原節(jié)點,，即link1(i)=原節(jié)點;

　　·把i插入OPEN1表,，即insert1(i)。

　　(3)判斷OPEN1表是否為空,，若為空提示出錯,，算法停止;否則從OPEN1表中移出費用值f1最小的節(jié)點iNODEmin，令節(jié)點i的搜索狀態(tài)flag1(iNODEmin)=scanned,，判斷iNODEmin是否滿足搜索終止條件,。若滿足跳轉(zhuǎn)至(7)，否則對iNODEmin的所有后繼節(jié)點i進行如下操作:

　　·判斷路徑(iNODEmin,，i)是否限制路段,，是處理下一節(jié)點，否則繼續(xù);

????·計算i的費用f1(i)=g1(i)+h1’(i);

????·若節(jié)點i的搜索狀態(tài)flag1(i)=unlabbled,，則令其費用f1(i)=g1(i)+h1’(i),，link1(i)=iNODEmin，insert1(i);

????·如果節(jié)點i的flag1(i)=labbled,，計算節(jié)點i新的費用g1’(i)=g1(iNODEmin)+從iNODEmin到i的實際費用,，若g1’(i)

????·若flag1(i)=scanned,，計算g1’(i)=g1(iNODEmin)+從iNODEmin到i的實際費用,，若g1’(i)

????·判斷前向搜索是否進行了20步,，是跳轉(zhuǎn)至(4)(第一次切換)或(6)(第二次以后的切換),，否則跳轉(zhuǎn)至(3)。

????(4)同(1),，只是對CLOSE2操作;

????(5)同(2),，只是對OPEN2和CLOSE2操作;

????(6)同(3)，只是對OPEN2和CLOSE2操作,，切換時跳轉(zhuǎn)至(3);

????(7)計算最優(yōu)路徑的費用,，分別從搜索停止節(jié)點到原節(jié)點和從搜索停止節(jié)點到目標節(jié)點回朔，報告解路徑,。上述流程中(1～3)步為前向搜索,，(4～6)為后向搜索。

3 試驗結(jié)果及結(jié)論

　　作者用C語言實現(xiàn)了雙向啟發(fā)式搜索算法和其它三種算法,，并用約有10000個節(jié)點的美國紐約地圖進行了大量路徑規(guī)劃試驗,。試驗的部分數(shù)據(jù)如表1所示,。表中的數(shù)據(jù)除起止節(jié)點外，為相關(guān)算法的搜索節(jié)點數(shù),，括弧中數(shù)據(jù)為一次測試中該算法的搜索點數(shù)少于改進的迪杰斯特拉算法的搜索點數(shù)的百分比,。大量試驗統(tǒng)計表明，啟發(fā)式搜索算法的搜索空間比改進的迪杰斯特拉算法少1.5%,，雙向搜索算法的搜索空間比改進的迪杰斯特拉算法減少26.6%,，雙向啟發(fā)式搜索算法的搜索空間比改進的迪杰斯特拉算法少28.0%。算法運算時間與搜索點數(shù)成正比,。雙向搜索的效果較好,，啟發(fā)式的效果較差。主要原因是試驗地圖數(shù)據(jù)庫給出的節(jié)點坐標是經(jīng)緯度,，估計費用直接用兩點的經(jīng)緯度算出,，其值很小，所以引導的效果不好,。進行坐標變換后,，啟發(fā)式的效果應(yīng)有比較大的改善，雙向啟發(fā)式搜索算法的速度會更快,。

?

?

　　算法程序全部用C語言編寫,，所用功能模塊均以函數(shù)的形式給出，以便移植到基于WindowCE的硬件平臺,?？傊倪M的雙向啟發(fā)式搜索算法快速高效，已經(jīng)成功用于正在開發(fā)的車載導航儀,。

?

參考文獻

1 [美]趙亦林.車輛定位與導航系統(tǒng),，北京:電子工業(yè)出版社

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 殷人昆.數(shù)據(jù)結(jié)構(gòu).北京:清華大學出版社

5 [美]Greg Perry.C++程序設(shè)計教程,，北京:清華大學出版社