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

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

2、路徑規(guī)劃是車載導(dǎo)航儀的重要功能模塊。在開發(fā)車載導(dǎo)航儀過程中，為了實(shí)現(xiàn)路徑規(guī)劃模塊，對(duì)單車輛路徑規(guī)劃算法舉行了討論。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ù)，一定可以

3、找到從原節(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'ng 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)到目標(biāo)節(jié)點(diǎn)的估量費(fèi)用。啟發(fā)式搜尋算法基本同于改進(jìn)的迪杰斯特拉算法，唯一不同的是前者的費(fèi)用是f'n，而后者為g n。估量費(fèi)用h'

4、; 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)路徑，而且估量費(fèi)用滿足可納性，即h' n小于從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)之間的實(shí)際費(fèi)用，那么通過該算法一定可以找到一條最優(yōu)路徑。前面兩種算法都是從原節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)沒單一方向舉行搜尋的算法。雙向搜尋算法的思想是：不僅舉行從原節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的前向搜尋，而且舉行從目標(biāo)節(jié)點(diǎn)到原節(jié)點(diǎn)的后向搜尋。在單cpu硬件平臺(tái)條件下，兩個(gè)方向的搜尋交替舉行。勝利實(shí)現(xiàn)雙向搜尋有兩個(gè)條件，即合適的搜尋停止條件和前向后向搜尋切換標(biāo)準(zhǔn)。其算法時(shí)光為

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

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

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

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

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

10、令flagl原節(jié)點(diǎn)scanned，其費(fèi)用gl原節(jié)點(diǎn)0，其它節(jié)點(diǎn)的費(fèi)用為無窮。(2)對(duì)原節(jié)點(diǎn)全部后繼節(jié)點(diǎn)i舉行如下操作：·推斷路徑(原節(jié)點(diǎn)，i)是否限制路段，是處理下一個(gè)后繼節(jié)點(diǎn)，否則繼續(xù)；·計(jì)算i的費(fèi)用f1i g1 i+hl'i；·置i的搜尋狀態(tài)flag1 ilabbled；·把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 inodemins

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