發(fā)布時(shí)間：2020-12-14 23:32

　　當(dāng)今社會(huì),隨著科學(xué)的進(jìn)步和發(fā)展,交通網(wǎng)絡(luò)越來越發(fā)達(dá),人們?cè)诼糜�、出差或者其他出行時(shí),不僅會(huì)關(guān)心費(fèi)用問題,而且對(duì)里程和所需要的時(shí)間等問題也特別感興趣。例如,當(dāng)前所在城市到目的地城市的最短距離、以及如何根據(jù)最短距離行駛等。為了更方便出行,急需建立起一個(gè)可實(shí)現(xiàn)最短路徑規(guī)劃的交通咨詢系統(tǒng),如谷歌地圖、百度地圖等均具有相似的功能。此類系統(tǒng)可以方便的解決人們所面臨的有關(guān)交通的問題。此類問題為最短路徑問題,該問題的解決可以在運(yùn)輸系統(tǒng)、電子導(dǎo)航系統(tǒng)以及人工智能等領(lǐng)域中具有重要應(yīng)用,因此具有很重要的實(shí)際應(yīng)用價(jià)值。A*算法是目前最短路徑問題所采用的理論基礎(chǔ),因此是一種非常經(jīng)典的最短路徑算法。常見的尋路、路徑規(guī)劃問題都可由A*算法解決。本文提出了針對(duì)運(yùn)用A*算法尋找出的鋸齒路徑的平滑處理策略,并建立了 A*算法的群體模型,通過比較各種不同方式的環(huán)境地圖,測(cè)試出基于A*算法的路徑尋求算法的實(shí)際表現(xiàn)效果,并分析它們的適用情況和在路徑尋找中的應(yīng)用范圍。本文的主要工作如下:首先,本文對(duì)路徑算法在國(guó)內(nèi)外的應(yīng)用和發(fā)展前景作了簡(jiǎn)單的總結(jié)和說明,并介紹了最短路徑的定義以及現(xiàn)有的幾種最短路徑算法。其次,本文通過對(duì)目前比較主流... 

【文章來源】：揚(yáng)州大學(xué)江蘇省

【文章頁數(shù)】：58 頁

【學(xué)位級(jí)別】：碩士

【部分圖文】：

圖３．３?Ａ＊算法模擬路徑示意圖??圖３．３就是在有障礙物的情況下，Ａ＊算法求出的路徑，它不需要像Ｄｉｊｋｓｔｍ算法一樣，??

?揚(yáng)州大學(xué)碩士學(xué)位論文?１８??圖３．１是用Ｄｉｊｋｓｔｒａ算法對(duì)某一塊區(qū)域進(jìn)行最短路徑的尋找，顏色越深代表邊的距離??越長(zhǎng)，付出的代價(jià)越大。??最佳優(yōu)先搜索算法（ＢＦＳ）算法和Ｄｉｊｋｓｔｒａ算法比較類似，但不同的是ＢＦＳ算法能預(yù)先??評(píng)估任意節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的值。而且ＢＦＳ算法不能保證找到一條最短路徑，它只能保證在??找到近似值的同時(shí)，提高了尋路過程的速度，能迅速的靠近目標(biāo)節(jié)點(diǎn)。??丨?ｆ?？?ｆｉ?Ｉ?ｔ?；?ｊ?＆?＞?Ｉ?｜?＊?ｊ?丨．．ｉ?丨?ｉ?１?ｆ?丨?｛?ｌ??ＺＣ?丁一?ｒＣ?＝—１１Ｌ．１Ｊ．．Ｉ???－丄．ｊｚ?一??ｊ?！?ｉ??二＝１＝講．．ｐ?■二二：＾：二其：??＝：ｐｉ〒二一二十一Ｔ－?＾?Ｊ；，???？」、、■顯?－?：??［?ｊ???＂ＪＪ＇Ｊ；?ｚｔｔ．Ｊ．ＺＺ?Ｚ?Ｚ?ＺｌＩＺ?Ｉ??＇?發(fā)為靈■鐵戀?Ｉ—＼…！??：?－ｉ－．．．．．．??—４，上二—ｉｉ；?－一，￣ｉ?ｈ??：Ｉｐ：「■＇ｊ．??：－－１?愈??Ｉ?Ｉ?Ｉ?Ｉ?Ｉ?Ｉ?Ｉ?Ｉ?ｊ?ｊ?Ｉ?Ｉ?Ｉ?Ｉ?Ｉ?Ｉ?Ｉ?Ｉ?Ｉ?Ｉ?Ｉ?Ｉ?ｊ?１?Ｉ?Ｉ?Ｉ?Ｉ?１??圖３．２?ＢＦＳ算法模擬路徑示意圖??圖３．２顯示就是ＢＦＳ算法找出的路徑，不是非常準(zhǔn)確。這還僅僅是沒有障礙物情況下，??最短路徑都是偏向于直線，如果有障礙物，那么用Ｄｉｊｋｓｔｒａ算法會(huì)非常慢，如果用ＢＦＳ算??法，雖然運(yùn)行速度很快，但是找到路徑未必會(huì)很準(zhǔn)確。而Ａ＊算法則是把ＢＦＳ算法中的啟??發(fā)式思想和傳統(tǒng)的Ｄｉｊｋｓｔｒａ算法融合在一起，又能很快的找到路徑，還能保證路徑的準(zhǔn)確??

）和ＢＦＳ算法（靠近目標(biāo)點(diǎn)的結(jié)點(diǎn)）的信息塊結(jié)合起來。??在Ａ＊算法的術(shù)語中，ｇ（ｎ）表示從初始結(jié)點(diǎn)到任意距離結(jié)點(diǎn)ｎ的代價(jià)，ｈ（ｎ）表示從結(jié)點(diǎn)ｎ到??目標(biāo)點(diǎn)的啟發(fā)式評(píng)估代價(jià)；當(dāng)從初識(shí)點(diǎn)向目標(biāo)點(diǎn)移動(dòng)時(shí)，Ａ＊很好的平衡了這兩者：每次進(jìn)??行主循環(huán)判斷時(shí)，它會(huì)檢查ｆ（ｎ）最小的結(jié)點(diǎn)ｎ，其中ｆ（ｎ）＝ｇ（ｎ）＋ｈ（ｎ）。??啟發(fā)式函數(shù)ｈ（ｎ）則是明確了?Ａ＊從任意結(jié)點(diǎn)ｎ到目標(biāo)結(jié)點(diǎn)的最小代價(jià)評(píng)估值。選擇一??個(gè)好的啟發(fā)式函數(shù)是重要的。??ｌ－ｉｖ．?＾?Ｊｉ?－＇Ｉ１?Ｂ３ａＤｙ１?｜??圖４．１?Ａ＊算法示例圖??如上圖（４．１），我們將搜索區(qū)域劃分成像素點(diǎn)，我們可以用方塊來代替像素點(diǎn)，本圖??可以拆分成７＊６＝４２個(gè)方塊。在Ａ＊算法中需要用到２張列表：ｏｐｅｎ列表，存放所有被考慮??來尋找最短路徑的方塊；ｃｌｏｓｅｄ列表，存放不會(huì)再被考慮的方塊。??我們可以給每個(gè)方塊一個(gè)Ｇ＋Ｈ的值。Ｇ是起始點(diǎn)Ａ到目標(biāo)方塊的移動(dòng)距離。由此我??們可以發(fā)現(xiàn)，起始點(diǎn)Ａ到相鄰的８?jìng)�(gè)小方塊的移動(dòng)量為１，并且該值Ｇ會(huì)隨著目標(biāo)方塊的??移動(dòng)而逐漸增大。Ｈ則是從當(dāng)前方塊到目標(biāo)點(diǎn)的移動(dòng)量的一個(gè)估算值。通常啟發(fā)式函數(shù)就??是Ｈ函數(shù)，啟發(fā)式函數(shù)越精確，搜索出來的路徑就越逼近最優(yōu)值。??對(duì)于距離，如果可以對(duì)角線移動(dòng)，一般設(shè)置為七。如果有不同的地形，那么可以把相??應(yīng)的移動(dòng)量調(diào)整的大一點(diǎn)，例如沼澤、水等等。??

【參考文獻(xiàn)】：
期刊論文
[1]基于改進(jìn)A~*算法的室內(nèi)移動(dòng)機(jī)器人路徑規(guī)劃[J]. 王殿君.  清華大學(xué)學(xué)報(bào)(自然科學(xué)版). 2012(08)
[2]動(dòng)態(tài)不確定環(huán)境下多目標(biāo)路徑規(guī)劃方法[J]. 魏唯,歐陽丹彤,呂帥,馮宇軒.  計(jì)算機(jī)學(xué)報(bào). 2011(05)
[3]移動(dòng)機(jī)器人路徑規(guī)劃技術(shù)綜述[J]. 朱大奇,顏明重.  控制與決策. 2010(07)
[4]未知環(huán)境下改進(jìn)的基于BUG算法的移動(dòng)機(jī)器人路徑規(guī)劃[J]. 康亮,趙春霞,郭劍輝.  系統(tǒng)仿真學(xué)報(bào). 2009(17)



本文編號(hào)：2917211