A算法的改進(jìn)課程設(shè)計(jì)

1、課程設(shè)計(jì)說(shuō)明書(shū) NO.1A*最短路徑算法的改進(jìn)1.課程設(shè)計(jì)的目的本課程設(shè)計(jì)是學(xué)習(xí)數(shù)據(jù)通信與通信網(wǎng)技術(shù)課程必要的教學(xué)環(huán)節(jié)。由于該課程是專業(yè)必修課，需要通過(guò)實(shí)踐鞏固基礎(chǔ)知識(shí)，為使學(xué)生取得最現(xiàn)代化的設(shè)計(jì)技能和研究方法，課程設(shè)計(jì)訓(xùn)練也就成為了一個(gè)重要的教學(xué)環(huán)節(jié)。通過(guò)對(duì)路由算法的設(shè)計(jì)和實(shí)現(xiàn)，達(dá)到進(jìn)一步完善對(duì)通信網(wǎng)基礎(chǔ)及應(yīng)用課程學(xué)習(xí)的效果。2.設(shè)計(jì)方案論證算法具體的形式包括：確定起點(diǎn)的最短路徑問(wèn)題：即已知起始結(jié)點(diǎn)，求最短路徑的問(wèn)題。確定終點(diǎn)的最短路徑問(wèn)題：與確定起點(diǎn)的問(wèn)題相反，該問(wèn)題是已知終結(jié)結(jié)點(diǎn)，求最短路徑的問(wèn)題。在無(wú)向圖中該問(wèn)題與確定起點(diǎn)的問(wèn)題完全等同，在有向圖中該問(wèn)題等同于把所有路徑方向反轉(zhuǎn)的確定起

2、點(diǎn)的問(wèn)題。確定起點(diǎn)終點(diǎn)的最短路徑問(wèn)題：即已知起點(diǎn)和終點(diǎn)，求兩結(jié)點(diǎn)之間的最短路徑。全局最短路徑問(wèn)題：求圖中所有的最短路徑。（1）Floyd求多源、無(wú)負(fù)權(quán)邊的最短路。用矩陣記錄圖。時(shí)效性較差，時(shí)間復(fù)雜度O(V3)。Floyd-Warshall算法（Floyd-Warshall algorithm）是解決任意兩點(diǎn)間的最短路徑的一種算法，可以正確處理有向圖或負(fù)權(quán)的最短路徑問(wèn)題。Floyd-Warshall算法的時(shí)間復(fù)雜度為O(N3)，空間復(fù)雜度為O(N2)。Floyd-Warshall的原理是動(dòng)態(tài)規(guī)劃：設(shè)Di,j,k為從i到j(luò)的只以(1.k)集合中的節(jié)點(diǎn)為中間節(jié)點(diǎn)的最短路徑的長(zhǎng)度。若最短路徑經(jīng)過(guò)點(diǎn)k，

3、則Di,j,k = Di,k,k-1 + Dk,j,k-1；若最短路徑不經(jīng)過(guò)點(diǎn)k，則Di,j,k = Di,j,k-1。因此，Di,j,k = min(Di,k,k-1 + Dk,j,k-1 , Di,j,k-1)。在實(shí)際算法中，為了節(jié)約空間，可以直接在原來(lái)空間上進(jìn)行迭代，這樣空間可降至二維。 沈 陽(yáng) 大 學(xué)課程設(shè)計(jì)說(shuō)明書(shū) NO2Floyd-Warshall算法的描述如下：for k 1 to n do for i 1 to n do for j 1 to n do if (Di,k + Dk,j < Di,j) then Di,j Di,k + Dk,j; 其中Di,j表示由點(diǎn)i到點(diǎn)j

4、的代價(jià)，當(dāng)Di,j為 表示兩點(diǎn)之間沒(méi)有任何連接。（2）Dijkstra求單源、無(wú)負(fù)權(quán)的最短路。時(shí)效性較好，時(shí)間復(fù)雜度為O（V*V+E）。源點(diǎn)可達(dá)的話，O（V*lgV+E*lgV）=>O（E*lgV）。當(dāng)是稀疏圖的情況時(shí)，此時(shí)E=V*V/lgV，所以算法的時(shí)間復(fù)雜度可為O（V2） 。若是斐波那契堆作優(yōu)先隊(duì)列的話，算法時(shí)間復(fù)雜度，則為O（V*lgV + E）。（3）Bellman-Ford求單源最短路，可以判斷有無(wú)負(fù)權(quán)回路（若有，則不存在最短路），時(shí)效性較好，時(shí)間復(fù)雜度O（VE）。Bellman-Ford算法是求解單源最短路徑問(wèn)題的一種算法。單源點(diǎn)的最短路徑問(wèn)題是指：給定一個(gè)加權(quán)有向圖G和源

5、點(diǎn)s，對(duì)于圖G中的任意一點(diǎn)v，求從s到v的最短路徑。與Dijkstra算法不同的是，在Bellman-Ford算法中，邊的權(quán)值可以為負(fù)數(shù)。設(shè)想從我們可以從圖中找到一個(gè)環(huán)路（即從v出發(fā)，經(jīng)過(guò)若干個(gè)點(diǎn)之后又回到v）且這個(gè)環(huán)路中所有邊的權(quán)值之和為負(fù)。那么通過(guò)這個(gè)環(huán)路，環(huán)路中任意兩點(diǎn)的最短路徑就可以無(wú)窮小下去。如果不處理這個(gè)負(fù)環(huán)路，程序就會(huì)永遠(yuǎn)運(yùn)行下去。 而B(niǎo)ellman-Ford算法具有分辨這種負(fù)環(huán)路的能力。A*（A-Star)算法是一種靜態(tài)路網(wǎng)中求解最短路最有效的直接搜索方法。注意是最有效的直接搜索算法。之后涌現(xiàn)了很多預(yù)處理算法（ALT，CH，HL等等），在線查詢效率是A*算法的數(shù)千甚至上萬(wàn)倍。公

6、式表示為： f(n)=g(n)+h(n),其中 f(n) 是從初始點(diǎn)經(jīng)由節(jié)點(diǎn)n到目標(biāo)點(diǎn)的估價(jià)函數(shù)，g(n) 是在狀態(tài)空間中從初始節(jié)點(diǎn)到n節(jié)點(diǎn)的實(shí)際代價(jià)，h(n) 是從n到目標(biāo)節(jié)點(diǎn)最佳路徑的估計(jì)代價(jià)。保證找到最短路徑（最優(yōu)解的）條件，關(guān)鍵在于估價(jià)函數(shù)h(n)的選?。?沈 陽(yáng) 大 學(xué)課程設(shè)計(jì)說(shuō)明書(shū) NO.3估價(jià)值h(n)<= n到目標(biāo)節(jié)點(diǎn)的距離實(shí)際值，這種情況下，搜索的點(diǎn)數(shù)多，搜索范圍大，效率低。但能得到最優(yōu)解。并且如果h(n)=d(n)，即距離估計(jì)h(n)等于最短距離，那么搜索將嚴(yán)格沿著最短路徑進(jìn)行，此時(shí)的搜索效率是最高的。如果估價(jià)值>實(shí)際值,搜索的點(diǎn)數(shù)少，搜索范圍小，效率高，但不能

7、保證得到最優(yōu)解。 算法是一種啟發(fā)式搜索算法, 在路徑規(guī)劃中得到廣泛的應(yīng)用, 其中啟發(fā)函數(shù)的設(shè)計(jì)尤其重要。本文針對(duì)路徑規(guī)劃問(wèn)題, 對(duì)A* 算法作了以下改進(jìn): 一是在估價(jià)函數(shù)中考慮以距離和方向兩個(gè)要素, 通過(guò)歸一化處理解決了單位不統(tǒng)一的問(wèn)題; 二是利用 k- d樹(shù)空間索引結(jié)構(gòu), 動(dòng)態(tài)加載節(jié)點(diǎn)信息, 減小內(nèi)存使用空間。實(shí)驗(yàn)結(jié)果表明, 改進(jìn)后的A* 算法的搜索效率得到了明顯的提高。最經(jīng)典的最短路徑搜索算法是 Dijkstra算法,屬于遍 歷搜索, 它簡(jiǎn)單易用并總能搜索到最短路徑。但是當(dāng)網(wǎng) 絡(luò)中節(jié)點(diǎn)數(shù)較多時(shí),該算法搜索的結(jié)點(diǎn)數(shù)量會(huì)很大,效率非常低。因此有人提出了啟發(fā)式搜索算法,如: 局部擇 優(yōu)搜索法、最

8、好優(yōu)先搜索法、A*算法等。啟發(fā)式搜索就是 在狀態(tài)空間中, 對(duì)每一個(gè)搜索的位置進(jìn)行評(píng)估, 得到最好的位置,從而在這個(gè)位置進(jìn)行搜索直到搜索到目標(biāo)為止。 目前在路徑優(yōu)化領(lǐng)域, 最流行的啟發(fā)式搜索算法當(dāng)屬由 H ar,t Nilsson, Raphael等人首先提出的 A* 算法。它利用啟發(fā)函數(shù)來(lái)估計(jì)任意點(diǎn)到目標(biāo)點(diǎn)的遠(yuǎn)近程度, 從而減少 搜索空間, 提高搜索效率。許多文獻(xiàn)都對(duì) A* 算法進(jìn)行了研究, 并且都提出在估價(jià)函數(shù)中引入距離和方向兩個(gè)要素。但是距離和方向的單位是不統(tǒng)一的,所以在利用時(shí)會(huì)出現(xiàn)一些問(wèn)題, 本文針對(duì)這一問(wèn)題進(jìn)行了研究,并對(duì)估價(jià)函數(shù)進(jìn)行了改進(jìn)。另外,為了進(jìn)一步提高算法的運(yùn)行效率,本文在算

9、法運(yùn)行結(jié)構(gòu)上,采用 k- d樹(shù)空間索引結(jié)構(gòu),降低內(nèi)存存儲(chǔ)空間。實(shí)驗(yàn)結(jié)果證明了改進(jìn)后算法的合理性和可行性。3.設(shè)計(jì)的過(guò)程與分析 A*算法是建立在Dijkstra和 BFS(最好優(yōu)先搜索 )算法基礎(chǔ)上的。它的整體框架采用遍歷搜索法, 但是它采 用了啟發(fā)函數(shù)來(lái)估計(jì)地圖上任意點(diǎn)到目標(biāo)點(diǎn)的費(fèi)用, 從而可以很好地選擇搜索方向。A*算法引入了當(dāng)前節(jié)點(diǎn)j的啟發(fā)函數(shù) f*( j),當(dāng)前節(jié)點(diǎn) j的啟發(fā)函數(shù)定義為: f*(j)=g(j)+h*(j)(1)其中 g(j)是從起點(diǎn)到當(dāng)前節(jié)點(diǎn) j的實(shí)際費(fèi)用的量度, h*(j)是從當(dāng)前節(jié)點(diǎn)j到終點(diǎn)的最小費(fèi)用的估計(jì)。 沈 陽(yáng) 大 學(xué)課程設(shè)計(jì)說(shuō)明書(shū) NO.4注意到若 h *(j

10、) = 0,即沒(méi)有利用任何全局信息,這時(shí)A* 算法就變成了普通的 Dijkstra算法。因此普通的Dijkstra算法可 看作 A* 算法的特殊情形。h* (j)要滿足相容性條件: 即不能高于節(jié)點(diǎn) j到終點(diǎn)的實(shí)際最小費(fèi)用?？梢宰C明,如果估價(jià)函數(shù)滿足相容性條件, 且原問(wèn)題存在最優(yōu)解,則 A* 算 法一定能夠求出最優(yōu)路徑 。A* 算法的優(yōu)點(diǎn)在于利用啟發(fā)函數(shù), 使搜索方向更加智能的趨向于終點(diǎn),所以其搜索深度較小, 搜索的節(jié)點(diǎn)數(shù)少,故占用存儲(chǔ)空間少,如圖 1所示。 圖1 A*算法與Dijkstra算法搜索區(qū)域?qū)Ρ?A* 算法的估價(jià)函數(shù) A* 算法的關(guān)鍵在于設(shè)計(jì)一個(gè)合適的啟發(fā)函數(shù)。有文 獻(xiàn)對(duì)其特點(diǎn)進(jìn)行了

11、分析, 認(rèn)為啟發(fā)函數(shù) f* (j)值是非遞減 的,只要能夠滿足相容性條件即估價(jià)函數(shù) h* ( j)小于節(jié)點(diǎn) j到目標(biāo)點(diǎn)的實(shí)際費(fèi)用,它生成的路徑一定是最優(yōu)的。許多文獻(xiàn)都在估價(jià)函數(shù)的構(gòu)造中引入了距離和方向兩個(gè)要素 ,即: h*(j) = w1* L+w2*如圖2所示。其中 L 表示當(dāng)前節(jié)點(diǎn)到終點(diǎn)的歐氏距離,表示起點(diǎn)到當(dāng)前節(jié)點(diǎn)的線段與當(dāng)前節(jié)點(diǎn)到終點(diǎn)的線段的夾角即 SjE,有文獻(xiàn)也用到了中間節(jié)點(diǎn)與關(guān)聯(lián)節(jié)點(diǎn)的線段和關(guān)聯(lián)節(jié)點(diǎn)與終點(diǎn)的線段夾角 NjE。w1和w2分別是距離和角度的加權(quán)值,w1和w2 的取值范圍分別為 055- 0.65和0.35-0.45。但距離和角度的單位不統(tǒng) 一的問(wèn)題不能忽略,即使角度的

12、單位為弧度、距離的單位 為千米,它們之間也很有可能出現(xiàn)距離值遠(yuǎn)大于角度值 (即 L )的情況,特別是在大區(qū)域路徑規(guī)劃過(guò)程中,問(wèn)題更明顯。 沈 陽(yáng) 大 學(xué)課程設(shè)計(jì)說(shuō)明書(shū) NO.5而當(dāng) L時(shí), 方向不再有約束力,而使得估價(jià)函數(shù)失去意義。 A* 算法的運(yùn)行結(jié)構(gòu) 當(dāng)構(gòu)造合適的估價(jià)函數(shù)后就要考慮算法的運(yùn)行,目前大多數(shù)方法是將全部數(shù)據(jù)讀入到內(nèi)存當(dāng)中, 然后搜索 最短路徑。從理論上講, A* 算法可以通過(guò)搜索更少的節(jié) 點(diǎn)完成最短路徑的搜索。但是算法運(yùn)行時(shí),必須要考慮兩個(gè)問(wèn)題:一是數(shù)據(jù)讀取的速度。即使可以很快地將數(shù) 據(jù)讀入到內(nèi)存中,我們也還要考慮第二個(gè)問(wèn)題, 即系統(tǒng)內(nèi) 存的大小。如果系統(tǒng)內(nèi)存足夠大,在算法運(yùn)行

13、過(guò)程中,也將會(huì)出現(xiàn)對(duì)同一節(jié)點(diǎn)進(jìn)行重復(fù)的搜索,從而降低算法的運(yùn)行效率。針對(duì)數(shù)據(jù)的讀取問(wèn)題,有學(xué)者提出了基于限 制區(qū)域的A* 算法,減小數(shù)據(jù)的加載量。但是由于A* 算法本身就是一種有損算法, 這種方法很有可能搜索 不到最短路徑, 特別是在考慮道路屬性信息和交通限制信息時(shí)。圖2 估價(jià)函數(shù)構(gòu)造示意圖 改進(jìn)的 A* 算法 （1） A* 算法估價(jià)函數(shù)的改進(jìn)針對(duì)A* 算法估價(jià)函數(shù)所出現(xiàn)的問(wèn)題,我們將距離和角度進(jìn)行歸一化處理,即首先計(jì)算當(dāng)前節(jié)點(diǎn)所有關(guān)聯(lián)節(jié)點(diǎn)相應(yīng)的距離和角度值,然后求它們的平均值即 L，從而使得估價(jià)函數(shù) 變?yōu)? h* (j) = w1* L + w2* (5) 其中: L= L/L (6)=/(

14、7) 歸一化處理以后,只考慮距離和角度對(duì)路徑的貢獻(xiàn),而不必考慮距離和角度的數(shù)值大小。從而避免了距離和 角度單位不統(tǒng)一的問(wèn)題。雖然算法的運(yùn)行要增加計(jì)算 量, 但是我們可以通過(guò)進(jìn)一步減小算法的搜索空間, 改善 算法的運(yùn)行結(jié)構(gòu)來(lái)提高算法的搜索效率。 沈 陽(yáng) 大 學(xué)課程設(shè)計(jì)說(shuō)明書(shū) NO.6 針對(duì)算法運(yùn)行效率的問(wèn)題, 建立k-d樹(shù)空間索引結(jié)構(gòu), 動(dòng)態(tài)加載路網(wǎng)數(shù)據(jù), 從而提高算法效率不失為一個(gè)好方法。 k- d樹(shù)索引結(jié)構(gòu)是 k( k > 1)的二叉檢索樹(shù),主要用于索引多屬性的數(shù)據(jù)或多維點(diǎn)數(shù)據(jù), 它可以通 過(guò)坐標(biāo)快速的訪問(wèn)區(qū)域中的路網(wǎng)數(shù)據(jù)。在算法執(zhí)行過(guò)程中,并非開(kāi)始就裝載所有的路網(wǎng)數(shù)據(jù),而是根據(jù)算法的

15、需要,讀取節(jié)點(diǎn)的相關(guān)信息,或刪除節(jié)點(diǎn)信息,雖然會(huì)增加運(yùn)算過(guò)程中的 I/O運(yùn)算,但是這樣可以避免無(wú)效數(shù)據(jù)的大量裝載,占用大量的內(nèi)存空間。例如,首先判斷當(dāng)前節(jié)點(diǎn)是否在確定的范圍內(nèi), 如果不在則裝載相應(yīng)區(qū)域的數(shù)據(jù),如果在確定的范圍內(nèi),則讀取數(shù)據(jù)的相關(guān)信息,并進(jìn)行節(jié)點(diǎn)擴(kuò)展。然后,在此基礎(chǔ)上計(jì)算路段的啟發(fā)值,搜索最短路徑。 （2） A* 算法的實(shí)現(xiàn)在算法的實(shí)現(xiàn)過(guò)程中,要構(gòu)造兩個(gè)鏈表。分別存儲(chǔ)待擴(kuò)展的節(jié)點(diǎn)和已擴(kuò)展的節(jié)點(diǎn),分別稱為Open表和 Close 表。算法步驟如下: 初始化設(shè)置。將起點(diǎn)信息加載到 Open表中, Close 表賦值為空。令g(j) = 0。 搜索距離當(dāng)前節(jié)點(diǎn)最近的節(jié)點(diǎn),即求f* (j

16、)的最小值,將節(jié)點(diǎn)j從Open表中刪除并加載到Close表中。判斷節(jié)點(diǎn) j是否為終點(diǎn),如果是,終點(diǎn)轉(zhuǎn)向步驟4;否則轉(zhuǎn)向步驟3。判斷節(jié)點(diǎn)j的節(jié)點(diǎn)信息是否在確定的范圍內(nèi),如果在范圍內(nèi),則擴(kuò)展節(jié)點(diǎn)j;否則加載節(jié)點(diǎn)j的節(jié)點(diǎn)信息并進(jìn)行擴(kuò)展。轉(zhuǎn)向步驟2。從節(jié)點(diǎn)j開(kāi)始, 利用回溯的方法輸出起始節(jié)點(diǎn)到目 標(biāo)節(jié)點(diǎn)的最優(yōu)路徑, 以及最短距離,算法終止。在算法的運(yùn)行過(guò)程中,避免了對(duì)同一節(jié)點(diǎn)的重復(fù)訪 問(wèn), 極大地縮小了搜索空間, 從而縮短了算法的運(yùn)行時(shí)間。對(duì)改進(jìn)后的A*算法進(jìn)行了實(shí)驗(yàn), 在估價(jià)函數(shù)歸一化處理前后的最短路徑搜索結(jié)果如圖3(a), (b)所示。圖3a改進(jìn)前的搜索路徑 沈 陽(yáng) 大 學(xué)課程設(shè)計(jì)說(shuō)明書(shū) NO.7

17、圖3b 改進(jìn)后的搜索路徑（3） 實(shí)驗(yàn)采用鄭州市地圖,節(jié)點(diǎn)2606個(gè),路段4127條,在 core i5, 8GB內(nèi)存的 PC機(jī)上運(yùn)行。與其他算法的實(shí)驗(yàn)結(jié)果進(jìn)行了對(duì)比, 結(jié)果見(jiàn)表1。表 中: T 表示臨時(shí)標(biāo)記節(jié)點(diǎn)個(gè)數(shù),N表示永久標(biāo)記節(jié)點(diǎn)的個(gè)數(shù), D表示規(guī)劃路徑長(zhǎng)度。表1 算法比較圖4 臨時(shí)標(biāo)記節(jié)點(diǎn)個(gè)數(shù)比較 沈 陽(yáng) 大 學(xué)課程設(shè)計(jì)說(shuō)明書(shū) NO.8圖5 永久標(biāo)記節(jié)點(diǎn)個(gè)數(shù)比較 將表1數(shù)據(jù)中的臨時(shí)標(biāo)記節(jié)點(diǎn),永久標(biāo)記節(jié)點(diǎn)比較關(guān) 系用圖4、圖5表示。通過(guò)實(shí)驗(yàn)由圖4可以看出,歸一化處理后的A* 算法的搜索區(qū)域明顯減小,由表1可以看出 A* 算法的搜索效率要比 Dijkstra算法的搜索效率高。由圖4、圖5可知

18、,改進(jìn)后的A* 算法的搜索效率明顯要高,在利用 k- d樹(shù)建立 空間索引結(jié)構(gòu)以后,使得搜索的點(diǎn)數(shù)明顯減少,特別是在區(qū)域比較大時(shí),改進(jìn)后的A* 算法的效率提高得更加明顯。需要指出的是, 由于A* 算法本身就是有損算法,所以其尋找到的路徑長(zhǎng)度一般要比 Dijkstra算法的規(guī)劃結(jié)果要長(zhǎng),但由于所選的道路更加合理,所以改進(jìn)后算法的搜索結(jié)果更加實(shí)用。4設(shè)計(jì)體會(huì)通過(guò)這次的課程設(shè)計(jì)，利用A*算法求解最短路徑，加深了對(duì)A*算法的了解與認(rèn)識(shí)。課程設(shè)計(jì)環(huán)節(jié)中把教材里面的理論知識(shí)與實(shí)踐聯(lián)系起來(lái)，利用理論知識(shí)指導(dǎo)實(shí)踐仿真，取得很多的收獲。學(xué)習(xí)這個(gè)算法開(kāi)始的時(shí)候會(huì)覺(jué)得比較難，花了一天的時(shí)間看資料理解算法的原理。在知道

19、原理后的第二天開(kāi)始編寫(xiě)代碼，同樣也花了一天時(shí)間。最后是程序的顯示的優(yōu)化。總之通過(guò)學(xué)習(xí)這個(gè)算法編寫(xiě)程序，可以慢慢的從參考別人的代碼轉(zhuǎn)變自己知道原理后編寫(xiě)代碼這個(gè)過(guò)程會(huì)比較慢需要不斷的聯(lián)系。A* 算法作為一種啟發(fā)式搜索算法在路徑規(guī)劃中得到 了非常廣泛的應(yīng)用。利用啟發(fā)函數(shù)減小搜索空間,從而提高搜索效率,因此啟發(fā)函數(shù)在 A* 算法中起著關(guān)鍵的作用。針對(duì)A* 算法啟發(fā)函數(shù)中距離和角度兩個(gè)要素單 沈 陽(yáng) 大 學(xué)課程設(shè)計(jì)說(shuō)明書(shū) NO.9位不統(tǒng)一的問(wèn)題做了研究,提出將距離和角度歸一化處理,并且利用 k-d樹(shù)的空間索引結(jié)構(gòu),減少搜索空間。試驗(yàn)結(jié)果表明,改進(jìn)后的A* 算法的效率明顯提高。5參考文獻(xiàn) 1T.H.Co

20、rmen,C.E.Leiserson,R.L.Rives,teta.lIntroductiontoAlgorithmsM . McGraw- H il,l 2001. 2 StevenM. LaVatle P lanning A lgorithm sM . Cambridge University Press, 2006. 3李擎，宋頂立.兩種改進(jìn)的最優(yōu)路徑規(guī)劃算法J.北京科技大學(xué)學(xué)報(bào)，2011.4周春輝，李詩(shī)高.Dijkstra算法與A算法研究J.軟件導(dǎo)刊，2007.5馬進(jìn)通信網(wǎng)分析M北京：人民交通出版社，2003 沈 陽(yáng) 大 學(xué)課程設(shè)計(jì)說(shuō)明書(shū) NO.10附錄部分程序代碼：package c

21、om.ubird.astar.core.exception;public class AStarPositionException extends RuntimeException private static final long serialVersionUID = 5968574301453821996L; public AStarPositionException(String msg) super(msg); package com.ubird.astar.core;import java.util.ArrayList;import java.util.HashMap;import

22、java.util.List;import java.util.Map;public class AStarMap private List<AStarNode> openList = new ArrayList(); private Map<String, AStarNode> closeMap = new HashMap(); private boolean isFind = false; private List<AStarNode> path = new ArrayList(); public static final int STATE_BARRI

23、ER = 2; AStarNode target; AStarNode source; int astarData; public AStarMap(int xGridNum, int yGridNum) this.astarData = new intyGridNumxGridNum; this.source = new AStarNode(0, 0); this.target = new AStarNode(xGridNum - 1, yGridNum - 1); public AStarNode getTarget() return this.target; 沈 陽(yáng) 大 學(xué)課程設(shè)計(jì)說(shuō)明書(shū)

24、 NO.11public AStarNode getSource() return this.source; public int getAStarData() return this.astarData; public List<AStarNode> find() init(); AStarNode current = null; while (!isEnd() && (!isFind() current = getMinFNodeFromOpenList(); if (isAchieve(current) buildPath(current); this.isF

25、ind = true; else add2CloseMap(current); for (AStarNode neighbor : getNeighbor(current) if (neighbor = null) | (isInCloseMap(neighbor) | (isCanNotGo(current, neighbor) continue; boolean isBetter = true; AStarNode nodeFromOpenList = getNodeFromOpenList(neighbor); if (nodeFromOpenList != null) neighbor

26、 = nodeFromOpenList; int tg = neighbor.distinctG(current); isBetter = tg <= neighbor.getG(); else add2OpenList(neighbor); if (isBetter) neighbor.reCalculatorGAndH(current, this.target); return this.path; 沈 陽(yáng) 大 學(xué)課程設(shè)計(jì)說(shuō)明書(shū) NO.12private AStarNode getNodeFromOpenList(AStarNode node) for (AStarNode open

27、Node : this.openList) if (openNode.equals(node)return openNode;return null;private boolean isCanNotGo(AStarNode from, AStarNode to)if (isBarrier(to) return true;int offsetX = from.getX() - to.getX();int offsetY = from.getY() - to.getY();return (Math.abs(offsetX) = 1) && (Math.abs(offsetY) =

28、1) && (offsetX = 1) && (offsetY = -1) && (isValidX(from.getX() - 1) && (2 = this.astarDatafrom.getY()(from.getX() - 1) | (isValidY(from.getY() + 1) && (2 = this.astarData(from.getY() + 1)from.getX() | (offsetX = 1) && (offsetY = 1) && (isValidY

29、(from.getY() - 1) && (2 = this.astarData(from.getY() - 1)from.getX() | (isValidX(from.getX() - 1) && (2 = this.astarDatafrom.getY()(from.getX() - 1) | (offsetX = -1) && (offsetY = 1) && (isValidX(from.getX() + 1) && (2 = this.astarDatafrom.getY()(from.getX() +

30、 1) | (isValidY(from.getY() - 1) && (2 = this.astarData(from.getY() - 1)from.getX() | (offsetX = -1) && (offsetY = -1) && (isValidX(from.getX() + 1) && (2 = this.astarDatafrom.getY()(from.getX() + 1) | (isValidY(from.getY() + 1) && (2 = this.astarData(from.get

31、Y() + 1)from.getX();private boolean isValidX(int x)return (x >= 0) && (x < this.astarData0.length);private boolean isValidY(int y) return (y >= 0) && (y < this.astarData.length); private AStarNode getMinFNodeFromOpenList() int index = 0; int minF = (AStarNode)this.openLis

32、t.get(index).getF(); int length = this.openList.size(); 沈 陽(yáng) 大 學(xué)課程設(shè)計(jì)說(shuō)明書(shū) NO.13for (int i = 1; i < length; i+) AStarNode aStarNode = (AStarNode)this.openList.get(i); if (minF > aStarNode.getF() minF = aStarNode.getF(); index = i; return (AStarNode)this.openList.remove(index); private boolean isAc

33、hieve(AStarNode current) return current.equals(this.target); private void init() initParameter(); initOpenListAndCloseMap(); addSource2OpenList(); private void initParameter() this.isFind = false; this.source.init(this.target); this.path.removeAll(this.path); private void initOpenListAndCloseMap() c

34、learOpenList(); this.closeMap.clear(); public void clearOpenList() this.openList.removeAll(this.openList); private void addSource2OpenList() add2OpenList(this.source); 沈 陽(yáng) 大 學(xué)課程設(shè)計(jì)說(shuō)明書(shū) NO.14 private void add2OpenList(AStarNode node) this.openList.add(node); private void add2CloseMap(AStarNode node) th

35、is.closeMap.put(node.toString(), node); private boolean isFind() return this.isFind; private boolean isEnd() return this.openList.size() = 0; public void loadData(int data, int barrierVal, int clearVal) if (data = null) return; if (data.length != this.astarData.length) | (this.astarData0.length != d

36、ata0.length) throw new RuntimeException("new data should be as large as the old astar map' data"); for (int i = 0; i < this.astarData.length; i+) for (int j = 0; j < this.astarDatai.length; j+) if (dataij = barrierVal) this.astarDataij = 2; else if (dataij = clearVal) this.astarD

37、ataij = 0; public void initTargetAndSource(int x, int y) this.source.setX(this.target.getX(); this.source.setY(this.target.getY(); this.target.setX(x); this.target.setY(y); package com.ubird.astar.core; 沈 陽(yáng) 大 學(xué)課程設(shè)計(jì)說(shuō)明書(shū) NO.15import com.ubird.astar.core.exception.AStarPositionException;public class ASt

38、arNode implements Comparable<AStarNode> private static final int G_1 = 10; private static final int G_2 = 14; private static final int G_3 = 10; private static final int G_4 = 14; private static final int G_5 = 10; private static final int G_6 = 14; private static final int G_7 = 10; private s

39、tatic final int G_8 = 14; private static final int G_0 = 10; private int g; private int h; private int f; private int x; private int y; private AStarNode father; public AStarNode(int x, int y) this.x = x; this.y = y; public int getX() return this.x; public void setX(int x) this.x = x; public int get

40、Y() return this.y; public void setY(int y) this.y = y; public AStarNode getFather() return this.father; 沈 陽(yáng) 大 學(xué)課程設(shè)計(jì)說(shuō)明書(shū) NO.16public void setFather(AStarNode father) this.father = father; public void init(AStarNode target) this.g = 0; this.h = heuristicCostEstimate(this, target); this.f = (this.g + th

41、is.h); public int heuristicCostEstimate(AStarNode source, AStarNode target) return (Math.abs(source.x - target.x) + Math.abs(source.y - target.y) * 10; public int compareTo(AStarNode o) return this.f < o.f ? -1 : 1; public boolean equals(Object obj) if (obj = null) | (!(obj instanceof AStarNode)

42、return false; AStarNode node = (AStarNode)obj; return (node.x = this.x) && (node.y = this.y); public String toString() return this.x + ", " + this.y; public void reCalculatorGAndH(AStarNode father, AStarNode target) this.g = distinctG(father); this.h = heuristicCostEstimate(this, t

43、arget); this.f = (this.g + this.h); this.father = father; 沈 陽(yáng) 大 學(xué)課程設(shè)計(jì)說(shuō)明書(shū) NO.17public int distinctG(AStarNode father) int offsetX = this.x - father.x; int offsety = this.y - father.y; int distinct = 0; if (offsetX = 0) && (offsety = -1) distinct = 10; else if (offsetX = 1) && (offsety

44、 = -1) distinct = 14; else if (offsetX = 1) && (offsety = 0) distinct = 10; else if (offsetX = 1) && (offsety = 1) distinct = 14; else if (offsetX = 0) && (offsety = 1) distinct = 10; else if (offsetX = -1) && (offsety = 1) distinct = 14; else if (offsetX = -1) &&

45、amp; (offsety = 0) distinct = 10; else if (offsetX = -1) && (offsety = -1) distinct = 14; else throw new AStarPositionException("Unvalid relation between current node(" + this + ") and fater node(" + father + ")"); return distinct + father.g; public int getG() r

46、eturn this.g; public boolean isBetter(AStarNode node) return isGBetter(node); public boolean isGBetter(AStarNode node) return this.g + distinctG(node) < node.g; 沈 陽(yáng) 大 學(xué)課程設(shè)計(jì)說(shuō)明書(shū) NO.18public boolean isFBetter(AStarNode node) return this.f < node.f; public int getF() return this.f; package com.ubi

47、rd.astar.demo;import com.ubird.astar.ui.AStarMenuBar;import com.ubird.astar.ui.AstarPanel;import com.ubird.astar.ui.ControlPanel;import com.ubird.astar.ui.StatusPanel;import com.ubird.astar.ui.UFrame;import java.awt.Container;import javax.swing.SwingUtilities;public class AStarDemo public static voi

48、d main(String args) SwingUtilities.invokeLater(new Runnable() public void run() UFrame frame = new UFrame(); AstarPanel astarPanel = new AstarPanel(15, 15, 60, 40); StatusPanel statusPanel = new StatusPanel(); astarPanel.setStatusPanel(statusPanel); frame.getContentPane().add(astarPanel, "Cente

49、r"); frame.getContentPane().add(new ControlPanel(astarPanel), "North"); frame.getContentPane().add(statusPanel, "South"); frame.setJMenuBar(new AStarMenuBar(astarPanel); frame.pack(); frame.setVisible(true); frame.setDefaultCloseOperation(3); astarPanel.requestFocus(); ); 沈 陽(yáng) 大 學(xué)課程設(shè)計(jì)說(shuō)明書(shū) NO.19在算法的實(shí)現(xiàn)過(guò)程中, 要構(gòu)造兩個(gè)鏈表。分別存儲(chǔ) 待擴(kuò)展的節(jié)點(diǎn)和已擴(kuò)展的節(jié)點(diǎn), 分別稱為 Open表和 C lose 表。