A算法演示系統(tǒng)畢業(yè)設(shè)計

1、摘要本次課程設(shè)計的題目是“ A星算法的演示系統(tǒng)”，A*算法在人工智能中是一種典型的 啟發(fā)式搜索算法，這是一種在圖形平面上，有多個節(jié)點的路徑，求出最低通過成本的算法。 常用于游戲中的NPC勺移動計算，或在線游戲的BOT勺移動計算上。本次課程設(shè)計要求能 夠演示出整個算法的執(zhí)行過程，能夠進行單步演示，動態(tài)演示，把算法的執(zhí)行過程的精髓 演示出來。在對算法充分了解的基礎(chǔ)上，演示算法的執(zhí)行過程，就要涉及到圖像的繪制，而對于 圖像的編程，顯然高級語言有其開發(fā)效率高的特點，java強大的運算和圖形展示功能，使 圖像編程變得更加的簡單和直觀。本課題基于 eclipse的java集成開發(fā)環(huán)境，設(shè)計并實 現(xiàn)了 A星

2、算法的演示系統(tǒng)，展示 A星算法如何進行啟發(fā)式搜索和尋路的過程。實現(xiàn)了設(shè)置 起點、設(shè)置終點、設(shè)置障礙、清除障礙、直接尋路、單步尋路、動態(tài)尋路、重新尋路、添 加默認障礙這些功能的操作。使用者能夠通過自己的要求進行A星算法的演示和使用，本軟件充分展示A星算法的執(zhí)行過程。關(guān)鍵字：A*算法，啟發(fā)式搜索，javaAbstractThe topic of the course design isA star algorithm demo software, A * algorithm in artificial intelligence is A kind of typical heuristic sear

3、ch algorithm, this is A graphics in the plane ,have more than one node path, the algorithm of minimum through cost.it often be used in the game of mobile computing of NPC, or online games on mobile computing of BOT.The course design requirs to demonstrate the implementation process of the whole algo

4、rithm, can be single step demo, dynamic demonstration, the essenceof the execution process of algorithm demo.on the basis of full understanding of the algorithm, Demonstrateing the algorithm implementation process will involve the Graph drawing, and the programming on image, obviously a high-level l

5、anguage has the characteristics of its development of high efficiency, Java powerful computing and graphics display function, make the image programming more simple and intuitive.This project is based on eclipses Java integrated development environment, A star algorithm demo software was designed an

6、d implemented, showing how A star algorithm of heuristic search and pathfinding.Implements set the starting point and end point, barriers, clear obstacles, directly pathfinding, single step pathfinding, dynamic pathfinding, pathfinding again, add default barrier function of these operations.the user

7、 can use the software according to their requirments, the software fully shows the execution of A star algorithm.Keywords： AStar arithmetic , heuristic search, java目錄 TOC o 1-5 h z HYPERLINK l bookmark0 o Current Document 摘要.0 HYPERLINK l bookmark2 o Current Document Abstract1. HYPERLINK l bookmark4

8、 o Current Document 目錄2. HYPERLINK l bookmark6 o Current Document 1需求分析3.編寫目的3.背景3.A*搜索算法介紹.3.Dijkstra 算法4.java語言介紹 5.java圖形化編程的知識 7.任務(wù)概述7.運行環(huán)境規(guī)定 8.其他A星軟件的優(yōu)劣8.(1)軟件一 8.軟件二9. HYPERLINK l bookmark8 o Current Document 2概要設(shè)計1.0界面設(shè)計10軟件的進入界面設(shè)計10軟件的進入界面的分析10軟件主題界面的設(shè)計1.1軟件主體界面的分析1.1程序需要實現(xiàn)的功能 1.2 HYPERLINK

9、l bookmark10 o Current Document 3詳細設(shè)計1.3類圖的設(shè)計13類之間的關(guān)系說明1.3類圖的分析14程序的實現(xiàn)15程序邏輯的設(shè)計1.5找到link中結(jié)點的F值最小的結(jié)點 1.9響應(yīng)繪制方塊paint的參數(shù)與getGraphics( )2 2程序主體界面 MyPanel中paint函數(shù)做的工作 2 3主體界面類做的工作23鼠標監(jiān)聽 mouseClicked OR mousePressed.24動態(tài)尋路的演示24設(shè)置起點的工作24設(shè)置終點的工作24找不到路徑的提示25 HYPERLINK l bookmark12 o Current Document 4總結(jié)26. H

10、YPERLINK l bookmark14 o Current Document 5致謝27. HYPERLINK l bookmark16 o Current Document 6參考資料281需求分析編寫目的A*算法作為為基本尋路算法常出現(xiàn)在游戲設(shè)計中，剛剛接觸A*算法，難免初學者會產(chǎn)生迷惑，為了使算法的執(zhí)行步驟更加的清晰，是算法的思路完整的展現(xiàn)出來，此次課題的 要求就是用圖形化的方式，一步一步的展現(xiàn) A*算法的執(zhí)行步驟，使想了解 A*算法的人能 夠更清晰的理解此算法，等真正理解了，就會發(fā)現(xiàn)，原來游戲的尋路是這樣的，從而也會 是學習者有更大的興趣深入其他算法的學習。目樂A*搜索算法介紹A*

11、在游戲設(shè)計中有它很典型的用法，是人工智能在游戲中的代表。A*算法在人工智能 中是一種典型的啟發(fā)式搜索算法在說啟發(fā)式搜索之前先提狀態(tài)空間搜索。狀態(tài)空間搜索，如果按專業(yè)點的說法就是將 問題求解過程表現(xiàn)為從初始狀態(tài)到目標狀態(tài)尋找這個路徑的過程。通俗點說，兩點之間求 一線路，這兩點是求解的開始和問題的結(jié)果，而這一線路不一定是直線，可以是曲折的。 由于求解問題的過程中分枝有很多，主要是求解過程中求解條件的不確定性，不完備性造 成的，使得求解的路徑很多這就構(gòu)成了一個圖，我們說這個圖就是狀態(tài)空間。問題的求解 實際上就是在這個圖中找到一條路徑可以從開始到結(jié)果。這個尋找的過程就是狀態(tài)空間搜 索。常用的狀態(tài)空間搜

12、索有深度優(yōu)先和廣度優(yōu)先。廣度優(yōu)先是從初始狀態(tài)一層一層向下找， 直到找到目標為止。深度優(yōu)先是按照一定的順序先查找完一個分支，再查找另一個分支， 以至找到目標為止。這兩種算法在數(shù)據(jù)結(jié)構(gòu)書中都有描述，可以參看這些書得到更詳細的 解釋。前面說的廣度和深度優(yōu)先搜索有一個很大的缺陷就是他們都是在一個給定的狀態(tài)空間 中窮舉。這在狀態(tài)空間不大的情況下是很合適的算法，可是當狀態(tài)空間十分大，且不預(yù)測 的情況下就不可取了。他的效率實在太低，甚至不可完成。在這里就要用到啟發(fā)式搜索了。啟發(fā)式搜索就是在狀態(tài)空間中的搜索對每一個搜索的位置進行評估，得到最好的位置，再從這個位置進行搜索直到目標。這樣可以省略大量無謂的搜索路徑

13、，提高了效率。在啟 發(fā)式搜索中，對位置的估價是十分重要的。采用了不同的估價可以有不同的效果。啟發(fā)中的估價是用估價函數(shù)表示的，如：f(n) = g(n) + h(n)其中f(n)是節(jié)點n的估價函數(shù)，g(n)是在狀態(tài)空間中從初始節(jié)點到 n節(jié)點的實際代 價，h(n)是從n到目標節(jié)點最佳路徑的估計代價。 在這里主要是h(n)體現(xiàn)了搜索的啟發(fā)信 息，因為g(n)是已知的。如果說詳細點，g(n)代表了搜索的廣度的優(yōu)先趨勢。但是當h(n) g(n)時，可以省略g(n),而提高效率。啟發(fā)式搜索其實有很多的算法，比如：局部擇優(yōu)搜索法、最好優(yōu)先搜索法等等。當然 A*也是。這些算法都使用了啟發(fā)函數(shù)，但在具體的選取最

14、佳搜索節(jié)點時的策略不同。像局 部擇優(yōu)搜索法，就是在搜索的過程中選取“最佳節(jié)點”后舍棄其他的兄弟節(jié)點，父親節(jié)點， 而一直得搜索下去。這種搜索的結(jié)果很明顯，由于舍棄了其他的節(jié)點，可能也把最好的節(jié) 點都舍棄了，因為求解的最佳節(jié)點只是在該階段的最佳并不一定是全局的最佳。最好優(yōu)先 就聰明多了，他在搜索時，并沒有舍棄節(jié)點(除非該節(jié)點是死節(jié)點)，在每一步的估價中 都把當前的節(jié)點和以前的節(jié)點的估價值比較得到一個“最佳的節(jié)點”。這樣可以有效的防 止“最佳節(jié)點”的丟失。那么 A*算法又是一種什么樣的算法呢？其實A*算法也是一種最好優(yōu)先的算法，只不過要加上一些約束條件罷了。由于在一些 問題求解時，我們希望能夠求解出

15、狀態(tài)空間搜索的最短路徑，也就是用最快的方法求解問 題，A*就是干這種事情的！我們先下個定義，如果一個估價函數(shù)可以找出最短的路徑，我們稱之為可采納性。A*算法是一個可采納的最好優(yōu)先算法。A*算法的估價函數(shù)可表示為：f(n) = g(n) + h(n)這里，f(n)是估價函數(shù)，g(n)是起點到節(jié)點n的最短路徑值，h(n)是n到目標的最 短路經(jīng)的啟發(fā)值。舉一個例子，其實廣度優(yōu)先算法就是A*算法的特例。其中g(shù)(n)是節(jié)點所在的層數(shù)，h(n)=0 ,這種h(n)肯定小于h(n),所以由前述可知廣度優(yōu)先算法是一種可 采納的。實際也是。當然它是一種最臭的 A*算法。再說一個問題，就是有關(guān)h(n)啟發(fā)函數(shù)的信

16、息性。h(n)的信息性通俗點說其實就是在 估計一個節(jié)點的值時的約束條件，如果信息越多或約束條件越多則排除的節(jié)點就越多，估 價函數(shù)越好或說這個算法越好。這就是為什么廣度優(yōu)先算法的那么臭的原因了，誰叫它的 h(n)=0 , 一點啟發(fā)信息都沒有。但在游戲開發(fā)中由于實時性的問題，h(n)的信息越多，它的計算量就越大，耗費的時間就越多。就應(yīng)該適當?shù)臏p小h(n)的信息，即減小約束條件。但算法的準確性就差了，這里就有一個平衡的問題。游戲中速度和精確度之間的選擇并不是全局的。在地圖上的某些區(qū)域，精確度是重要 的，你可以基于此進行動態(tài)選擇。例如，假設(shè)我們可能在某點停止重新計算路徑或者改變 方向，則在接近當前位置

17、的地方，選擇一條好的路徑則是更重要的，因此為何要對后續(xù)路 徑的精確度感到厭煩？或者，對于在地圖上的一個安全區(qū)域，最短路徑也許并不十分重要， 但是當從一個敵人的村莊逃跑時，安全和速度是最重要的。所以A星算法應(yīng)用在游戲中時可以根據(jù)具體的情況為各種不同的障礙設(shè)置不同的加權(quán)值是盡可能的出最有效的方案。Dijkstra 算法圖1.1 Dijkstra算法的執(zhí)行圖Dijkstra 算法迪科斯徹算法使用了廣度優(yōu)先搜索解決非負權(quán)有向圖的單源最短路徑 問題，算法最終得到一個最短路徑樹。并沒有啟發(fā)尋路，屬于A*算法的特例。這個算法的 工作過程就是從起始點開始，不斷的向未知點擴展，使從已知點集合到達任意未知點的距

18、離權(quán)重都是最小的，這樣當擴展到終止點的時候，也就找到了最短的權(quán)重。java語言介紹(1)起源Java是由Sun Microsystems公司于1995年5月推出的Java面向?qū)ο蟪绦蛟O(shè)計語言 (以下簡稱Java語言)和Java平臺的總稱。由James Gosling和同事們共同研發(fā)，并在 1995年正式推出。Java最初被稱為Oak,是1991年為消費類電子產(chǎn)品的嵌入式芯片而設(shè) 計的。1995年更名為Java,并重新設(shè)計用于開發(fā)Internet應(yīng)用程序。用Java實現(xiàn)的HotJava 瀏覽器(支持Java applet )顯示了 Java的魅力：跨平臺、動態(tài)的 Web Internet 計算。

19、 從此，Java被廣泛接受并推動了 Web勺迅速發(fā)展，常用的瀏覽器均支持 Javaapplet。另 一方面，Java技術(shù)也不斷更新。(2)組成Java由四方面組成：Java編程語言Java文件格式Java 虛擬機(JVM)Java應(yīng)用程序接口(Java API)(3)體系Java 分為三個體系 JavaSE (J2S6 (Java2 Platform Standard Edition , java 平臺 標準版)，JavaEE(J2EE)(Java 2 Platform,Enterprise Edition , java 平臺企業(yè)版), JavaME(J2ME)(Java 2 Platform

20、 Micro Edition , java 平臺微型版)。(4)優(yōu)勢與傳統(tǒng)程序不同，Sun公司在推出Java之際就將其作為一種開放的技術(shù)。全球數(shù)以 萬計的Java開發(fā)公司被要求所設(shè)計的Java軟件必須相互兼容?！癑ava語言靠群體的力 量而非公司的力量”是Sun公司的口號之一，并獲得了廣大軟件開發(fā)商的認同。這與微軟 公司所倡導的注重精英和封閉式的模式完全不同。Sun公司對Java編程語言的解釋是：Java編程語言是個簡單、面向?qū)ο?、分布式?解釋性、健壯、安全與系統(tǒng)無關(guān)、可移植、高性能、多線程和動態(tài)的語言。Java平臺是基于Java語言的平臺。這樣的平臺非常流行。因此微軟公司推出了與之 競爭的

21、.NET平臺以及模仿Java的C#言。Java是功能完善的通用程序設(shè)計語言，可以用來開發(fā)可靠的、要求嚴格的應(yīng)用程序。(5)語言特征Java編程語言的風格十分接近 C語言、C+1言。Java是一個純粹的面向?qū)ο蟮某绦?設(shè)計語言，它繼承了 C+語言面向?qū)ο蠹夹g(shù)的核心。Java舍棄了 C語言中容易引起錯誤的 指針(以引用取代)、運算符重載(operator overloading )、多重繼承(以接口取代) 等特性，增加了垃圾回收器功能用于回收不再被引用的對象所占據(jù)的內(nèi)存空間，使得程序 員不用再為內(nèi)存管理而擔憂。在 Java 1.5 版本中，Java又引入了泛型編程(Generic Programm

22、ing) 類型安全的枚舉、不定長參數(shù)和自動裝 /拆箱等語言特性。Java不同于一般的編譯執(zhí)行計算機語言和解釋執(zhí)行計算機語言。它首先將源代碼編譯 成二進制字節(jié)碼（bytecode）,然后依賴各種不同平臺上的虛擬機來解釋執(zhí)行字節(jié)碼。從 而實現(xiàn)了 “一次編譯、到處執(zhí)行”的跨平臺特性。不過，每次的執(zhí)行編譯后的字節(jié)碼需要 消耗一定的時間，這同時也在一定程度上降低了Java程序的性能。（6）主要特性Java語言是易學的。Java語言的語法與C語言和C+胡言很接近，使得大多數(shù)程序員 很容易學習和使用Java。另一方面，Java丟棄了 C+”很少使用的、很難理解的、令人迷 惑的那些特性，如操作符重載、多繼承、

23、自動的強制類型轉(zhuǎn)換。特別地，Java語言不使用指針，而是引用。并提供了自動的廢料收集，使得程序員不必為內(nèi)存管理而擔憂。Java語言是強制面向?qū)ο蟮?。Java語言提供類、接口和繼承等原語，為了簡單起見， 只支持類之間的單繼承，但支持接口之間的多繼承，并支持類與接口之間的實現(xiàn)機制（關(guān) 鍵字為implements ）。Java語言全面支持動態(tài)綁定，而C+胡言只對虛函數(shù)使用動態(tài)綁定。 總之，Java語言是一個純的面向?qū)ο蟪绦蛟O(shè)計語言。Java語言是分布式的。Java語言支持Internet應(yīng)用的開發(fā)，在基本的Java應(yīng)用編程 接口中有一個網(wǎng)絡(luò)應(yīng)用編程接口（ java net ）,它提供了用于網(wǎng)絡(luò)應(yīng)用編

24、程的類庫，包括 URL URLConnection、Socket ServerSocket 等。Java 的 RMI （遠程方法激活）機制也是 開發(fā)分布式應(yīng)用的重要手段。Java語言是健壯的。Java的強類型機制、異常處理、垃圾的自動收集等是 Java程序 健壯性的重要保證。對指針的丟棄是Java的明智選擇。Java的安全檢查機制使得Java更 具健壯性。Java語言是安全的。Java通常被用在網(wǎng)絡(luò)環(huán)境中，為此，Java提供了一個安全機制 以防惡意代碼的攻擊。除了 Java語言具有的許多安全特性以外，Java對通過網(wǎng)絡(luò)下載的 類具有一個安全防范機制（類 ClassLoader）,如分配不同的名

25、字空間以防替代本地的同 名類、字節(jié)代碼檢查，并提供安全管理機制（類 SecurityManager ）讓Java應(yīng)用設(shè)置安全 哨兵。Java語言是體系結(jié)構(gòu)中立的。Java程序（后綴為java的文件）在Java平臺上被編譯 為體系結(jié)構(gòu)中立的字節(jié)碼格式（后綴為 class的文件），然后可以在實現(xiàn)這個 Java平臺 的任何系統(tǒng)中運行。這種途徑適合于異構(gòu)的網(wǎng)絡(luò)環(huán)境和軟件的分發(fā)。Java語言是解釋型的。如前所述，Java程序在Java平臺上被編譯為字節(jié)碼格式，然 后可以在實現(xiàn)這個Java平臺的任何系統(tǒng)中運行。在運行時，Java平臺中的Java解釋器對 這些字節(jié)碼進行解釋執(zhí)行，執(zhí)行過程中需要的類在聯(lián)接階段

26、被載入到運行環(huán)境中。Java是性能略高的。與那些解釋型的高級腳本語言相比，Java的性能還是較優(yōu)的。Java語言是原生支持多線程的。在 Java語言中，線程是一種特殊的對象，它必須由Thread類或其子（孫）類來創(chuàng)建。通常有兩種方法來創(chuàng)建線程：其一，使用型構(gòu)為 Thread（Runnable）的構(gòu)造子將一個實現(xiàn)了 Runnable接口的對象包裝成一個線程，其二， 從Thread類派生出子類并重寫run方法，使用該子類創(chuàng)建的對象即為線程。值得注意的 是Thread類已經(jīng)實現(xiàn)了 Runnable接口，因此，任何一個線程均有它的 run方法，而run 方法中包含了線程所要運行的代碼。線程的活動由一組

27、方法來控制。Java語言支持多個線 程的同時執(zhí)行，并提供多線程之間的同步機制（關(guān)鍵字為synchronized ）。Java語言是動態(tài)的。Java語言的設(shè)計目標之一是適應(yīng)于動態(tài)變化的環(huán)境。Java程序需要的類能夠動態(tài)地被載入到運行環(huán)境，也可以通過網(wǎng)絡(luò)來載入所需要的類。這也有利于 軟件的升級。另外，Java中的類有一個運行時刻的表示，能進行運行時刻的類型檢查。Java語言的優(yōu)良特性使得Java應(yīng)用具有無比的健壯性和可靠性，這也減少了應(yīng)用系 統(tǒng)的維護費用。Java對對象技術(shù)的全面支持和Java平臺內(nèi)嵌的API能縮短應(yīng)用系統(tǒng)的開 發(fā)時間并降低成本。Java的編譯一次，到處可運行的特性使得它能夠提供一

28、個隨處可用的 開放結(jié)構(gòu)和在多平臺之間傳遞信息的低成本方式。特別是Java企業(yè)應(yīng)用編程接口（ JavaEnterprise APIs ）為企業(yè)計算及電子商務(wù)應(yīng)用系統(tǒng)提供了有關(guān)技術(shù)和豐富的類庫。java圖形化編程的知識java的GUI編程（Graphic User Interface ,圖形用戶接口），是在它的抽象窗口工 具箱（Abstract WindowToolkit , AWT上實現(xiàn)的，java.awt是AWT勺工具類庫，其中包 括了豐富的圖形、用戶界面元件和布局管理器的支持。GUI主要用在兩個地方：Application ； Applet。GUI界面：用戶與程序之間交互的一個控制面板，具內(nèi)

29、包含有菜單，控件（或組件），容器并能 響應(yīng)用戶的事件?，F(xiàn)在有各種各樣的窗口系統(tǒng)，不同的窗口系統(tǒng)提供給程序設(shè)計的程序庫是大不一樣的， 例如，基于 Windows的SDK和基于Unix平臺的X Windows的Xlib。為了使程序能在不同的窗口系統(tǒng)下運行，Java提出了 “抽象窗口系統(tǒng)”的概念，提供 了 AWT（抽象窗口工具箱），使得java能夠在不同的窗口系統(tǒng)下運行。Java中的GUI實現(xiàn)方式：采用AWT（抽象窗口工具集）從而可使 GUI適用于不同OS的環(huán)境。特點如下：其具體實現(xiàn)由目標平臺下的 OS來解釋，從而導致Java GUI在不同平臺下會出現(xiàn)不 同的運行效果（窗口外觀、字體等的顯示效果會發(fā)

30、生變化）。 組件在設(shè)計時不應(yīng)采用絕對定位，而應(yīng)采用布局管理器來實現(xiàn)相對定位，以達到與平臺及設(shè)備無關(guān)。3）新增的Swing GUI組件AWffi件以及事件響應(yīng)不及微軟的 SDK富（因為有些OS平臺無彳軟的Window卻件）， Sun在Java2中新增了 Swing GUI組件。但是，AWT:匕較簡單，功能也能滿足大多數(shù)界面 需求，特別在Java Applet的設(shè)計中受到了普遍的應(yīng)用。任務(wù)概述本次課程設(shè)計的題目是“ A星算法的演示系統(tǒng)”，A*算法在人工智能中是一種典型的 啟發(fā)式搜索算法，這是一種在圖形平面上，有多個節(jié)點的路徑，求出最低通過成本的算法。 常用于游戲中的NPC勺移動計算，或在線游戲的B

31、OTB移動計算上。本次課程設(shè)計要求能夠演示出整個算法的執(zhí)行過程，能夠進行單步演示，動態(tài)演示，把算法的執(zhí)行過程的精髓 演示出來。實現(xiàn)了設(shè)置起點、設(shè)置終點、設(shè)置障礙、清除障礙、直接尋路、單步尋路、動態(tài)尋路、 重新尋路、添加默認障礙這些功能的操作。運行環(huán)境規(guī)定任何安裝java運行環(huán)境的系統(tǒng)1：在eclipse中加載該項目，直接打開并運行該項目。2：安裝java運行環(huán)境的機器中，控制臺下，進入bin目錄，輸入java .java13:安裝java運行環(huán)境的機器中，直接運行已經(jīng)打包好的axing.jar其他A星軟件的優(yōu)劣(1)軟件圖1.2 C#完成的A*算法的演示程序這個程序的好處就是實現(xiàn)的功能很全。優(yōu)

32、點：(1)對于障礙的不同級別，進行了設(shè)置，表現(xiàn)在程序上我覺得就是障礙的加權(quán)值的不 同，而且在實際的執(zhí)行過程中也可以越過一些障礙。(2)時間的延遲進行了設(shè)置，對于程序的演示效果能有更好的展現(xiàn)。(3)方格的大小也進行了設(shè)置，可以進行隨便的調(diào)節(jié)，也是為了方便展示。缺點：(1)功能過于復(fù)雜，初次拿到軟件的人會先進行一段時間的熟悉，不適合激發(fā)初學A星算法的人的興趣。(2)文字說明多，也是其復(fù)雜原因的一種，如果用圖形化的方式進行更多的說明會事 半功倍。(2)軟件二這個軟件演示的很清晰，說明很到位，沒有實現(xiàn)動態(tài)執(zhí)行的功能。優(yōu)點：該有的功能一般都有了，操作起來并不復(fù)雜，演示效果很好，圖形化的執(zhí)行很不錯。缺點：

33、每次執(zhí)行都要全屏展示，在我的電腦上如果一旦按 WINDOWS進行其他操作，在打開 此程序，發(fā)現(xiàn)看不到之前的執(zhí)行路徑了?；谏厦娴难芯砍晒?，我本次使用JAVA語言寫的A星算法演示程序，爭取盡可能的簡 單易操作。2概要設(shè)計界面設(shè)計軟件的進入界面設(shè)計圖2.1軟件的進入界面軟件的進入界面的分析一般軟件都有自己的進入界面，軟件的進入界面能夠使軟件更富有意義，界面設(shè) 計是為了滿足軟件專業(yè)化標準化的需求而產(chǎn)生的對軟件的使用界面進行美化優(yōu)化規(guī)范化 的設(shè)計分支。(2)此界面大小長950像素，寬710像素，能夠滿足大部分計算機的整個屏幕的顯示， 跟程序的主體界面大小一致。圖形的顯示位置在 x=30, y=10的位

34、置?！癆Star算法演示軟 件”幾個字采用70號字，總體加粗。作者和姓名及“進入演示程序”字體采用40號，F(xiàn)ont _LAYOUT _NO _LIMIT_CONTE笳。(3)整個框架是外面的 MyFace包含F(xiàn)acePanel ,左右圖形的繪制通過 FacePanel中 的paint函數(shù)實現(xiàn)。(4)背景是宇宙，有很多的星星，周圍放出萬丈光芒，宇宙能夠給人以無限的想象， 此處希望本程序的演示也能給使用者以無限的想象。藍色的光線是從兩邊的中心位置依次 向上面和下面畫線，下面的間距為 30個像素，這樣的設(shè)計能夠突出中間文字的顯示效果。(5)此處星星的設(shè)計和程序的名稱有相對應(yīng)的地方，星星的繪制是通過在

35、界面的區(qū)域 內(nèi)隨機產(chǎn)生450個三種顏色的點來顯示的。(6)當點擊“進入程序演示”就會啟動一個線程執(zhí)行顯示程序主體界面的程序，同時 本界面會隱藏。軟件主題界面的設(shè)計圖2.2軟件主體界面軟件主體界面的分析(1)整個FRAM的大小，長950像素，寬710像素，內(nèi)包含兩個Panel,頂層的Panel 包含4個JRadioButton ,分別是“設(shè)置起點”、“設(shè)置終點”、“設(shè)置障礙”，“清除障 礙”。下面的Panel是自定義的，包含左邊的方塊區(qū)域和右邊的說明區(qū)域，方塊區(qū)域的長 700像素，寬600像素。(2)小方塊的邊長為50,整個區(qū)域長14個方塊，高12個方塊。之所以這幾這么大 小，是因為，這樣的大小

36、基本適合13寸以上的電腦能夠在整個屏幕內(nèi)演示，能夠滿足大 部分使用此軟件的人員的要求。(3) JRadioButton剛開始默認選定是設(shè)置障礙，可以通過點擊其他的單選按鈕，進 行相應(yīng)的操作。當點擊其他的單選按鈕后，鼠標對下面方框區(qū)域的操作與其對應(yīng)。(4)右邊說明的主題意思是通過方塊顏色的不同來區(qū)分起始結(jié)點，終止結(jié)點，CLOSE中的節(jié)點，OPEW的節(jié)點等。另外箭頭指向啟發(fā)式尋路過程中的每個節(jié)點的前驅(qū)。2.2程序需要實現(xiàn)的功能1:設(shè)置起點2:設(shè)置終點3:設(shè)置障礙4:消除障礙5:直接尋路（點擊按鈕就顯示出最后的尋路結(jié)果）6:單步尋路（通過不斷的點擊按鈕，一步一步顯示出程序的尋路過程）7:動態(tài)尋路8:

37、重新尋路9:添加默認障礙3.1類圖的設(shè)計ni 二 I.nte=r sy： Integeri2ntsist H: Intsfitr F:IntiE*r H*ca3tFTMi; String sdirect:Znteger kf1ag:integaTaca-j.cT : LnliziLted2.3詳細設(shè)計KxingT-alhH 7 Integer-CHth:integET *otartx 二nte.&r startT：Inteear-&ndT：工nt號彳工-pr ice 二Integer= zzDirect _j lUhIlei_ . .-te-pG 二：ntBETHisSetter:Boolea

38、n心噎h(huán)： lAjiftENdsvcloi#List :Axir：ffN&dtk*pwnL 己 5t 二 RxfngXodeAxins-fiad3mFAfunStep,horPath-gap:Integer size 二lEteaST* 二三工匚he :Zntegex iFrcsr：:ntsger vuinE：Axini HE.M：UnlEz3Wt看, 仁二 1 二 r 7 er ;UiB.,jpliUnlioitt., =W1 ：X?Panel-jrbl :Unl isit. tS jr b2: Uni lz：lt . cjrbl .Ud imt. jblfUnli.aite . wjfc2

39、：Unl:aite . wjb3：rnLiHitE.-Jc4: Unlisite. e jc 52 tinliniite.,Unliziiti&d. wcolcr lUiliffii.u . *ch.&n.E-Dnt#&r -fag an 二1 nt 仔8丁 IFrame fL earl is t *5 tit&ck *zBDU.sFre Ad itjKttStat tCha. KtionPETf-Tsed *run圖3.1 A星算法演示軟件的類圖3.2類之間的關(guān)系說明(1)繼承關(guān)系：繼承指的是一個類(稱為子類、子接口)繼承另外的一個類(稱為父 類、父接口)的功能，并可以增加它自己的新功能的能

40、力。在 Java中繼承關(guān)系通過關(guān)鍵 字extends明確標識，在設(shè)計時一般沒有爭議性。在 UM送圖設(shè)計中，繼承用一條帶空心 三角箭頭的實線表示，從子類指向父類，或者子接口指向父接口。(2)實現(xiàn)關(guān)系：實現(xiàn)指的是一個class類實現(xiàn)interface 接口(可以是多個)的功能, 實現(xiàn)是類與接口之間最常見的關(guān)系。在Java中此類關(guān)系通過關(guān)鍵字implements明確標識， 在設(shè)計時一般沒有爭議性。在 UMLfe圖設(shè)計中，實現(xiàn)用一條帶空心三角箭頭的虛線表示， 從類指向?qū)崿F(xiàn)的接口。(3)依賴關(guān)系：簡單的理解，依賴就是一個類 A使用到了另一個類B,而這種使用關(guān) 系是具有偶然性的、臨時性的、非常弱的，但是類

41、 B的變化會影響到類A。比如某人要過 河，需要借用一條船，此時人與船之間的關(guān)系就是依賴。表現(xiàn)在代碼層面，為類 B作為參 數(shù)被類A在某個method方法中使用。在UM改圖設(shè)計中，依賴關(guān)系用由類 A指向類B的 帶箭頭虛線表示。(4)關(guān)聯(lián)關(guān)系：關(guān)聯(lián)體現(xiàn)的是兩個類之間語義級別的一種強依賴關(guān)系，比如我和我的 朋友，這種關(guān)系比依賴更強、不存在依賴關(guān)系的偶然性、關(guān)系也不是臨時性的，一般是長 期性的，而且雙方的關(guān)系一般是平等的。關(guān)聯(lián)可以是單向、雙向的。表現(xiàn)在代碼層面，為 被關(guān)聯(lián)類B以類的屬性形式出現(xiàn)在關(guān)聯(lián)類 A中，也可能是關(guān)聯(lián)類A引用了一個類型為被關(guān) 聯(lián)類B的全局變量。在UM送圖設(shè)計中，關(guān)聯(lián)關(guān)系用由關(guān)聯(lián)類 A

42、指向被關(guān)聯(lián)類B的帶箭頭 實線表示，在關(guān)聯(lián)的兩端可以標注關(guān)聯(lián)雙方的角色和多重性標記。(5)聚合關(guān)系：聚合是關(guān)聯(lián)關(guān)系的一種特例，它體現(xiàn)的是整體與部分的關(guān)系，即has-a 的關(guān)系。此時整體與部分之間是可分離的，它們可以具有各自的生命周期，部分可以屬于 多個整體對象，也可以為多個整體對象共享。比如計算機與CPU公司與員工的關(guān)系等，比如一個航母編隊包括?？漳概?、驅(qū)護艦艇、艦載飛機及核動力攻擊潛艇等。表現(xiàn)在代碼 層面，和關(guān)聯(lián)關(guān)系是一致的，只能從語義級別來區(qū)分。在UMLfe圖設(shè)計中，聚合關(guān)系以空心菱形加實線箭頭表小0(6)組合關(guān)系：組合也是關(guān)聯(lián)關(guān)系白一種特例，它體現(xiàn)的是一種contains-a的關(guān)系，這種關(guān)

43、系比聚合更強，也稱為強聚合。它同樣體現(xiàn)整體與部分間的關(guān)系，但此時整體與部 分是不可分的，整體的生命周期結(jié)束也就意味著部分的生命周期結(jié)束，比如人和人的大腦。表現(xiàn)在代碼層面，和關(guān)聯(lián)關(guān)系是一致的，只能從語義級別來區(qū)分。在UML1圖設(shè)計中，組合關(guān)系以實心菱形加實線箭頭表示。3.3類圖的分析(1)類圖(Class diagram)是顯示了模型的靜態(tài)結(jié)構(gòu)，特別是模型中存在的類、類的 內(nèi)部結(jié)構(gòu)以及它們與其他類的關(guān)系等，一般在詳細設(shè)計過程中出現(xiàn)，主要用來描述系統(tǒng)中 各個模塊中類之間的關(guān)系，包括類或者類與接口的繼承關(guān)系，類之間的依賴、聚合等關(guān)系。(2)此次的A*算法演示程序共用到了 7個類，此7個類的關(guān)系相對比

44、較簡單，有依 賴關(guān)系和聚合關(guān)系組成。java1類是程序的入口點，包含程序需的 main函數(shù)，main函數(shù)產(chǎn)生了界面類的 對象。進而界面類會調(diào)用界面類包含的 Panel類的paint函數(shù)，繪制出軟件的進入界面。軟件的進入界面類對應(yīng) MyFace類,MyFace類包含F(xiàn)acePanel類的對象，此界面 的繪圖操作是通過FacePanel類的paint函數(shù)來繪制的，(見上面的圖2.1軟件的進入界 面)當點擊”進入演示程序”按鈕之后，會啟動一個線程，此線程會產(chǎn)生MyFram酸的對象。MyFram嵌是程序的主題界面顯示的類，如圖 2.2軟件主體界面，此類包含兩個 Panel,頂層的Panel包含單選按鈕

45、和按鈕，底層的 Panel包含圖形的繪制主體方塊和說 明信息。MyPanel是自己定義的JPanel,它繼承自JPanel,這個類主要是畫出主體方塊 區(qū)域和現(xiàn)實說明信息。Axing類用來設(shè)計整個A星算法，其中包含圖形的起始坐標，終止坐標，每走一 步的帶權(quán)值，以及最重要的 A星算法的實現(xiàn)代碼等。AxingNode類是程序的結(jié)點類，它設(shè)計了程序的結(jié)點，因為A星算法要用到兩個鏈表，鏈表的結(jié)點類型就是 AxingNode類型，每個節(jié)點都包含自己在方塊區(qū)域的坐標，GH、F值，指向前驅(qū)的字符串，direct用來指示cameFromfl勺方向，flag用來標記每個結(jié)點 的類型，0:起始點1:障礙2:目標點3

46、:其他，還有顏色值。3.4程序的實現(xiàn)程序邏輯的設(shè)計我此處用了兩個鏈表：OpenList初始化時存放起始結(jié)點，用來存放還為探測的結(jié)點。CloseList初始化為空，用來存放已經(jīng)探測過得結(jié)點。整個圖的結(jié)點用一個 AxingNode型數(shù)組來存放因為A星算法需要進行啟發(fā)式尋路，我采用的啟發(fā)式尋路的方式為當前結(jié)點與目標結(jié) 點的橫縱坐標的和作為啟發(fā)尋路的啟發(fā) H值，G值為前驅(qū)結(jié)點到起始結(jié)點的權(quán)值加上前驅(qū) 結(jié)點到本結(jié)點的權(quán)值。F=G+H乍為總權(quán)值。每次比較就是按照 F值進行的比較。F = G + HG=從起點沿著產(chǎn)生的路徑，移動到網(wǎng)格上指定方格的移動耗費。H=從網(wǎng)格上那個方格移動到終點 B的預(yù)估移動耗費。正

47、如上面所說，G表示沿路徑從起點到當前點的移動耗費。在這個例子里，我們令水 平或者垂直移動的耗費為10。既然我們在計算沿特定路徑通往某個方格的G值，求值的方法就是取它的前驅(qū)結(jié)點的G值，然后依照它相對前驅(qū)結(jié)點直角方向（非對角線），增加和10。例子中這個方法的需求 會變得更多，因為我們從起點方格以外獲取了不止一個方格。H值可以用不同的方法估算。我們這里使用的方法被稱為曼哈頓方法，它計算從當前 格到目的格之間水平和垂直的方格的數(shù)量總和，忽略對角線方向。然后把結(jié)果乘以10。這被成為曼哈頓方法是因為它看起來像計算城市中從一個地方到另外一個地方的街區(qū)數(shù)，在 那里你不能沿對角線方向穿過街區(qū)。很重要的一點，我們

48、忽略了一切障礙物。這是對剩余 距離的一個估算，而非實際值，這也是這一方法被稱為啟發(fā)式的原因。F的值是G和H的和。第一步搜索的結(jié)果可以在下面的圖表中看到。 F,G和H的評分被 寫在每個方格里。正如在緊挨起始格右側(cè)的方格所表示的，F(xiàn)被打印在左上角，G在左下角，H則在右下角。具體算法的尋路思路如下：（1）將從起始點開始，方塊添加到 open列表中，該列表有最小的和值。且將這個方 塊稱為S吧。（2）將S從open列表移除，然后添加S到closed列表中。（3）對于與S相鄰的每一塊可通行的方塊 T:（這里我問題只要有上下左右可以通行）1）如果T為終止結(jié)點，則結(jié)束。2）如果T在closed列表中：不管它。

49、3）如果T不在open列表中：添加它然后計算出它的和值，并標記S為他的前驅(qū)。4）如果T已經(jīng)在open列表中：當我們使用當前生成的路徑到達那里時計算新 F值，檢查新F值與原有F值相比是否更小。如果是，更新它的 F值和它的前驅(qū)。5)繼續(xù)掃描open列表中擁有最小的F值的結(jié)點，記為S,重復(fù)(3)/A星算法的具體代碼如下public boolean Afun()(while(!openList.isEmpty() (AxingNode tempNode=openList.get(findMinF(openList); if(tempNode.flag=2)/如果是最后一個結(jié)點(pathstartxst

50、arty.F=pathendxendy.F;pathstartxstarty.H=pathendxendy.G; return true;/能夠到達最后的結(jié)點openList.remove(tempNode);closeList.add(tempNode);/另外添加，對于openList,closeList中的結(jié)點的顏色進行設(shè)置if(tempNode.flag!=0)/如果不是開始結(jié)點(tempNode.color=Color.cyan;/藍綠色標志為進入 closeList 中的結(jié)點。/對于剛加入closeList即剛從openList中刪除的結(jié)點，看其周圍的結(jié)占 八LinkedList

51、neighborNodes=new LinkedList();if(tempNode.x0&pathtempNode.x-1tempNode.y.flag!=1&!closeList.contai ns(pathtempNode.x-1tempNode.y)/ 左 (如果openList不包含周圍的結(jié)點，即周圍的結(jié)點并沒有提前在 openList中，那么可以更改directif(!openList.contains(pathtempNode.x-1tempNode.y)(pathtempNode.x-1tempNode.y.direct=1;/neighborNodes加入的順序是“左右上下”

52、，這個順序隨意neighborNodes.add(pathtempNode.x-1tempNode.y);if(tempNode.x0&pathtempNode.xtempNode.y-1.flag!=1&!closeList.contai ns(pathtempNode.xtempNode.y-1)/ 上 if(!openList.contains(pathtempNode.xtempNode.y-1) pathtempNode.xtempNode.y-1.direct=3; neighborNodes.add(pathtempNode.xtempNode.y-1); if(tempNode

53、.y11&pathtempNode.xtempNode.y+1.flag!=1&!closeList.conta ins(pathtempNode.xtempNode.y+1)/ 下 if(!openList.contains(pathtempNode.xtempNode.y+1) pathtempNode.xtempNode.y+1.direct=2; neighborNodes.add(pathtempNode.xtempNode.y+1); isBetter=false;/ 很重要，防止之前的 for(i=0;ineighborNodes.size();i+) /if(closeList

54、.contains(neighborNodes.get(i)/continue;/中的/tempNode 是從openList中取出的最小的，剛加入 closeList 結(jié)點/tempG指按照這個結(jié)點計算出的四周的結(jié)點的G值tempG=pathtempNode.xtempNode.y.G+price;/從起點至 Uneighbor的G距離if(!openList.contains(neighborNodes.get(i) openList.add(neighborNodes.get(i);isBetter=true;else if(tempGneighborNodes.get(i).G)/op

55、enList 之前已經(jīng)包含neighborNode結(jié)點，但是按照當前的結(jié) 點計算tempG會更小一些if(neighborNodes.get(i).xtempNode.x) neighborNodes.get(i).direct=0;if(neighborNodes.get(i).ytempNode.y) neighborNodes.get(i).direct=2;if(neighborNodes.get(i).ytempNode.y) neighborNodes.get(i).direct=3; isBetter=true; else isBetter=false; if(isBetter)

56、 鄰居節(jié)點X小于當前指向左指向上指向下neighborNodes.get(i).cameFrom=Character.toString(szDirectneighborNodes.ge t(i).direct);neighborNodes.get(i).G=tempG;neighborNodes.get(i).H=(Math.abs(endx-neighborNodes.get(i).x)+Math.abs(end y-neighborNodes.get(i).y)*price;neighborNodes.get(i).F=neighborNodes.get(i).G+neighborNode

57、s.get(i).H;if(neighborNodes.get(i).flag!=2)/如果不是終止結(jié)點 neighborNodes.get(i).color=Color.blue;/藍色設(shè)置為加入openList中的結(jié)點的顏色 /end for(neighbor) /end while return false; 代碼說明： 代碼中的path是相對于主體界面(圖2.2軟件主體界面)桔黃色尋路區(qū)域的二維數(shù) 組代碼表示，是AXingNode類型的結(jié)點。 neighboeNodes也是AXingNode類型的鏈表的表示。用來存飯每次要進行拓展的當前 結(jié)點的可以進行再探測的結(jié)點。 總體的執(zhí)行思路就是

58、按照上面給出的執(zhí)行邏輯進行的編碼。3.3.2找到link中結(jié)點的F值最小的結(jié)點/找到link中結(jié)點的F值最小的結(jié)點的下標(最后探測到的) /從后向前掃描，找到最前面的最小的F的結(jié)點的下標，返回注意探測的鏈表因為下標從0開始都是數(shù)據(jù)，所以使用前一定要判斷鏈表不為空才 行！ ！ ！public int findMinF(LinkedList link) int i,minF,index=0;minF=link.get(0).F;/從前向后掃描，找到最小的那個 F的下標，如果幾個相同的下標， /取最后面的最小的那個，這樣可以以最快的方式到達目標結(jié)點 for(i=1;ilink.size();i+)

59、if(link.get(i).F=minF)/*如果此處沒有=,那么會去最前面的最小的結(jié)點，會探測一些無用的點。 index=i;minF=link.get(i).F;)return index;/返回下標探測結(jié)果如下:圖3.2 FindMin 加上“=”的執(zhí)行效果圖如果/*處的 =改成 ,代碼如下：public int findMinF(LinkedList link)int i,minF,index=0;minF=link.get(0).F;for(i=1;ilink.size();i+)if(link.get(i).FminF)/* 此處沒有=index=i;minF=link.get(

60、i).F;return index;/ 返回下標)對于相同的障礙，結(jié)果如下:圖3.3 FindMin 不加上“=”的執(zhí)行效果圖很明顯，后面的情況會探測很多無用功的結(jié)點。通過此函數(shù)的演示效果，可以說明不同的最小值選取防止對于程序的執(zhí)行結(jié)果優(yōu)化程 度是不同的，這里之所以選取從前向后最后探測到的那個最小的結(jié)點作為繼續(xù)探測的最小 的結(jié)點，是因為(1)每次探測結(jié)點都是在鏈表后面進行插入。(2)每次探測我們做的選擇都是目前最優(yōu)的選擇， 及選擇最接近目標結(jié)點的那個結(jié)點 進行探測。(3)因為我的啟發(fā)式搜索的H的計算采用的是通過當前結(jié)點和目標結(jié)點橫縱坐標的絕 對值之差相加。所有不算是最精確的啟發(fā)式尋路，尋路過程