路網(wǎng)尋徑中的A星算法改進(jìn).pdf

1、隨著經(jīng)濟(jì)的發(fā)展，城市的地理信息數(shù)據(jù)呈爆炸式增長(zhǎng)且城市路網(wǎng)的結(jié)構(gòu)也變得日益復(fù)雜。能否從復(fù)雜的城市路網(wǎng)中幾乎實(shí)時(shí)地找出從出發(fā)地到日的地的最短路線越發(fā)受到老百姓的關(guān)注。A星算法作為一種經(jīng)典的啟發(fā)式尋路算法，廣泛用于城市交通尋路。隨著時(shí)代的前進(jìn)，多種改進(jìn)A星算法已被人們提出。其中以二叉堆存儲(chǔ)結(jié)構(gòu)代替?zhèn)鹘y(tǒng)OPEN表的線性存儲(chǔ)結(jié)構(gòu)的改進(jìn)令人矚目，雖效率提升明顯但逐漸難以滿足用戶需求。本文在此背景下對(duì)上述算法展開了研究。
　　本文首先對(duì)圖和圖搜

2、索算法相關(guān)知識(shí)進(jìn)行了敘述，著重介紹本文研究對(duì)象----A星算法，對(duì)其進(jìn)行分析并指出其瓶頸。接著簡(jiǎn)單介紹了已被人提出的A星算法改進(jìn)方案?；趯?duì)上述改進(jìn)方案的研究并結(jié)合較為成熟多核多線程技術(shù)，本文提出了兩種算法改進(jìn)方案。第一種方案是節(jié)點(diǎn)并行擴(kuò)展及OPEN表分治并行查找最小代價(jià)值節(jié)點(diǎn)。該方案讓節(jié)點(diǎn)擴(kuò)展時(shí)可以在鄰接節(jié)點(diǎn)代價(jià)值計(jì)算、節(jié)點(diǎn)是否在OPEN表和CLOSE表中等耗時(shí)讀操作上由多個(gè)子線程并行進(jìn)行，而OPEN表添加節(jié)點(diǎn)或更改節(jié)點(diǎn)代價(jià)值、CLO

3、SE表添加節(jié)點(diǎn)等寫操作由主線程串行進(jìn)行。同時(shí)，為了減少查找OPEN表中最小代價(jià)值節(jié)點(diǎn)的時(shí)間，基于“分治”思想，提出將OPEN表分成多個(gè)節(jié)點(diǎn)更少的表，由多線程并行實(shí)現(xiàn)二叉堆存儲(chǔ)，每個(gè)線程找出單個(gè)表的最小代價(jià)值節(jié)點(diǎn)后交由主線程得出全局的最小代價(jià)值節(jié)點(diǎn)。另一種方案是雙向并行運(yùn)行尋徑。該方案提出開啟兩個(gè)線程同時(shí)分別從起始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)分別朝對(duì)方尋徑，兩個(gè)線程各獨(dú)自擁有OPEN表但共用一個(gè)CLOSE表且對(duì)此表進(jìn)行同步處理，當(dāng)其中一個(gè)線程從其獨(dú)自擁