【正文】 學(xué)號： 1620868 上海 建橋?qū)W院 本科生畢業(yè)設(shè)計（論文） 基于 A*算法的路徑尋找 學(xué) 院： 商學(xué)院 專 業(yè)： 國際經(jīng)濟與貿(mào)易 班 級： B162 姓 名： 阮晨陽 指導(dǎo)老師：史小宏 完成日期： 2020年 11月 基于 A*算法的路徑尋找 I 基于 A*算法的路徑尋找 摘 要 啟發(fā)式搜索算法的 有很多種類，其中一種就是 A*搜索算法。在狀態(tài)空間對每一個可能的位置進行判斷 ， 并且根據(jù)一定的判斷標準得出最優(yōu)化的位置，然后以這個位置作為開始繼續(xù)搜索到終點目標位置，以上就是啟發(fā)式搜素的 基本的定義。 對于每次都要選取最小估價的節(jié)點，應(yīng)該用到最小優(yōu)先級隊列（也叫最小二叉堆）。 可以直接使用。當(dāng)然不要忘了重載自定義節(jié)點的比較操作符。 A*算法的特點： A*算法在理論上是時間最優(yōu)的，但是也有缺點： 在理論上最差的情況下， 它的空間增長 將有可能是 指數(shù)級別的。 這一搜索算法的的好處就是可以將很多的不需要的冗余的路徑略去，從而使得時間和空間的效率大大提升。它的主要的組成部分為 OpenList,CloseList 和估價函數(shù)。 他可以應(yīng)用在路由的路徑查找，地圖上路徑查找。 關(guān)鍵詞：啟發(fā)式算法，搜索路徑， A*算法，估 價函數(shù) 基于 A*算法的路徑尋找 II Based on the path of the A * algorithm to find Abstract Heuristic search algorithm, there are many types, one of which is A * 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 select 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 fet the overloaded selfdefined node operation character. A * algorithm characteristics: A * algorithm is theoretically optimal time, but it also has disadvantages: 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 ponents OpenList, CloseList and valuation functions. 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 基于 A*算法的路徑尋找 III 目 錄 引 言 .................................................................................................................................... 1 1 研究背景和意義 .................................................................................................................... 2 背景及意義 ................................................................................................................. 2 本文研究內(nèi)容 ............................................................................................................. 3 2 路徑尋址和開發(fā)工具 ............................................................................................................ 4 路徑尋址的方法介紹 ................................................................................................. 4 模擬 .................................................................................................................. 4 最短路徑問題 .................................................................................................. 4 Dijkstra 算法 ..................................................................................................... 4 開 發(fā)工具 —— Eclipse ................................................................................................. 5 3 基于搜索算法的機器人路徑尋址 ........................................................................................ 7 廣度優(yōu)先算法（ BFS） .............................................................................................. 7 深度優(yōu)先搜尋（ DFS） .............................................................................................. 7 A*算法 ......................................................................................................................... 7 4 A*算法仿真系統(tǒng)設(shè)計 .......................................................................................................... 11 路徑尋址系統(tǒng)概述 .................................................................................................... 11 對用戶界面進行模塊設(shè)計 ....................................................................................... 11 主窗口界面 .................................................................................................... 11 繪畫過程代碼 ................................................................................................ 11 工具欄代碼 .................................................................................................... 12 按鈕代碼 ........................................................................................................ 13 狀態(tài)欄代碼 .................................................................................................... 14 對算法實現(xiàn)進行設(shè)計 ............................................................................................... 14 路徑組成函數(shù)和搜索邏輯設(shè)計 .................................................................... 14 節(jié)點判斷函數(shù)及屬性函數(shù)的設(shè)計 ................................................................ 16 5 仿真實驗結(jié)果的比較及界面 UI ......................................................................................... 18 SWING 技術(shù)介紹 ...................................................................................................... 18 仿真實驗及結(jié)果比較 ............................................................................................... 18 g(n)的改變對結(jié)果的變化 .............................................................................. 18 基于 h(n)的變化對結(jié)果的影響 .................................................................... 24 6 結(jié)束語 .................................................................................................................................. 30 總結(jié) ........................................................................................................................... 30 基于 A*算法的路徑尋找 IV 實驗存在的問題和改善 ...............................................