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

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

?

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

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

1 路徑規(guī)劃算法

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

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

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

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

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

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

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

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

2.2 搜索停止條件、搜索切換標(biāo)準(zhǔn)和估計(jì)費(fèi)用函數(shù)

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

?

?

2.3 算法流程

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

　　(1)把原節(jié)點(diǎn)移入前向CLOSE表，即令flag1(原節(jié)點(diǎn))=scanned，其費(fèi)用g1(原節(jié)點(diǎn))=0，其它節(jié)點(diǎn)的費(fèi)用為無(wú)窮。

　　(2)對(duì)原節(jié)點(diǎn)所有后繼節(jié)點(diǎn)i進(jìn)行如下操作:

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

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

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

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

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

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

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

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

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

????·如果節(jié)點(diǎn)i的flag1(i)=labbled，計(jì)算節(jié)點(diǎn)i新的費(fèi)用g1’(i)=g1(iNODEmin)+從iNODEmin到i的實(shí)際費(fèi)用，若g1’(i)

????·若flag1(i)=scanned，計(jì)算g1’(i)=g1(iNODEmin)+從iNODEmin到i的實(shí)際費(fèi)用，若g1’(i)

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

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

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

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

????(7)計(jì)算最優(yōu)路徑的費(fèi)用，分別從搜索停止節(jié)點(diǎn)到原節(jié)點(diǎn)和從搜索停止節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)回朔，報(bào)告解路徑。上述流程中(1～3)步為前向搜索，(4～6)為后向搜索。

3 試驗(yàn)結(jié)果及結(jié)論

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

?

?

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

?

參考文獻(xiàn)

1 [美]趙亦林.車輛定位與導(dǎo)航系統(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).北京:清華大學(xué)出版社

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