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

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

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

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

1 路徑規(guī)劃算法

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

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

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

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

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

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

通過對雙向啟發(fā)式搜索算法的仔細(xì)分析，發(fā)現(xiàn)算法主要圍繞兩個表進行操作，即OPEN表和CLOSE表。前者用于存放已經(jīng)搜索但尚未確定最小費用的節(jié)點，稱la