改進雙向啟發(fā)式搜索算法及其車載導(dǎo)航儀中應(yīng)用

1、改進雙向啟發(fā)式搜索算法及其車載導(dǎo)航儀中應(yīng)用車載導(dǎo)航儀也稱為車載定位和導(dǎo)航系統(tǒng)(vehicle location and navigation system。它的主要功能是利用全球定位系統(tǒng)()獵取定位信息并與地圖舉行匹配，以打算車輛的當(dāng)前位置并用圖形化方式顯示；按要求規(guī)劃從動身地到目的地的最優(yōu)駕駛路途；根據(jù)預(yù)先設(shè)定的路途，自動按照車輛的位置向駕駛員提供操作命令引導(dǎo)駕駛；提供與電子地圖相關(guān)的集成信息服務(wù)；提供無線通信服務(wù)等。車載導(dǎo)航儀把先進的全球衛(wèi)星定位技術(shù)、地理信息技術(shù)、數(shù)據(jù)庫技術(shù)、多媒體技術(shù)和現(xiàn)代通信技術(shù)綜合在一起?能夠?qū)崟r、高效地向駕駛員提供多種重要信息，具有很強的有用價值和廣大的市場前景。

2、路徑規(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ù)，一定可以

3、找到從原節(jié)點到各節(jié)點的最優(yōu)解。缺點是需遍歷全部節(jié)點。算法的運行時光為o slogn 1，其中n、s分離為路徑節(jié)點和路段的總數(shù)。單車導(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'ng n+h'n，其中g(shù)n表示從原節(jié)點到當(dāng)前節(jié)點n的實際費用，h'n為當(dāng)前節(jié)點到目標(biāo)節(jié)點的估量費用。啟發(fā)式搜尋算法基本同于改進的迪杰斯特拉算法，唯一不同的是前者的費用是f'n，而后者為g n。估量費用h'

4、; 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)。其算法時光為

5、o bd/2。若雙向搜尋算法中加入估量費用函數(shù)，便是更快的雙向啟發(fā)式搜尋算法。2 雙向啟發(fā)式搜尋算法的改進和實現(xiàn)2.1 算法的優(yōu)化與改進通過對雙向啟發(fā)式搜尋算法的認(rèn)真分析，發(fā)覺算法主要圍繞兩個表舉行操作，即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)該表及其操作

6、，可以提高算法的效率和速度。最后用有高效算法的最小堆4實現(xiàn)了open表及其操作，優(yōu)化了算法。詳細(xì)實現(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 remo

7、ve_min int &iminnode/刪除堆中最小費用f'值的節(jié)點。在實際的路網(wǎng)中，路段有不同的屬性，如高速馬路、收費路段、單行路段等。有些路段可能因修建或發(fā)生交通故障而臨時封閉。因此在舉行路徑規(guī)劃時，算法應(yīng)當(dāng)考慮路網(wǎng)中路段的屬性，才干舉行符合實際的規(guī)劃，否則理論上規(guī)劃出來的最優(yōu)路徑可能是不通的。為此，對算法舉行了改進。增強一個變量紀(jì)錄各路段的屬性，算法每搜尋一新的路段，都要檢查該路段的屬性，若是限制的路段，算法不做任何處理。同時路徑規(guī)劃算法入口參數(shù)中應(yīng)解釋限制的內(nèi)容。這樣就能按照用戶的意愿或?qū)崟r交通信息，避開走某些特定的路段。2.2 搜尋停止條件、搜尋切換標(biāo)準(zhǔn)和估量費用函

8、數(shù)前面提到，勝利實現(xiàn)雙向搜尋算法必需有合適的搜尋停止條件和切換標(biāo)準(zhǔn)。兩個標(biāo)準(zhǔn)沒有現(xiàn)成的理論依據(jù)。經(jīng)過對車載導(dǎo)航儀實際應(yīng)用的分析和反復(fù)實驗，最終找到牢靠有效的標(biāo)準(zhǔn)。其中停止條件為：(1)搜尋到這樣一個節(jié)點inodemin，它在前向后向搜尋過程中均被標(biāo)為scanned節(jié)點；(2)gl inodemin +g2 inodemin的確是最小的，其中g(shù)l inodemin表示從原節(jié)點到inodemin的最小費用，g2 inodemin表示從目標(biāo)節(jié)點到inodemin的最小費用。假如只滿足第一個條件就停止搜尋，找到的最優(yōu)路徑不一定是最優(yōu)的。惟獨加上其次個條件，才干確保找到最優(yōu)的路徑，但付出的代價是要多搜尋

9、幾十個點。詳細(xì)的搜尋停止條件1所示。此外，經(jīng)過試驗發(fā)覺，如前向搜尋的步數(shù)和后向搜尋的步數(shù)不同，則算法的總的搜尋節(jié)點數(shù)增強。因此兩個方向上的搜尋步數(shù)應(yīng)相同，然后切換。但搜尋步距過小或過大，也會增強總搜尋量。最后定下的切換標(biāo)準(zhǔn)是，每個方向搜尋20步后切換方向。此外，前向搜尋估量費用函數(shù)hl'n定義為從當(dāng)前節(jié)點n到盡頭的歐氏距離，后向估量費用函數(shù)h2' n定義為從n到原節(jié)點的歐氏距離。因為這兩個距離均小于從n到目標(biāo)節(jié)點或原節(jié)點的路徑的實際距離，因此hl'n和h2'n滿足可納性。2.3 算法流程改進的雙向啟發(fā)式搜尋算法主要流程如下：(1)把原節(jié)點移入前向close表，即

10、令flagl原節(jié)點scanned，其費用gl原節(jié)點0，其它節(jié)點的費用為無窮。(2)對原節(jié)點全部后繼節(jié)點i舉行如下操作：·推斷路徑(原節(jié)點，i)是否限制路段，是處理下一個后繼節(jié)點，否則繼續(xù)；·計算i的費用f1i g1 i+hl'i；·置i的搜尋狀態(tài)flag1 ilabbled；·把i的后向指針指向原節(jié)點，即link1 i原節(jié)點；·把i插入open1表，即insert1 i。(3)推斷open1表是否為空，若為空提醒出錯，算法停止；否則從open1表中移出費用值f1最小的節(jié)點inodemin，令節(jié)點i的搜尋狀態(tài)flag1 inodemins

11、canned，推斷inodemin是否滿足搜尋終止條件。若滿足跳轉(zhuǎn)至(7)，否則對inodemin的全部后繼節(jié)點i舉行如下操作：·推斷路徑(inodemin，i)是否限制路段，是處理下一節(jié)點，否則繼續(xù)；·計算i的費用f1 ig1 i+h1'i；·若節(jié)點i的搜尋狀態(tài)flag1 iunlabbled，則令其費用f1 ig1 i+h1' i，link1iinodemin insert1 i；·假如節(jié)點i的flag1 ilabbled，計算節(jié)點i新的費用g1'i g1 inodemin+從inodemin到i的實際費用，若g1' i g1 i，令g1 ig1'i ，link1 iinodemin，decrease1 i；否則繼續(xù)。·若flag1 iscanned，計算g1'i g1 inodemin+從inodemin到i的實際費用，若g1' ig1 i，令g1 ig1' i，link1iinodemin，flag1 ilabbled，inertl i；·推斷前向搜尋是否舉行了20步，是跳轉(zhuǎn)至(4)(第一次切換)或(6)(其次次以后的切換)