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

【相似文獻】

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

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

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

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

4 梁毅;周剛;;基于定位點和路徑復用的大型多人在線游戲?qū)ぢ匪惴╗J];計算機應用;2010年12期

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

8 劉婷;改進人工蜂群算法及其在多用戶檢測中的應用[D];天津大學;2013年

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

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

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

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

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

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

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

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

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

7 荊東星;人工神經(jīng)網(wǎng)絡在游戲?qū)ぢ分械膽醚芯縖D];長沙理工大學;2010年

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

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

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

本文編號：2743936