1、學號：1620868上海建橋學院本科生畢業設計（論文）基于A*算法的路徑尋找學 院：商學院專 業：國際經濟與貿易班 級：B16-2姓 名：阮晨陽指導老師：史小宏完成日期：2016年11月基于A*算法的路徑尋找基于A*算法的路徑尋找摘 要啟發式搜索算法的有很多種類，其中一種就是A*搜索算法。在狀態空間對每一個可能的位置進行判斷，并且根據一定的判斷標準得出最優化的位置，然后以這個位置作為開始繼續搜索到終點目標位置，以上就是啟發式搜素的基本的定義。對于每次都要選取最小估價的節點，應該用到最小優先級隊列（也叫最小二叉堆）。可以直接使用。當然不要忘了重載自定義節點的比較操作符。A*算法的特點：A*算法在

2、理論上是時間最優的，但是也有缺點：在理論上最差的情況下，它的空間增長將有可能是指數級別的。這一搜索算法的的好處就是可以將很多的不需要的冗余的路徑略去，從而使得時間和空間的效率大大提升。它的主要的組成部分為OpenList,CloseList和估價函數。他可以應用在路由的路徑查找，地圖上路徑查找。關鍵詞：啟發式算法，搜索路徑，A*算法，估價函數- IV -Based on the path of the A * algorithm to findAbstractHeuristic search algorithm, there are many types, one of which is A

3、* search algorithm. The judge in the state space of every possible location, and obtained optimal location according to certain criteria, and then to continue searching to the end of this location as the target location, the above is the basic definition of heuristic search. For each node must selec

4、t a minimum valuation, should be used in a minimum priority queue (also known as the least binary heap). Can be used directly. Of course do not forget the overloaded self-defined node operation character.A * algorithm characteristics: A * algorithm is theoretically optimal time, but it also has disa

5、dvantages: in theory the worst case, the growth of its space will be possible to the index level. The benefits of the search algorithm can be a lot of unwanted redundant path omitted, making time and space efficiency is greatly enhanced. Its main components OpenList, CloseList and valuation function

6、s.He can be applied to the routing path search path to locate on the map.Key words:Heuristic algorithm, the search path, the A * algorithm, the valuation function目 錄引 言11 研究背景和意義21.1 背景及意義21.2 本文研究內容32 路徑尋址和開發工具42.1 路徑尋址的方法介紹42.1.1 模擬42.1.2 最短路徑問題42.1.3 Dijkstra算法42.2 開發工具Eclipse53 基于搜索算法的機器人路徑尋址73.

7、1 廣度優先算法（BFS）73.2 深度優先搜尋（DFS）73.3 A*算法74 A*算法仿真系統設計114.1路徑尋址系統概述114.2 對用戶界面進行模塊設計114.2.1 主窗口界面114.2.2 繪畫過程代碼114.2.3 工具欄代碼124.2.4 按鈕代碼134.2.5 狀態欄代碼144.3 對算法實現進行設計144.3.1 路徑組成函數和搜索邏輯設計144.3.2 節點判斷函數及屬性函數的設計165 仿真實驗結果的比較及界面UI185.1 SWING技術介紹185.2 仿真實驗及結果比較185.2.1 g(n)的改變對結果的變化185.2.2 基于h(n)的變化對結果的影響246

8、結束語306.1 總結306.2 實驗存在的問題和改善30參 考 文 獻31發表學術論文情況32致 謝33引 言現實世界中有許許多多的不同的網絡構成，交通網絡，通信網絡，計算機網絡，貿易網絡等等。網絡中有一個十分重要的部分就是尋找各個節點之間的路徑，路徑的存在是非常多的，而最有的路徑一直是人們所期望的。因此涌現了許許多多的不同的搜索算法，但是不同的算法之間有著十分顯著的差別，我們需要根據不同的情況來使用不同的策略。算法有兩個十分重要的特性就是空間和時間連個度量，他們對程序的運行產生了十分巨大的影響。在不斷的研究中，更加優秀和智能的搜索算法也在不斷出現。1 研究背景和意義1.1 背景及意義搜索算

9、法他們大致上可以被分成兩個大的類型，即深度優先搜索（DFS）和廣度優先搜索（BFS）。深度優先搜索所遵循的搜索策略是盡可能“深”地搜索樹。它的基本思想是：為了求得問題的解，先選擇某一種可能情況向前（子結點）探索，在探索過程中，一旦發現原來的選擇不符合要求，就回溯至父親結點重新選擇另一結點，繼續向前探索，如此反復進行，直至求得最優解。深度優先搜索的實現方式可以采用遞歸或者棧來實現。而廣度優先算法則是盡可能的先尋找與節點相同的同一層的節點。類似樹的按層遍歷，其過程為：首先訪問初始點Vi，并將其標記為已訪問過，接著訪問Vi的所有未被訪問過可到達的鄰接點Vi1、Vi2Vit，并均標記為已訪問過，然后再

10、按照Vi1、Vi2Vit的次序，訪問每一個頂點的所有未被訪問過的鄰接點，并均標記為已訪問過，依此類推，直到圖中所有和初始點Vi有路徑相通的頂點都被訪問過為止。廣度和深度優先搜索有一個很大的缺陷就是他們都是在一個給定的狀態空間中窮舉。這在狀態空間不大的情況下是很合適的算法，可是當狀態空間十分大，且不預測的情況下就不可取了。他的效率太低，在這里就要用到啟發式搜索了。啟發式搜索其實有很多的算法，比如：局部擇優搜索法、最好優先搜索法等等。這些算法都無一例外的將啟發式的函數應用在這些算法中，優化了他的搜索的過程得出一個相對比較好的結果，可是在應用到具體的搜索過程中選取每一個最佳的節點的方法和策略是不盡相

11、同的。比如局部的優化搜索算法，他的目的就是在他的搜索的過程中間得到有優化的節點然后將其他備選的可能的節點刪去，這些節點通常是他的兄弟節點（即在同一層的節點）以及父節點。但是上述的過程中也有個問題就是這一搜索的過程可能被局限在一個小的局部能然后不停的循環使得在這個循環外的可能的更優化的節點無法進入到搜索的過程中來，最后往往導致一個局部的最優解而忽視了全局可能的優化解。而最好優先伐則靈活的多了，在他的搜索的過程中，他不會刪除一個節點他會保留它除了這個節點沒有了子節點成為了一個死的節點，他在比較的過程中引入了以前計算過的節點的不同估價值然后和當前的值進行了比較通過這一比較的過程得到了一優化的解。這樣

12、就會有效地避免了局部的最優化的解產生，可以將全局的可能的優化的解都考慮進來。最好優先算法一個代表就是A*算法，但是它比起普通的最好優先算法，又有著些許的不同，他在搜索的過程中添加了一個約束性質的條件。在面對一些實際的問題中是，人們總是會要求找出狀態空間內可以搜索到的最好的路徑。也就是說他們希望可以用最少的時間和空間的代價得出最優化的解，而A*就是為了這些情況的出現而準備的。1.2 本文研究內容這次我們主要實現的是A*算法，他是啟發式搜索算法的一種。使用它的估價函數產生不同節點的估價值對不同的路徑進行評估，最后得出一個最好的路徑。通過對于A*算法的應用，使得他可以在隨意的設置的障礙物之間找到最好

13、的路徑，從起點到達終點。由于障礙物時隨意擺放的因此，可以顯示他的智能化，而不是僵化的產生的一個最優化的路徑，這在許多方面有個重要的應用，比如游戲和導航中，這些都需要智能化尋址。而不是僵化的指導方式。2 路徑尋址和開發工具2.1 路徑尋址的方法介紹2.1.1 模擬為了模擬現實中的情況，我們借用物理中的質點的概念，將物體縮小為一個方格（類似一個點），他的路徑的搜索則是在一個由方格組成的途中繞開他的障礙物到達終點。2.1.2 最短路徑問題最短路徑問題是圖論研究中的一個經典算法問題，他的目的就是最后產生起點到終點之間最短的路徑。涉及到他的算法具體的邏輯的過程主要有下面幾種：1已知了起點的求出最優化路徑

14、問題。這一問題比較適合使用Dijkstra算法。2已知了終點未知的的最短路徑問題，與上一個問題恰恰相反這是已知了終點的情況下得出最優化路徑的問題。 這涉及到圖論中無向圖的原理，在這一理論中上述兩個問題是等價，而在有向圖的理論中前一個問題就是講將已知的路徑反向從而確定出起點的問題。3已知了起點終點的最優化路徑問題這是為了找出這兩個結點之間的各種路徑選擇的最好的解。這又被稱為全局最短路徑問題，他適合使用Floyd-Warshall算法。我們這次的模擬中是已知起始點，因此使用類似于Dijkstra算法比較相似的A*算法。2.1.3 Dijkstra算法戴克斯特拉算法（即是Dijkstra's

15、 algorithm）是由荷蘭計算機科學家艾茲赫爾·戴克斯特拉發明的。他的目的是為了解決郵箱途中某一個節點到其他的節點的有優化的路徑的問題。比如說在一張有向圖中一個節點表示一個超市，而有向圖各邊的權重則表示了每個路徑的距離大小，這一個算法就是為了找出節點間即超時間最短的距離的大小。在算法的開始初始化一個每條邊都有權重的有向圖G，和G中的起點節點A。在這里我們將S 表示為一個集合，它包含了G中所有節點的集合。有向圖中的一條邊，我們可以將它表示成由兩個節點組成的有序的元素對。（a,b） 表示從某一個節點a到b是相通的他們之間存在一條邊e。然后我們將E表示為所有邊的集合，而每天存在的邊權重

16、書將由權重函數W:E（e>0）定義。那么我們就可以將W(a, b) 就是從頂點a到頂點b的消耗值，且他恒為正值。而每條邊的消耗值就可以被理解成兩個節點的距離的值。那么同理推得任意的兩個節點間的路徑的消耗值，就是連接這兩個節點的路徑的總的距離值的和。已知有S中有頂點m和n，而Dijkstra算法已算出這兩節點m和n的最好的路徑，通常就是最短的路徑。同時這個算法也可以在有向圖G中，通過點m找到他到其他相通的點的最短的路徑值。Dijkstra算法的工作原理就是通過為每個存在的點n記錄他可以找到的m到點n最短的路徑，然后將這些路徑相互之間進行比較。在初始化的時候，起點m的權重值設置為0，他的數學

17、表達是dm=0,要是存在一條邊連接了m,n兩個節點，那么dm就等價與w（m,n）,然后我們將其他存在的節點（包括了節點m無法直接到達的）的權重值設為了無窮，這就表示了目前我們并不知道節點m到這些節點的路徑的存在和大小。（用數學表達就是說S中所有節點s除m和n 外 ds = ）。那就是說當我們結束了算法后，ds 中記錄的應該是從m到n的最優的路徑，一個特殊的情況是記錄的值是無窮那么就表示就是這條路徑并不存在。Dijkstra算法的搜索方式就是從一條邊探索到另一條邊上：比如，p與點n可以相通那么邊（p,n）可以加到邊（m,n）后面，那么這條路勁的長度就從w（m,n）變成了dp+w(m,n)。然后將

18、這條邊和已經記錄的 dv1比較，如果dv的值相對要小，那么就可以用新值來替代當前 dv1 中的值，這就是最基本查找路徑的方式。這一不斷搜索的過程一直循環到記錄的dv是可以找到的最短的路徑。Dijkstra算法算法通過不斷比較和替換dv的值，在他達到最優化的值時，每一天存在的邊都只會被比較一次。這一算法保留兩個節點的集合P,Q。集合P的作用就是記錄了已知的所有可能的邊通過相互的邊最終產生的最短路徑的值dv他所代表的節點（因為在運算結束以前可能存在不同解），而集合 Q 將會記錄剩下不在集合P中的節點。集合P初始狀態應該是空集，在以后算法不停搜索的過程中每一次搜索的都有一個節點從 Q 被移動到P中。

19、而這個被選中的節點是 Q 中擁有最小的 du 值的頂點。當某一個節點s 從 Q 中轉移到了P中，就相當于算法對每條可能的存在的相連的邊 (u, v) 進行搜索。這點類似于對一顆樹不停向下級子節點進行搜索，并將值記錄在dv中。如果有已知信息可用來估計某一點到目標點的距離，則可改用A*搜尋算法，以減小最短路徑的搜索范圍。與最短路徑問題相關最有名的一個問題是旅行商問題（Traveling salesman problem），此類問題要求找出恰好通過所有目標點一次且最終回到原點的最短路徑。然而該問題為NP-完全的，因此旅行商問題不太可能具有多項式時間解法。由于本人能力有限，所以不探索TSP問題，希望以

20、后有時間繼續研究。2.2 開發工具EclipseEclipse是著名的跨平臺的自由集成開發環境（IDE）。Eclipse的基礎是富客戶機平臺（Rich Client Platform，即RCP）。RCP包括下列組件：核心平臺（啟動Eclipse，運行插件）OSGi（標準集束框架）SWT（可移植構件工具包）JFace（文件緩沖，文本處理，文本編輯器）Eclipse工作臺（即Workbench，包含視圖（views）、編輯器（editors）、視角（perspectives）、和向導（wizards）Eclipse采用的技術是IBM公司開發的（SWT），這是一種基于Java的窗口組件，類似Java

21、本身提供的AWT和Swing窗口組件；不過IBM聲稱SWT比其他Java窗口組件更有效率。Eclipse的用戶界面還使用了GUI中間層JFace，從而簡化了基于SWT的應用程序的構建。Eclipse的插件機制是輕型軟件組件化架構。在富客戶機平臺上，Eclipse使用插件來提供所有的附加功能，例如支持Java以外的其他語言。已有的分離的插件已經能夠支持C/C+（CDT）、PHP、Perl、Ruby，Python、telnet和數據庫開發。插件架構能夠支持將任意的擴展加入到現有環境中，例如配置管理，而決不僅僅限于支持各種編程語言。Eclipse的設計思想是：一切皆插件。Eclipse核心很小，其它

22、所有功能都以插件的形式附加于Eclipse核心之上。Eclipse基本內核包括：圖形API（SWT/Jface），Java開發環境插件（JDT），插件開發環境（PDE）等。3 基于搜索算法的機器人路徑尋址搜索算法分為了廣度優先算法(BFS) 和深度優先搜尋(DFS)這主要的兩種，首先介紹些這兩種算法的原理和優缺點。為了方便描述這一搜索的過程我將所有可能的點都認為一個樹上的各個的節點。而起始點則是整棵樹的父節點，終點則是樹的某一個子節點，而尋求最短的路徑則是找到一條路徑具有最少的層數和權值，達到這個設定的子節點。3.1 廣度優先算法（BFS）BFS算法試圖找出一點與最初始的點最接近在一層內，但是

23、他不會連續兩次訪問同一個節點。他的最好的情況為o(bd)，最差的情況為o(bd)此處b-樹的廣度，d-樹的深度。這個算法的好處是他一定可以找出一個解，并且解出步數將會小于DFS的步數，因為對于樹來說，深度往往要比樹的廣度要打，但是這一算法將會大量的耗費內存，他會將他所有的可能的節點全部保存下來，因此他在算法效率上十分的笨重。BFS算法傾向于使用隊列作為他的數據處理方式。3.2 深度優先搜尋（DFS）DFS算法與BFS的區別就是他將會對每個節點子節點優先進行搜索，這將會對具有很大廣度的樹來說更加有效率，它最好的情況為o(b*d)最壞的情況為 o(bd)。此處b-樹的廣度，d-樹的深度。DFS對于

24、某些特殊的情況更加使用，因此它的使用范圍相對BFS小點，但是它的優勢就是BFS就會使用bd個空間用于存儲節點，而DFS不會，它將大大節省空間。DFS更加傾向于使用堆債作為他的數據的處理方式。3.3 A*算法以上兩種算法BFS肯定能找出答案，但是他會耗費大量的資源，DFS雖然效率更好但是他只是用某些特殊的情況，而且他有可能會在一個局部內死循環，從而得出一個局部的最優解，而不是全局的最優解。這里引入A*算法，A*算法更加的智能它引入了一個估價函數的機制，從而避免了局部最優解的局面。*的意思是他比起普通的算法更加的優化。對于A算法來說，他不會比較估價函數的值，而A*算法則會比較他們之間的值，從而得出

25、最好接，這就會將局部以外的可能更優的節點加入到搜索的過程中。這個函數式為f*(n)=g*(n)+h*(n)，最重要的是找出h*(n)的值如果無法計算出一個好的值，那么他的效率將會和上面說到算法一樣低下，因此它最好的情況是O(b*d)最差的情況是O(bd)。此處g*(n)不是重點的原因是因為在其他的位置可能存在更好的解，這就會防止局部最優解的產生。A*搜尋算法，他可以應用在具有多個不同節點的路徑的圖上，同時求出一個最短路徑的算法。它的最常見的應用是在游戲中NPC的移動方面，或者是在網絡游戲中BOT的移動計算方面。上文中提到該算法像與Dijkstra算法的原理基本一致，目的是為找出一條最短的路徑；

26、同時他也像BFS一樣，進行啟發式的搜索。在這個算法中引入了一個叫做估價值的概念，它的大致的原理如下：g(n)表示從起點到任意節點n的路徑的距離長度，h(n)表示圖中任意一個存在的節點n到目標節點的股價值的大小。 因此，A*算法的關于估價值的公式可以表示為下式：f(n)=g(n)+h(n)。 這個公式具有以下幾個特殊的地方：如果h(n)為0，那么f(n)=g(n)，這種情況出現在求出起點到任意節點n的最短路徑，這種情況下問題就類似于單源最短路徑的問題，此時就可以應用Dijkstra算法。如果h(n)<=“n到目標的實際距離”， 那么不停比較這些值就可以最終產生出最優解。不過當h(n)的值越

27、來越小的時候，他所涉及到的需要計算的節點數目將會越多，此時的算法效率將會低下。比如當應用到幾何型的網絡中時，可以取兩節點間直線距離（即是歐幾理德距離）做為節點的估價值，即f=g(n)+sqrt(dx-nx)*(dx-nx)+(dy-ny)*(dy-ny)；這樣的話受到估價值h的影響個，在g值一定的情況下估價函數f會受到h的約束，f的值越小就意味著h的值也小，同時表示這個節點距離目標點就越近，這樣話就是表示搜索到的每一個點就會產生一條最短路徑。而這點明顯和Dijstra算法在點四周漫無目的的以枚舉的方式進行尋找就好很多，因為他對每個點進行了預判剔除了不必要的點，極大地提高了效率。這里需要提到h（

28、n）的一個屬性他被稱為信息性，他的意思是在估算一個節點的估價值的時候的約束條件，當一個節點的約束條件越多或者說他的信息性越多的話，他被剔除的可能性就越大，這樣大量不需要計算的節點就會被排除，所以我們就可以說這個估價函數很好或者是這個算法更加優秀。這個特性使得它比廣度優先算法優秀很多，因為他的h(n)為0，換句話就是它不具有信息性即啟發性信息。但是在路徑搜索的過程中，他往往要求了很高的實時性，h(n)的信息性越強，他的要求的計算量就會相對上升，使得他耗費的時間也就會越大。此時為了滿足他的實時性，我們必須在一定程度上減少的h(n)的信息性，即減少節點的約束性的條件。但是他付出的代價就是準確性會降低

29、，這就是一個我們需要權衡的問題。簡化的A*算法流程：搜索區域被劃分成了方形網格。簡化搜索區域，是尋路的第一步。這一方法把搜索區域簡化成了一個二維數組。數組的每一個元素是網格的一個方塊，方塊被標記為可通過的和不可通過的。路徑被描述為從A到B我們經過的方塊的集合。一旦路徑被找到，我們的人就從一個方格的中心走向另一個，直到到達目的地。1.從起點開始，他會將其周圍待處理的節點放入一個列表中。一開始只有一個，即是起點，但是之后就會多起來。表格內包含待檢查的方格。2.尋找起點周圍可到達的一切可通過的方格，放棄不可通過的方格。把這些可行的方格加入到列表中。為這些方格保存點A為這些方格的父方格。父方格很重要類

30、，類似于樹中的父節點。3.從列表中刪除點A，將其加入另一個表（稱為關閉列表），這個列表中保存所有不需要再次檢查的方格。接著重復以上步驟，找出每個可行的方格的表和關閉列表。類似于一棵樹，尋找他的最小的路徑。選擇路徑中經過哪個方格的關鍵是下面這個等式：F=G+H*G=從起點A，沿著產生的路徑，移動到網格上指定方格的移動耗費。*H=從網格上那個方格移動到終點B的預估移動耗費。這經常被稱為啟發式的，H的值將會是不定的。此為最簡單的方式。既然我們在計算沿特定路徑通往某個方格的G值，求值的方法就是取它父節點的G值，然后依照它相對父節點是對角線方向或者直角方向(非對角線)，分別增加和。例子中這個方法的需求會

31、變得更多，因為我們從起點方格以外獲取了不止一個方格。H值可以用不同的方法估算。我們這里使用的方法被稱為曼哈頓方法，它計算從當前格到目的格之間水平和垂直的方格的數量總和，忽略對角線方向，然后把結果乘以10。這被稱為曼哈頓方法是因為它看起來像計算城市中從一個地方到另外一個地方的街區數，在那里你不能沿對角線方向穿過街區。很重要的一點，我們忽略了一切障礙物。這是對剩余距離的一個估算，而非實際值，這也是這一方法被稱為啟發式的原因。想知道更多？你可以在這里找到方程和額外的注解。F的值是G和H的和。第一步搜索的結果可以在下面的圖表中看到。F,G和H的評分被寫在每個方格里。正如在緊挨起始格右側的方格所表示的，

32、F被打印在左上角，G在左下角，H則在右下角。為了繼續搜索，我們簡單的從開啟列表中選擇F值最低的方格。然后，對選中的方格做如下處理：4，把它從開啟列表中刪除，然后添加到關閉列表中。5，檢查所有相鄰格子。跳過那些已經在關閉列表中的或者不可通過的(有墻，水的地形，或者其他無法通過的地形)，把他們添加進開啟列表，如果他們還不在里面的話。把選中的方格作為新的方格的父節點。6，如果某個相鄰格已經在開啟列表里了，檢查現在的這條路徑是否更好。換句話說，檢查如果我們用新的路徑到達它的話，G值是否會更低一些。如果不是，那就什么都不做。以上就是A*算法的主要的過程，但是無法體現估價函數重要的價值。為了更加明了的解釋

33、這格的重要性，我將用華容道作為例子來解釋他的重要性。有一個3*3的方格81345276他最終的目的是變成12384765他將會使用兩種不動估價函數，在附錄中將會有這兩種情況的圖片使用了兩種不同的估價函數f(n)good 和f(n)weak 都最終得到了結果但是f(n)good的估價函數效率更加高。我們通過更加深入的觀察這些過程可以了解到為何f(n)weak 用了更多的步數才得到了結果，從一開始，搜索的步驟直接導向了有最終結果的那個分支。但是在f(n)weak 達到這個路徑之前他多使用了4步才搜索到了這個具有最終解的分支。并且f(n)good 三個子節點的估價值遠遠高于f(n)weak的估價值是

34、的結果更加具有了區分度，更加容易得出具有答案的分支。再設計f(n)函數的時候，h(n)必須謹慎的設計，如果隨意設置就會導致算法效率及其的低下。h(n)的值可以根據不同的應用的場景特殊設計。4 A*算法仿真系統設計4.1路徑尋址系統概述建立一個可以自由畫障礙物的程序，在起點到終點的過程中可以繞過障礙物。尋找一個最優的路徑。并且可以保存及加載路徑，一邊可以用相互之間的比較。4.2 對用戶界面進行模塊設計4.2.1 主窗口界面使用JAVA的SWING技術搭建一個UI界面主要的程序入口為AStarDemo文件，他會負責加載各個窗體的組建AstarPanelastarPanel = newAstarPa

35、nel(15,15,60,40);StatusPanelstatusPanel = newStatusPanel();astarPanel.setStatusPanel(statusPanel);frame.setJMenuBar(newAStarMenuBar(astarPanel);frame.getContentPane().add(new ControlPanel(astarPanel), BorderLayout.NORTH);frame.setVisible(true);frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);以上代

36、碼將astarPanel，statusPanel，AStarMenuBar，ControlPanel等相關的組建加入到UI中。4.2.2 繪畫過程代碼astarPanel作用是最主要他負責在界面上畫出障礙物和畫出計算出的路徑，使得A*算法畫出他算出的路徑。并且可以顯示出每個節點的相應的坐標。g2d.fillRoundRect(x, y , width, height, arc, arc);g2d.setComposite(TIPS_COMPOSITE2);g2d.setColor(TIPS_FG);g2d.drawString("Current grid num : ("

37、+ tipsPoint.getLocation().x + ", "+ tipsPoint.getLocation().y + ")", x + 15, y + 15);g2d.dispose();其上為顯示坐標的代碼在4.2.1中第一句畫設置了一個60*40的表格而每個節點的大小為15pix*15pix的背景。publicvoidpaintComponent(Graphics g) super.paintComponent(g);fillBarrier(g);fillTargetAndSourceGrid(g);fillOpenList(g);fill

38、AStarPath(g);fillDrawData(g);drawGridLine(g);drawTips(g);以上代碼的繪畫邏輯是：圖4.1 繪畫代碼邏輯4.2.3 工具欄代碼AStarMenuBar的作用是顯示菜單欄，它的基本顯示的代碼：enumMainMenuFile("File", 'F'),View("View", 'V'),Help("Help", 'H');publicSubMenu getSubMenus() if(subMenus=null)List<SubMe

39、nu>tmp = newLinkedList<SubMenu>();for(SubMenusubMenu : SubMenu.values()if(subMenu.getFatherMenu()=this)tmp.add(subMenu);subMenus = newSubMenutmp.size();subMenus = tmp.toArray(subMenus);returnsubMenus;他有三個主菜單組成使用，getSubMenus()方法得到下層的菜單。ControlPanel的作用是實現界面上的三個按鈕通過調用不同的函數實現功能，三個函數是:startFind(

40、)這是算法開始的入口，是最重要的函數他將調用他的一個find()方法實現他的路徑搜索。clearPath()清理路徑clearMap()清理障礙物，起原理同上個函數4.2.4 按鈕代碼存在三個按鈕JButtonstartButton = new JButton("Start");JButtonclearButton = new JButton("ClearPath");JButtondrawButton = new JButton("ClearMap");這三個按鈕分別觸發三個函數實現各自的功能publicvoidclearPath(

41、) currentDrawIndex = 0;astarMap.clearOpenList();此步將路徑清除的同時將數據清理，避免對下次計算產生影響publicvoidclearMap() for (int i = 0; i <drawData.length; i+) for (int j = 0; j <drawDatai.length; j+) drawDataij = -1;rebuildAstarMap();此步將節點的繪圖信息清空，然后重新畫出新的圖（即是空的圖）4.2.5 狀態欄代碼狀態欄的目的是為了顯式的表示算法的效率，對實驗的總結很有必要。這里計算的算法結束的當前

42、的時間減去開始記錄下的時間updateCostTimeMillis(System.currentTimeMillis() - start);4.3 對算法實現進行設計4.3.1 路徑組成函數和搜索邏輯設計以下則是最重要的部分對于算法的實現，上面已經提及到find（）方法將會最終完成這個程序最重要的功能，尋找路徑。public List<AStarNode> find() init();AStarNode current = null;while(!isEnd() && !isFind()current = getMinFNodeFromOpenList();if(i

43、sAchieve(current)buildPath(current);isFind = true;elseadd2CloseMap(current);for(AStarNode neighbor : getNeighbor(current)if(neighbor=null | isInCloseMap(neighbor)| isCanNotGo(current, neighbor)continue;booleanisBetter = true;AStarNodenodeFromOpenList = getNodeFromOpenList(neighbor);if(nodeFromOpenLi

44、st!=null)inttg = neighbor.distinctG(current);isBetter = tg>neighbor.getG() ? false : true;elseadd2OpenList(neighbor);if(isBetter)neighbor.reCalculatorGAndH(current, target);return path;上述算法一開始將圖初始化，并且判定時候已經找到路徑或者已經到達了終點，如果不是則開始尋找，尋找最初，將判斷，這個節點是否有相鄰的節點，相鄰的節點時候已經搜索到，相鄰節點是否在已有路徑中。if( (offsetX=1 &

45、;&offsetY=-1 && (isValidX(from.getX()-1) &&STATE_BARRIER=astarDatafrom.getY()from.getX()-1 | isValidY(from.getY()+1) &&STATE_BARRIER=astarDatafrom.getY()+1from.getX() |(offsetX=1 &&offsetY=1 && (isValidY(from.getY()-1) &&STATE_BARRIER=astarDatafrom

46、.getY()-1from.getX() | isValidX(from.getX()-1) &&STATE_BARRIER=astarDatafrom.getY()from.getX()-1) |(offsetX=-1 &&offsetY=1 && (isValidX(from.getX()+1) &&STATE_BARRIER=astarDatafrom.getY()from.getX()+1 | isValidY(from.getY()-1) &&STATE_BARRIER=astarDatafrom.get

47、Y()-1from.getX() |(offsetX=-1 &&offsetY=-1 && (isValidX(from.getX()+1) &&STATE_BARRIER=astarDatafrom.getY()from.getX()+1 | isValidY(from.getY()+1) &&STATE_BARRIER=astarDatafrom.getY()+1from.getX()上述的的代碼根據每一個節點相對于父節點的相對位置進行判斷，判斷是否可以通過這個節點。dopath.add(0, current);current

48、 = current.getFather();while(current!=null);這就是路徑的組成他將她裝載到一個動態數組中，使得以后在繪畫出路徑的時候可以直接點調用。并且這樣的設計也易于路徑的保存，方便了試驗相互之間的比較。int index = 0;floatminF = openList.get(index).getF();int length = openList.size();for(int i=1; i<length; i+)AStarNodeaStarNode = openList.get(i);if(minF>aStarNode.getF()minF = aS

49、tarNode.getF();index = i;這段代碼就是將得出來的估計值和已有的估價值相互比較，得出最好的結果。在上面的介紹中其實已經可以看出在這個算法中起到最重要的作用其實是節點及其周邊環境。因此，算法中單獨寫了關于節點進行判斷和算法運算的部分。4.3.2 節點判斷函數及屬性函數的設計AStarMap.java實現的路徑總體的策略（即以上的代碼）AStarNode.java則是實現路勁上每一個點的判斷和下一個節點選擇的事宜。在AStarNode.java中所使用的方法在3.1已經有了詳細的描述，下面則是實現的代碼：publicvoidinit(AStarNode target) thi

50、s.g = 0;this.h = heuristicCostEstimate(this, target);this.f = g+h;此函數的作用就是判斷這個子節點是否能稱為最優路徑的下一個節點的函數。其中h是個很重要的度量，他將用：return (Math.abs(source.x - target.x) + Math.abs(source.y - target.y)*G_0;對角的平方差來計算他的值，值越小就意味著他離他的父節點就越近。這里值一開始會給一個預定的值以方便運算publicintdistinctG(AStarNode father) intoffsetX = x-father.x

51、;intoffsety = y-father.y;int distinct = 0;if(offsetX=0 &&offsety=-1)distinct = G_1;elseif(offsetX=1 &&offsety=-1)distinct = G_2;elseif(offsetX=1 &&offsety=0)distinct = G_3; . . .privatefinalstaticintG_1= 10;privatefinalstaticintG_2= 14;privatefinalstaticintG_3= 10;privatefina

52、lstaticintG_4= 14;privatefinalstaticintG_5= 10;一個方塊各個角上的值都是最大的，邊上的值則比他小一點。從上述的帶那種可以看出G_N的值是根據他的位置來確定，他的位置設置的代碼為if(offsetX=0 &&offsety=-1)distinct = G_1;這個就相當于（0，-1）的坐標thrownewAStarPositionException("Unvalid relation between current node("+this+") and fater node("+father+&

53、quot;)");returndistinct+father.g;為了保證不會出現局部最優的情況，他將調用下一函數再次計算是否存在一個更好的節點：publicvoidreCalculatorGAndH(AStarNode father, AStarNode target) this.g = distinctG(father);this.h = heuristicCostEstimate(this, target);this.f = g+h;this.father = father;以上就是程序一個基本的算法的實現。5 仿真實驗結果的比較及界面UI圖5.1 初始軟件界面上面就是A*算法

54、 的具體的實現的界面，采用的是JAVA的swing的技術，運用JAVA自帶的UI組建搭建一個具體的界面。當點擊各個按鈕將會觸發各個函數。5.1 SWING技術介紹Swing 是一個為Java設計的GUI工具包。 Swing 是 JAVA基礎類 的一部分。 Swing 包括了圖形用戶界面 (GUI) 器件 如：文本框，按鈕，分隔窗格和表。SWING 提供許多比AWT更好的屏幕顯示元素。它們用純Java寫成，所以同Java本身一樣可以跨平臺運行，這一點不像AWT。 它們是JFC的一部分。 它們支持可更換的面板和主題（各種操作系統默認的特有主題），然而不是真的使用原生平臺提供的設備，而是僅僅在表面上

55、模仿它們。這意味著你可以在任意平臺上使用JAVA支持的任意面板。 輕量級元件的缺點則是執行速度較慢，優點就是可以在所有平臺上采用統一的行為。5.2 仿真實驗及結果比較5.2.1 g(n)的改變對結果的變化圖5.2 第一次運行的路徑圖這是任意畫出的障礙物，灰色顯示的就是路徑中的障礙物。而藍紅色的則是尋找出的路徑，可以看書它相對而言是一天最短的路徑。在他一開始的時候他明顯是以對角線的方式進行著搜索，這是因為在AStarNode。JAVA文件中，定義了每個點的估價值我開始講對角線上的估價值設為最高，/* * G8G1G2 * G7G3 * G6G5G4 */privatefinalstaticintG_1= 10;privatefinalstaticintG_2= 14;privatefinalstaticintG_3= 10;privatefinalstaticintG_4= 14;privatefinalstaticintG_5= 10;privatefinalstaticintG_6= 14;privatefinalstaticintG_7= 10;privatefin