沈陽大學沈陽大學A*最短路徑算法的改進i?課程設計的目的本課程設計是學習《數據通信與通信網技術》課程必要的教學環節。由于該課程是專業必修課，需要通過實踐鞏固基礎知識，為使學生取得最現代化的設計技能和研究方法，課程設計訓練也就成為了一個重要的教學環節。通過對路由算法的設計和實現，達到進一步完善對通信網基礎及應用課程學習的效果。2.設計方案論證算法具體的形式包括：確定起點的最短路徑問題：即已知起始結點，求最短路徑的問題。確定終點的最短路徑問題：與確定起點的問題相反，該問題是已知終結結點，求最短路徑的問題。在無向圖中該問題與確定起點的問題完全等同，在有向圖中該問題等同于把所有路徑方向反轉的確定起點的問題。確定起點終點的最短路徑問題：即已知起點和終點，求兩結點之間的最短路徑。全局最短路徑問題：求圖中所有的最短路徑。Floyd求多源、無負權邊的最短路。用矩陣記錄圖。時效性較差，時間復雜度0(廠3)。Floyd-Warshall算法(Floyd-Warshallalgorithm)是解決任意兩點間的最短路徑的一種算法，可以正確處理有向圖或負權的最短路徑問題。Floyd-Warshall算法的時間復雜度為0(23)，空間復雜度為0(^2)。Floyd-Warshall的原理是動態規劃：設Di,j,k為從i到j的只以(1..k)集合中的節點為中間節點的最短路徑的長度。若最短路徑經過點k,則Di,j,k=Di,k,k-1+Dk,j,k-1；若最短路徑不經過點k,則Di,j,k=Di,j,k-1。因此，Di,j,k=min(Di,k,k-1+Dk,j,k-1,Di,j,k-1)。在實際算法中，為了節約空間，可以直接在原來空間上進行迭代，這樣空間可降至二維。Floyd-Warshall算法的描述如下：fork?1tondofori?1tondoforj?1tondoif(Di,k+Dk,j<Di,j)thenDi,j-Di,k+Dk,j;其中Di,j表示由點i到點j的代價，當Di,j為-表示兩點之間沒有任何連接。Dijkstra求單源、無負權的最短路。時效性較好，時間復雜度為O(V*V+E)。源點可達的話，O(V*lgV+E*lgV)=>O(E*lgV)。當是稀疏圖的情況時，此時E=V*V/lgV,所以算法的時間復雜度可為O(廠2)。若是斐波那契堆作優先隊列的話，算法時間復雜度，則為O(V*lgV+E)。Bellman-Ford求單源最短路，可以判斷有無負權回路(若有，則不存在最短路)，時效性較好，時間復雜度O(VE)。Bellman-Ford算法是求解單源最短路徑問題的一種算法。單源點的最短路徑問題是指：給定一個加權有向圖G和源點s,對于圖G中的任意一點v，求從s到v的最短路徑。與Dijkstra算法不同的是，在Bellman-Ford算法中，邊的權值可以為負數。設想從我們可以從圖中找到一個環路(即從v出發，經過若干個點之后又回到v)且這個環路中所有邊的權值之和為負。那么通過這個環路，環路中任意兩點的最短路徑就可以無窮小下去。如果不處理這個負環路，程序就會永遠運行下去。而Bellman-Ford算法具有分辨這種負環路的能力。A*(A-Star)算法是一種靜態路網中求解最短路最有效的直接搜索方法。注意是最有效的直接搜索算法。之后涌現了很多預處理算法(ALT,CH,HL等等)，在線查詢效率是A*算法的數千甚至上萬倍。公式表示為：f(n)=g(n)+h(n),其中f(n)是從初始點經由節點n到目標點的估價函數，g(n)是在狀態空間中從初始節點到n節點的實際代價，h(n)是從n到目標節點最佳路徑的估計代價。保證找到最短路徑(最優解的)條件，關鍵在于估價函數h(n)的選取：估價值h(n)<=n到目標節點的距離實際值，這種情況下，搜索的點數多，搜索范圍大，效率低。但能得到最優解。并且如果h(n)=d(n)，即距離估計h(n)等于最短距離，那么搜索將嚴格沿著最短路徑進行，此時的搜索效率是最高的。如果估價值>實際值，搜索的點數少，搜索范圍小，效率高，但不能保證得到最優解。算法是一種啟發式搜索算法，在路徑規劃中得到廣泛的應用，其中啟發函數的設計尤其重要。本文針對路徑規劃問題，對A*算法作了以下改進：一是在估價函數中考慮以距離和方向兩個要素，通過歸一化處理解決了單位不統一的問題；二是利用k-d樹空間索引結構，動態加載節點信息，減小內存使用空間。實驗結果表明，改進后的A*算法的搜索效率得到了明顯的提高。最經典的最短路徑搜索算法是Dijkstra算法，屬于遍歷搜索，它簡單易用并總能搜索到最短路徑。但是當網絡中節點數較多時,該算法搜索的結點數量會很大，效率非常低。因此有人提出了啟發式搜索算法，如：局部擇優搜索法、最好優先搜索法、A*算法等。啟發式搜索就是在狀態空間中，對每一個搜索的位置進行評估，得到最好的位置,從而在這個位置進行搜索直到搜索到目標為止。目前在路徑優化領域，最流行的啟發式搜索算法當屬由Har，tNilsson,Raphael等人首先提出的A*算法。它利用啟發函數來估計任意點到目標點的遠近程度，從而減少搜索空間，提高搜索效率。許多文獻都對A*算法進行了研究，并且都提出在估價函數中引入距離和方向兩個要素。但是距離和方向的單位是不統一的，所以在利用時會出現一些問題，本文針對這一問題進行了研究,并對估價函數進行了改進。另外,為了進一步提高算法的運行效率，本文在算法運行結構上，米用k-d樹空間索引結構，降低內存存儲空間。實驗結果證明了改進后算法的合理性和可行性。3?設計的過程與分析A*算法是建立在Dijkstra和BFS(最好優先搜索)算法基礎上的。它的整體框架采用遍歷搜索法，但是它采用了啟發函數來估計地圖上任意點到目標點的費用，從而可以很好地選擇搜索方向。A*算法引入了當前節點j的啟發函數f*(j),當前節點j的啟發函數定義為：f*(j)=g(j)+h*(j)(1)其中g(j)是從起點到當前節點j的實際費用的量度，h*(j)是從當前節點j到終點的最小費用的估計。注意到若h*j)=0,即沒有利用任何全局信息，這時A*算法就變成了普通的Dijkstra算法。因此普通的Dijkstra算法可看作A*算法的特殊情形。h*(j)要滿足相容性條件：即不能高于節點j到終點的實際最小費用。可以證明，如果估價函數滿足相容性條件，且原問題存在最優解，則A*算法一定能夠求出最優路徑°A*算法的優點在于利用啟發函數，使搜索方向更加智能的趨向于終點，所以其搜索深度較小，搜索的節點數少，故占用存儲空間少，如圖1所示。圖1A*算法與Dijkstra算法搜索區域對比A*算法的估價函數A*算法的關鍵在于設計一個合適的啟發函數。有文獻對其特點進行了分析，認為啟發函數f*(j)值是非遞減的，只要能夠滿足相容性條件即估價函數h*(j)小于節點j到目標點的實際費用，它生成的路徑一定是最優的。許多文獻都在估價函數的構造中引入了距離和方向兩個要素，即：h*(j)=w1*L+w2*如圖2所示。其中L表示當前節點到終點的歐氏距離，表示起點到當前節點的線段與當前節點到終點的線段的夾角即SjE，有文獻也用到了中間節點與關聯節點的線段和關聯節點與終點的線段夾角NjE°w1和w2分別是距離和角度的加權值,w1和w2的取值范圍分別為055-0.65和0.35-0.45。但距離和角度的單位不統一的問題不能忽略,即使角度的單位為弧度、距離的單位為千米，它們之間也很有可能出現距離值遠大于角度值(即L)的情況,特別是在大區域路徑規劃過程中，問題更明顯。而當L時，方向不再有約束力,而使得估價函數失去意義。A*算法的運行結構當構造合適的估價函數后就要考慮算法的運行，目前大多數方法是將全部數據讀入到內存當中，然后搜索最短路徑。從理論上講，A*算法可以通過搜索更少的節點完成最短路徑的搜索。但是算法運行時，必須要考慮兩個問題：一是數據讀取的速度。即使可以很快地將數據讀入到內存中，我們也還要考慮第二個問題，即系統內存的大小。如果系統內存足夠大，在算法運行過程中，也將會出現對同一節點進行重復的搜索，從而降低算法的運行效率。針對數據的讀取問題，有學者提出了基于限制區域的A*算法，減小數據的加載量。但是由于A*算法本身就是一種有損算法，這種方法很有可能搜索不到最短路徑，特別是在考慮道路屬性信息和交通限制信息時。圖2估價函數構造示意圖改進的A*算法A*算法估價函數的改進針對A*算法估價函數所出現的問題，我們將距離和角度進行歸一化處理,即首先計算當前節點所有關聯節點相應的距離和角度值，然后求它們的平均值即L,從而使得估價函數變為：h*j)=w1*L+w2*(5)其中：L=L/L(6)=/(7)歸一化處理以后，只考慮距離和角度對路徑的貢獻,而不必考慮距離和角度的數值大小。從而避免了距離和角度單位不統一的問題。雖然算法的運行要增加計算量,但是我們可以通過進一步減小算法的搜索空間，改善算法的運行結構來提高算法的搜索效率。針對算法運行效率的問題，建立k-d樹空間索引結構，動態加載路網數據，從而提高算法效率不失為一個好方法。k-d樹索引結構是k(k>1)的二叉檢索樹，主要用于索引多屬性的數據或多維點數據，它可以通過坐標快速的訪問區域中的路網數據。在算法執行過程中，并非開始就裝載所有的路網數據，而是根據算法的需要，讀取節點的相關信息，或刪除節點信息，雖然會增加運算過程中的I/O運算，但是這樣可以避免無效數據的大量裝載，占用大量的內存空間。例如,首先判斷當前節點是否在確定的范圍內，如果不在則裝載相應區域的數據，如果在確定的范圍內，則讀取數據的相關信息，并進行節點擴展。然后，在此基礎上計算路段的啟發值，搜索最短路徑。A*算法的實現在算法的實現過程中，要構造兩個鏈表。分別存儲待擴展的節點和已擴展的節點，分別稱為Open表和Close表。算法步驟如下：初始化設置。將起點信息加載到Open表中，Close表賦值為空。令g(j)=0。搜索距離當前節點最近的節點，即求f*(j)的最小值,將節點j從Open表中刪除并加載到Close表中。判斷節點j是否為終點，如果是,終點轉向步驟4;否則轉向步驟3。判斷節點j的節點信息是否在確定的范圍內，如果在范圍內，則擴展節點j；否則加載節點j的節點信息并進行擴展。轉向步驟2。從節點j開始，利用回溯的方法輸出起始節點到目標節點的最優路徑，以及最短距離，算法終止。在算法的運行過程中,避免了對同一節點的重復訪問，極大地縮小了搜索空間，從而縮短了算法的運行時間。對改進后的A*算法進行了實驗，在估價函數歸一化處理前后的最短路徑搜索結果如圖3(a),(b)所示。圖3a改進前的搜索路徑

圖3b改進后的搜索路徑實驗采用鄭州市地圖，節點2606個，路段4127條，在corei5,8GB內存的PC機上運行。與其他算法的實驗結果進行了對比結果見表1。表中：T表示臨時標記節點個數,N表示永久標記節點的個數，D表示規劃路徑長度。表1算法比較kT實驗編號L算法1算法改進的'算法tnt|lr11itlvptwlHV11nfvptfrdvptrurnjfwFri?yfzvruntwftvupnfvxxpIwi“Pty”hin|fyIIbwyrwmyipvmby?rbv1WyIwr1ruwrn|i'yvinWilltl|'wrnprinvvMlIlbtIFfywblhiiiyrw圖4臨時標記節點個數比較

100wRfl70605040100wRfl706050403020-*■■圖5永久標記節點個數比較將表1數據中的臨時標記節點,永久標記節點比較關系用圖4、圖5表示。通過實驗由圖4可以看出，歸一化處理后的A*算法的搜索區域明顯減小，由表1可以看出A*算法的搜索效率要比Dijkstra算法的搜索效率高。由圖4、圖5可知，改進后的A*算法的搜索效率明顯要高,在利用k-d樹建立空間索引結構以后,使得搜索的點數明顯減少，特別是在區域比較大時，改進后的A*算法的效率提高得更加明顯。需要指出的是,由于A*算法本身就是有損算法,所以其尋找到的路徑長度一般要比Dijkstra算法的規劃結果要長,但由于所選的道路更加合理，所以改進后算法的搜索結果更加實用。4?設計體會通過這次的課程設計，利用A*算法求解最短路徑，加深了對A*算法的了解與認識。課程設計環節中把教材里面的理論知識與實踐聯系起來，利用理論知識指導實踐仿真，取得很多的收獲。學習這個算法開始的時候會覺得比較難，花了一天的時間看資料理解算法的原理。在知道原理后的第二天開始編寫代碼，同樣也花了一天時間。最后是程序的顯示的優化。總之通過學習這個算法編寫程序，可以慢慢的從參考別人的代碼轉變自己知道原理后編寫代碼這個過程會比較慢需要不斷的聯系。A*算法作為一種啟發式搜索算法在路徑規劃中得到了非常廣泛的應用。利用啟發函數減小搜索空間，從而提高搜索效率，因此啟發函數在A*算法中起著關鍵的作用。針對A*算法啟發函數中距離和角度兩個要素單課程設計說明書課程設計說明書NO.#沈陽大學沈陽大學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();}});}}在算法的實現過程中，要構造兩個鏈表。分別存儲待擴展的節點和已擴展的節點，分別稱為Open表和Close表。算法步驟如下：1)初始化設置。將起點信息加載到Open表中，Close表賦值為空。令g(j)=0。2)搜索距離當前節點最近的節點，即求f*(j)的最小值，將節點j從Open表中刪除并加載到Close表中。判斷節點j是否為終點，如果是，終點轉向步驟4;否則轉向步驟3。3)判斷節點j的節點信息是否在確定的范圍內，如果在范圍內，則擴展節點j；否則加載節點j的節點信息并進行擴展。轉向步驟2。4)從節點j開始，利用回溯的方法輸出起始節點到目標節點的最優路徑，以及最短距離，算法終止。在算法的運行過程中，避免了對同一節點的重復訪問，極大地縮小了搜索空間，從而縮短了算法的運行時間。2.2A*算法的實現在算法的實現過程中，要構造兩個鏈表。分別存儲待擴展的節點和已擴展的節點，分別稱為Open表和Close表。算法步驟如下：1)初始化設置。將起點信息加載到Open表中，Close表賦值為空。令g(j)=0。2)搜索距離當前節點最近的節點，即求f*(j)的最小值，將節點j從Open表中刪除并加載到Close表中。判斷節點j是否為終點，如果是，終點轉向步驟4;否則轉向步驟3。3)判斷節點j的節點信息是否在確定的范圍內，如果在范圍內，則擴展節點j；否則加載節點j的節點信息并進行擴展。轉向步驟2。4)從節點j開始，利用回溯的方法輸出起始節點到目標節點的最優路徑，以及最短距離，算法終止。在算法的運行過程中，避免了對同一節點的重復訪問，極大地縮小了搜索空間，從而縮短了算法的運