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

沈陽(yáng)大學(xué)沈陽(yáng)大學(xué)A*最短路徑算法的改進(jìn)i?課程設(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)的確定起點(diǎn)的問(wèn)題。確定起點(diǎn)終點(diǎn)的最短路徑問(wèn)題：即已知起點(diǎn)和終點(diǎn)，求兩結(jié)點(diǎn)之間的最短路徑。全局最短路徑問(wèn)題：求圖中所有的最短路徑。Floyd求多源、無(wú)負(fù)權(quán)邊的最短路。用矩陣記錄圖。時(shí)效性較差，時(shí)間復(fù)雜度0(廠3)。Floyd-Warshall算法(Floyd-Warshallalgorithm)是解決任意兩點(diǎn)間的最短路徑的一種算法，可以正確處理有向圖或負(fù)權(quán)的最短路徑問(wèn)題。Floyd-Warshall算法的時(shí)間復(fù)雜度為0(23)，空間復(fù)雜度為0(^2)。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,則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)行迭代，這樣空間可降至二維。Floyd-Warshall算法的描述如下：fork?1tondofori?1tondoforj?1tondoif(Di,k+Dk,j<Di,j)thenDi,j-Di,k+Dk,j;其中Di,j表示由點(diǎn)i到點(diǎn)j的代價(jià)，當(dāng)Di,j為-表示兩點(diǎn)之間沒(méi)有任何連接。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(廠2)。若是斐波那契堆作優(yōu)先隊(duì)列的話，算法時(shí)間復(fù)雜度，則為O(V*lgV+E)。Bellman-Ford求單源最短路，可以判斷有無(wú)負(fù)權(quán)回路(若有，則不存在最短路)，時(shí)效性較好，時(shí)間復(fù)雜度O(VE)。Bellman-Ford算法是求解單源最短路徑問(wèn)題的一種算法。單源點(diǎn)的最短路徑問(wèn)題是指：給定一個(gè)加權(quán)有向圖G和源點(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)行下去。而Bellman-Ford算法具有分辨這種負(fù)環(huán)路的能力。A*(A-Star)算法是一種靜態(tài)路網(wǎng)中求解最短路最有效的直接搜索方法。注意是最有效的直接搜索算法。之后涌現(xiàn)了很多預(yù)處理算法(ALT,CH,HL等等)，在線查詢效率是A*算法的數(shù)千甚至上萬(wàn)倍。公式表示為：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)的選取：估價(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ù)少，搜索范圍小，效率高，但不能保證得到最優(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樹空間索引結(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)搜索法、最好優(yōu)先搜索法、A*算法等。啟發(fā)式搜索就是在狀態(tài)空間中，對(duì)每一個(gè)搜索的位置進(jìn)行評(píng)估，得到最好的位置,從而在這個(gè)位置進(jìn)行搜索直到搜索到目標(biāo)為止。目前在路徑優(yōu)化領(lǐng)域，最流行的啟發(fā)式搜索算法當(dāng)屬由Har，tNilsson,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)行效率，本文在算法運(yùn)行結(jié)構(gòu)上，米用k-d樹空間索引結(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(shù)(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ì)。注意到若h*j)=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所示。圖1A*算法與Dijkstra算法搜索區(qū)域?qū)Ρ華*算法的估價(jià)函數(shù)A*算法的關(guān)鍵在于設(shè)計(jì)一個(gè)合適的啟發(fā)函數(shù)。有文獻(xiàn)對(duì)其特點(diǎn)進(jìn)行了分析，認(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)題不能忽略,即使角度的單位為弧度、距離的單位為千米，它們之間也很有可能出現(xiàn)距離值遠(yuǎn)大于角度值(即L)的情況,特別是在大區(qū)域路徑規(guī)劃過(guò)程中，問(wèn)題更明顯。而當(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)行過(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*算法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)椋篽*j)=w1*L+w2*(5)其中：L=L/L(6)=/(7)歸一化處理以后，只考慮距離和角度對(duì)路徑的貢獻(xiàn),而不必考慮距離和角度的數(shù)值大小。從而避免了距離和角度單位不統(tǒng)一的問(wèn)題。雖然算法的運(yùn)行要增加計(jì)算量,但是我們可以通過(guò)進(jìn)一步減小算法的搜索空間，改善算法的運(yùn)行結(jié)構(gòu)來(lái)提高算法的搜索效率。針對(duì)算法運(yùn)行效率的問(wèn)題，建立k-d樹空間索引結(jié)構(gòu)，動(dòng)態(tài)加載路網(wǎng)數(shù)據(jù)，從而提高算法效率不失為一個(gè)好方法。k-d樹索引結(jié)構(gòu)是k(k>1)的二叉檢索樹，主要用于索引多屬性的數(shù)據(jù)或多維點(diǎn)數(shù)據(jù)，它可以通過(guò)坐標(biāo)快速的訪問(wèn)區(qū)域中的路網(wǎng)數(shù)據(jù)。在算法執(zhí)行過(guò)程中，并非開始就裝載所有的路網(wǎng)數(shù)據(jù)，而是根據(jù)算法的需要，讀取節(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ā)值，搜索最短路徑。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)的最小值,將節(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開始，利用回溯的方法輸出起始節(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)前的搜索路徑

圖3b改進(jìn)后的搜索路徑實(shí)驗(yàn)采用鄭州市地圖，節(jié)點(diǎn)2606個(gè)，路段4127條，在corei5,8GB內(nèi)存的PC機(jī)上運(yùn)行。與其他算法的實(shí)驗(yàn)結(jié)果進(jìn)行了對(duì)比結(jié)果見表1。表中：T表示臨時(shí)標(biāo)記節(jié)點(diǎn)個(gè)數(shù),N表示永久標(biāo)記節(jié)點(diǎn)的個(gè)數(shù)，D表示規(guī)劃路徑長(zhǎng)度。表1算法比較kT實(shí)驗(yàn)編號(hào)L算法1算法改進(jìn)的'算法tnt|lr11itlvptwlHV11nfvptfrdvptrurnjfwFri?yfzvruntwftvupnfvxxpIwi“Pty”hin|fyIIbwyrwmyipvmby?rbv1WyIwr1ruwrn|i'yvinWilltl|'wrnprinvvMlIlbtIFfywblhiiiyrw圖4臨時(shí)標(biāo)記節(jié)點(diǎn)個(gè)數(shù)比較

100wRfl70605040100wRfl706050403020-*■■圖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可知，改進(jìn)后的A*算法的搜索效率明顯要高,在利用k-d樹建立空間索引結(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è)算法開始的時(shí)候會(huì)覺(jué)得比較難，花了一天的時(shí)間看資料理解算法的原理。在知道原理后的第二天開始編寫代碼，同樣也花了一天時(shí)間。最后是程序的顯示的優(yōu)化。總之通過(guò)學(xué)習(xí)這個(gè)算法編寫程序，可以慢慢的從參考別人的代碼轉(zhuǎn)變自己知道原理后編寫代碼這個(gè)過(guò)程會(huì)比較慢需要不斷的聯(lián)系。A*算法作為一種啟發(fā)式搜索算法在路徑規(guī)劃中得到了非常廣泛的應(yīng)用。利用啟發(fā)函數(shù)減小搜索空間，從而提高搜索效率，因此啟發(fā)函數(shù)在A*算法中起著關(guān)鍵的作用。針對(duì)A*算法啟發(fā)函數(shù)中距離和角度兩個(gè)要素單課程設(shè)計(jì)說(shuō)明書課程設(shè)計(jì)說(shuō)明書NO.#沈陽(yáng)大學(xué)沈陽(yáng)大學(xué)publicintdistinctG(AStarNodefather){intoffsetX=this.x-father.x;intoffsety=this.y-father.y;intdistinct=0;if((offsetX==0)&&(offsety==-1))distinct=10;elseif((offsetX==1)&&(offsety==-1))distinct=14;elseif((offsetX==1)&&(offsety==0))distinct=10;elseif((offsetX==1)&&(offsety==1))distinct=14;elseif((offsetX==0)&&(offsety==1))distinct=10;elseif((offsetX==-1)&&(offsety==1))distinct=14;elseif((offsetX==-1)&&(offsety==0))distinct=10;elseif((offsetX==-1)&&(offsety==-1))distinct=14;elsethrownewAStarPositionException("Unvalidrelationbetweencurrentnode("+this+")andfaternode("+father+")");returndistinct+father.g;}publicintgetG(){returnthis.g;}publicbooleanisBetter(AStarNodenode){returnisGBetter(node);}publicbooleanisGBetter(AStarNodenode){returnthis.g+distinctG(node)<node.g;}publicbooleanisFBetter(AStarNodenode){returnthis.f<node.f;}publicintgetF(){returnthis.f;}[packagecom.ubird.astar.demo;importcom.ubird.astar.ui.AStarMenuBar;importcom.ubird.astar.ui.AstarPanel;importcom.ubird.astar.ui.ControlPanel;importcom.ubird.astar.ui.StatusPanel;importcom.ubird.astar.ui.UFrame;importjava.awt.Container;importjavax.swing.SwingUtilities;publicclassAStarDemo{publicstaticvoidmain(String[]args){SwingUtilities.invokeLater(newRunnable(){publicvoidrun(){UFrameframe=newUFrame();AstarPanelastarPanel=newAstarPanel(15,15,60,40);StatusPanelstatusPanel=newStatusPanel();astarPanel.setStatusPanel(statusPanel);frame.getContentPane().add(astarPanel,"Center");frame.getContentPane().add(newControlPanel(astarPanel),"North");frame.getContentPane().add(statusPanel,"South");frame.setJMenuBar(newAStarMenuBar(astarPanel));frame.pack();frame.setVisible(true);frame.setDefaultCloseOperation(3);astarPanel.requestFocus();}});}}在算法的實(shí)現(xiàn)過(guò)程中，要構(gòu)造兩個(gè)鏈表。分別存儲(chǔ)待擴(kuò)展的節(jié)點(diǎn)和已擴(kuò)展的節(jié)點(diǎn)，分別稱為Open表和Close表。算法步驟如下：1)初始化設(shè)置。將起點(diǎn)信息加載到Open表中，Close表賦值為空。令g(j)=0。2)搜索距離當(dāng)前節(jié)點(diǎn)最近的節(jié)點(diǎn)，即求f*(j)的最小值，將節(jié)點(diǎn)j從Open表中刪除并加載到Close表中。判斷節(jié)點(diǎn)j是否為終點(diǎn)，如果是，終點(diǎn)轉(zhuǎn)向步驟4;否則轉(zhuǎn)向步驟3。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。4)從節(jié)點(diǎn)j開始，利用回溯的方法輸出起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最優(yōu)路徑，以及最短距離，算法終止。在算法的運(yùn)行過(guò)程中，避免了對(duì)同一節(jié)點(diǎn)的重復(fù)訪問(wèn)，極大地縮小了搜索空間，從而縮短了算法的運(yùn)行時(shí)間。2.2A*算法的實(shí)現(xiàn)在算法的實(shí)現(xiàn)過(guò)程中，要構(gòu)造兩個(gè)鏈表。分別存儲(chǔ)待擴(kuò)展的節(jié)點(diǎn)和已擴(kuò)展的節(jié)點(diǎn)，分別稱為Open表和Close表。算法步驟如下：1)初始化設(shè)置。將起點(diǎn)信息加載到Open表中，Close表賦值為空。令g(j)=0。2)搜索距離當(dāng)前節(jié)點(diǎn)最近的節(jié)點(diǎn)，即求f*(j)的最小值，將節(jié)點(diǎn)j從Open表中刪除并加載到Close表中。判斷節(jié)點(diǎn)j是否為終點(diǎn)，如果是，終點(diǎn)轉(zhuǎn)向步驟4;否則轉(zhuǎn)向步驟3。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。4)從節(jié)點(diǎn)j開始，利用回溯的方法輸出起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最優(yōu)路徑，以及最短距離，算法終止。在算法的運(yùn)行過(guò)程中，避免了對(duì)同一節(jié)點(diǎn)的重復(fù)訪問(wèn)，極大地縮小了搜索空間，從而縮短了算法的運(yùn)