【摘要】：隨著經(jīng)濟(jì)的發(fā)展,最優(yōu)路徑應(yīng)用領(lǐng)域漸廣,如路網(wǎng)導(dǎo)航、游戲行業(yè)、物流行業(yè)等。其中,路網(wǎng)導(dǎo)航備受廣大學(xué)者的關(guān)注。隨著路網(wǎng)數(shù)據(jù)的日益龐大,常規(guī)尋路算法的尋路性能稍顯不足,不能快速地解決在龐大的路網(wǎng)中尋找任意兩點(diǎn)間路徑的問題。當(dāng)前使用較廣的尋路算法為分層算法。分層的思想是將詳細(xì)路網(wǎng)中權(quán)重較高的節(jié)點(diǎn)和路徑段抽象成一個新的交通路網(wǎng),通過合理地切換詳細(xì)路網(wǎng)和新路網(wǎng)使得尋路算法獲得較好的時空性能。雖然分層算法優(yōu)化了在龐大的地圖數(shù)據(jù)中尋路的性能,但是其尋路的質(zhì)量較A*算法相比有所下降。針對這個問題,本文借鑒了分層的思想、小世界網(wǎng)絡(luò)模型和路由理論等理論,給出了一種在保證路徑質(zhì)量的前提下提升尋路效率的尋路策略：基于小世界模型的啟發(fā)式尋路算法(Heuristic path finding algorithm based on small world model,簡稱 HPAS算法)。第一,路網(wǎng)分區(qū)。借鑒于分層算法中分層的思想和小世界網(wǎng)絡(luò)模型,通過對交通路網(wǎng)進(jìn)行聚類分析,將聚類結(jié)果中的各個簇劃分成不同區(qū)。第二,設(shè)置邊界路由節(jié)點(diǎn)和內(nèi)部路由節(jié)點(diǎn),并將相鄰路由節(jié)點(diǎn)之間的最優(yōu)路徑預(yù)存到緩存中。借鑒路由理論中的外部網(wǎng)關(guān)協(xié)議中路由器的功能,將各區(qū)中符合條件的節(jié)點(diǎn)設(shè)置成邊界路由節(jié)點(diǎn)或內(nèi)部路由節(jié)點(diǎn),相鄰路由節(jié)點(diǎn)之間的路徑可通過預(yù)處理階段求解出來并進(jìn)行緩存。第三,尋路階段。利用A*算法在各個分區(qū)中的邊界路由節(jié)點(diǎn)和內(nèi)部路由節(jié)點(diǎn)之間尋找最優(yōu)路徑。實(shí)驗(yàn)由路徑計(jì)算模塊、緩存模塊、地圖數(shù)據(jù)庫存取模塊和用戶請求處理模塊等組成。通過對美國東西部路網(wǎng)數(shù)據(jù)的測試表明,不同粒度的聚類在不同程度上提高了HPAS算法的尋路效率。但是較大粒度的聚類也會在一定程度上加大了所求解的路徑長度與最短路徑長度之間的偏差。仿真實(shí)驗(yàn)結(jié)果表明在不同的一級劃分中平均路徑長度與最優(yōu)路徑長度的偏差僅為0.03%。通過HPAS算法與A*算法、雙向A*算法和基于層次結(jié)構(gòu)的A*算法在尋路效率和路徑質(zhì)量上的實(shí)驗(yàn)數(shù)據(jù)的對比,可以看出改進(jìn)型A*算法在地圖規(guī)模較大的情況下表現(xiàn)出來較好的性能。
【學(xué)位授予單位】：華中師范大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：U495

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 蔣愷;;淺談游戲中自動尋路算法的實(shí)現(xiàn)與應(yīng)用[J];中國新通信;2018年02期

2 郭曉利;田俊輝;;游戲中自動尋路算法的改進(jìn)研究[J];福建電腦;2017年03期

3 蒯銳;洪金敏;;自動尋路A*算法的應(yīng)用及優(yōu)化設(shè)計(jì)[J];上海應(yīng)用技術(shù)學(xué)院學(xué)報(bào)(自然科學(xué)版);2014年02期

4 梁毅;周剛;;基于定位點(diǎn)和路徑復(fù)用的大型多人在線游戲?qū)ぢ匪惴╗J];計(jì)算機(jī)應(yīng)用;2010年12期

5 趙清松;;游戲開發(fā)中一種新的高效尋路算法——B~*尋路算法[J];程序員;2010年08期

6 鄧先習(xí);丁順利;杜蕊;;基于二元堆的A*算法及其在游戲地圖尋路中的應(yīng)用[J];福建電腦;2008年08期

7 李建元;師軍;曹菡;汪西莉;;一種分層尋路算法中的域值放棄策略[J];計(jì)算機(jī)應(yīng)用;2007年02期

8 蔡方方;楊士穎;張小鳳;劉東平;;雙層A~*算法在游戲?qū)ぢ贩矫娴难芯縖J];微型電腦應(yīng)用;2010年01期

9 蘆雨;;尋路[J];中國研究生;2019年05期

10 高天寒;劉文成;;面向3D場景智能尋路技術(shù)綜述[J];計(jì)算機(jī)工程與應(yīng)用;2017年01期

相關(guān)會議論文 前10條

1 徐一;楊靜;任志剛;楊迅幸;;基于學(xué)習(xí)的煙花算法[A];2018中國自動化大會(CAC2018)論文集[C];2018年

2 熊薇薇;吳懷宇;;一種改進(jìn)的角點(diǎn)檢測算法[A];中國計(jì)量協(xié)會冶金分會2009年年會論文集[C];2009年

3 陶麗;張自力;丁曉明;;一種適用于動態(tài)重構(gòu)的聯(lián)盟形成算法[A];2008年計(jì)算機(jī)應(yīng)用技術(shù)交流會論文集[C];2008年

4 張?zhí)m平;;談小學(xué)一年級算法多樣化的優(yōu)化[A];中華教育理論與實(shí)踐科研論文成果選編（下）[C];2007年

5 楊紅斌;;計(jì)劃量算法的優(yōu)化[A];第四屆全國醫(yī)院藥劑科建設(shè)與管理學(xué)術(shù)研討會論文集[C];2012年

6 許倫輝;傅惠;徐建閩;;基于分形維數(shù)的交通流預(yù)測模型及算法研究[A];2003年中國智能自動化會議論文集（下冊）[C];2003年

7 林克旺;;基于分層網(wǎng)絡(luò)實(shí)現(xiàn)高效的自穩(wěn)定的選舉算法[A];計(jì)算機(jī)技術(shù)與應(yīng)用進(jìn)展——全國第17屆計(jì)算機(jī)科學(xué)與技術(shù)應(yīng)用（CACIS）學(xué)術(shù)會議論文集（下冊）[C];2006年

8 徐英鐘;高震;李波;;基于禁忌搜索的蟻群算法求解旅行商問題[A];第四屆中國智能計(jì)算大會論文集[C];2010年

9 葉衍;樓榮生;何永保;;自然聯(lián)結(jié)的優(yōu)化算法[A];第十二屆全國數(shù)據(jù)庫學(xué)術(shù)會議論文集[C];1994年

10 趙唯;;晶粒度評級的改進(jìn)算法[A];中國圖象圖形科學(xué)技術(shù)新進(jìn)展——第九屆全國圖象圖形科技大會論文集[C];1998年

相關(guān)重要報(bào)紙文章 前10條

1 北京商報(bào)記者 郭秀娟 姚倩;九安醫(yī)療“調(diào)結(jié)構(gòu)”尋路[N];北京商報(bào);2019年

2 本報(bào)記者 路虹;內(nèi)外承壓，土耳其經(jīng)濟(jì)尋路難[N];國際商報(bào);2019年

3 本報(bào)記者 崔呂萍;制造業(yè)尋路，問道葛紅林[N];人民政協(xié)報(bào);2019年

4 本報(bào)通訊員 張小寒;尋路“未來村”[N];威海日報(bào);2018年

5 本報(bào)記者 謝雷鳴;尋路歐洲：打開另一端市場的方式[N];中國貿(mào)易報(bào);2018年

6 本報(bào)記者 趙娜;連續(xù)創(chuàng)業(yè)者尋路知識付費(fèi)：“內(nèi)容+服務(wù)”機(jī)會幾何？[N];21世紀(jì)經(jīng)濟(jì)報(bào)道;2018年

7 本報(bào)通訊員 閆寶明 v斌宏;一心尋路為窮親[N];甘肅經(jīng)濟(jì)日報(bào);2018年

8 中國出版?zhèn)髅缴虉?bào)記者 江海;尋路縣級店舉辦書展新徑[N];中國出版?zhèn)髅缴虉?bào);2018年

9 記者 孫磊;尋路中國：從主題之變看發(fā)展之變[N];杭州日報(bào);2018年

10 新華社記者 強(qiáng)勇;“創(chuàng)”中尋路 “新”中求機(jī)[N];黑龍江日報(bào);2017年

相關(guān)博士學(xué)位論文 前10條

1 段琦;基于尋路行為的公共設(shè)施內(nèi)導(dǎo)向標(biāo)識服務(wù)能力的優(yōu)化研究[D];天津大學(xué);2015年

2 李江濤;車載導(dǎo)航路網(wǎng)的胞式化尋路與密度自適應(yīng)[D];清華大學(xué);2015年

3 王冰;人工蜂群算法的改進(jìn)及相關(guān)應(yīng)用的研究[D];北京理工大學(xué);2015年

4 王艷嬌;人工蜂群算法的研究與應(yīng)用[D];哈爾濱工程大學(xué);2013年

5 李美安;普適分布式互斥算法及應(yīng)用[D];電子科技大學(xué);2007年

6 王小根;粒子群優(yōu)化算法的改進(jìn)及其在圖像中的應(yīng)用研究[D];江南大學(xué);2009年

7 白仲添;雞胚神經(jīng)管發(fā)育早期鰓運(yùn)動神經(jīng)的軸突尋路[D];蘭州大學(xué);2011年

8 劉婷;改進(jìn)人工蜂群算法及其在多用戶檢測中的應(yīng)用[D];天津大學(xué);2013年

9 邱劍鋒;人工蜂群算法的改進(jìn)方法與收斂性理論的研究[D];安徽大學(xué);2014年

10 肖建元;保幾何結(jié)構(gòu)算法在等離子體物理中的應(yīng)用[D];中國科學(xué)技術(shù)大學(xué);2017年

相關(guān)碩士學(xué)位論文 前10條

1 李德福;基于小世界模型的啟發(fā)式尋路算法研究[D];華中師范大學(xué);2015年

2 詹海波;人工智能尋路算法在電子游戲中的研究和應(yīng)用[D];華中科技大學(xué);2006年

3 程振興;分布式應(yīng)急救援系統(tǒng)尋路算法研究及仿真實(shí)現(xiàn)[D];北京化工大學(xué);2016年

4 李曉陽;性別、尋路策略、任務(wù)難度與地圖類型對室內(nèi)尋路行為的影響[D];陜西師范大學(xué);2016年

5 吳小玲;基于游客尋路行為的景區(qū)導(dǎo)向標(biāo)識系統(tǒng)評價(jià)研究[D];南京師范大學(xué);2015年

6 劉偉;三維高程地形中的多對象協(xié)同尋路[D];蘭州大學(xué);2006年

7 荊東星;人工神經(jīng)網(wǎng)絡(luò)在游戲?qū)ぢ分械膽?yīng)用研究[D];長沙理工大學(xué);2010年

8 余帥;即時戰(zhàn)略游戲中基于勢場的交互尋路方法[D];河北大學(xué);2014年

9 甄怡;商業(yè)綜合體建筑布局的易讀性與“尋路”[D];同濟(jì)大學(xué);2007年

10 王慶穩(wěn);基于尋路理論的網(wǎng)絡(luò)用戶信息瀏覽行為研究[D];西南大學(xué);2009年

本文編號：2743936