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

【文章來源】：揚州大學江蘇省

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

【學位級別】：碩士

【部分圖文】：

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

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

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

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



本文編號：2917211