資源描述:
《啟發(fā)式搜索實驗》由會員上傳分享,免費在線閱讀,更多相關內(nèi)容在行業(yè)資料-天天文庫。
1、實驗三搜索推理技術啟發(fā)式搜索算法—A*算法1.實驗目的(1)了解搜索推理的相關技術;(2)掌握啟發(fā)式搜索算法或者基于規(guī)則推理的分析方法。2.實驗內(nèi)容(2個實驗內(nèi)容可以選擇1個實現(xiàn))(1)啟發(fā)式搜索算法。熟悉和掌握啟發(fā)式搜索的定義、估價函數(shù)和算法過程,并求解博弈問題,理解求解流程和搜索順序;(2)產(chǎn)生式系統(tǒng)實驗。熟悉和掌握產(chǎn)生式系統(tǒng)的運行機制,掌握基于規(guī)則推理的基本方法。3.實驗報告要求(1)簡述實驗原理及方法,并請給出程序設計流程圖。(A-Star)算法是一種靜態(tài)路網(wǎng)中求解最短路最有效的直接搜索方法。公式表示為:f(n)=g(n)+h(n),其中f(n)是從初始點經(jīng)由節(jié)點n到目標點的估價函數(shù)
2、,g(n)是在狀態(tài)空間中從初始節(jié)點到n節(jié)點的實際代價,h(n)是從n到目標節(jié)點最佳路徑的估計代價。保證找到最短路徑(最優(yōu)解的)條件,關鍵在于估價函數(shù)h(n)的選取:估價值h(n)<=n到目標節(jié)點的距離實際值,這種情況下,搜索的點數(shù)多,搜索范圍大,效率低。但能得到最優(yōu)解。并且如果h(n)=d(n),即距離估計h(n)等于最短距離,那么搜索將嚴格沿著最短路徑進行,此時的搜索效率是最高的。然后我們通過圖文結(jié)合的形式來解釋下,如下圖:圖中有這么幾個要點先需要了解:1、類似迷宮圖,分開始節(jié)點(start)、障礙物、結(jié)束節(jié)點(end),我們需要從start節(jié)點探尋一條到end節(jié)點的路線2、對于探尋的每一
3、步,都會以當前節(jié)點為基點,掃描其相鄰的八個節(jié)點3、計算當前節(jié)點與start節(jié)點及到end的距離4、計算出最短路徑如果明白了上面的場景描述,下面就可以進行分析了。在A*算法中,核心思想是一個公式,上面已經(jīng)提到過:f(n)=g(n)+h(n)(2)源程序清單:packagecom.itxxz.ui.suanfa.astar;importjava.util.Iterator;importjava.util.LinkedList;importjava.util.Queue;importcom.itxxz.ui.suanfa.astar.Point;publicclassItxxzAstar{//開始
4、節(jié)點privatePointstartPoint=null;//當前節(jié)點privatePointendPoint=null;//結(jié)束節(jié)點privatePointcurrentPoint=null;//最短距離坐標節(jié)點privatePointshortestFPoint=null;//迷宮數(shù)組地圖privatestaticfinalint[][]mazeArray={{1,0,0,0,0},{1,0,2,0,0},{1,0,0,0,1},{1,0,0,0,0},{1,1,1,1,0},{1,0,0,0,0},{3,0,1,1,1}};//迷宮坐標對象privatePoint[][]mazePo
5、int=null;//開啟隊列,用于存放待處理的節(jié)點QueueopenQueue=null;//關閉隊列,用于存放已經(jīng)處理過的節(jié)點QueueclosedQueue=null;//起始節(jié)點到某個節(jié)點的距離int[][]FList=null;//某個節(jié)點到目的節(jié)點的距離int[][]GList=null;//起始節(jié)點經(jīng)過某個節(jié)點到目的節(jié)點的距離int[][]HList=null;/***構(gòu)造函數(shù)**@parammaze*迷宮圖*@paramstartPoint*起始節(jié)點*@paramendPoint*結(jié)束節(jié)點*/publicItxxzAstar(Point[][]ma
6、zePoint,PointstartPoint,PointendPoint){this.mazePoint=mazePoint;this.startPoint=startPoint;this.endPoint=endPoint;openQueue=newLinkedList();openQueue.offer(startPoint);closedQueue=newLinkedList();FList=newint[mazePoint.length][mazePoint[0].length];GList=newint[mazePoint.length][mazePo
7、int[0].length];HList=newint[mazePoint.length][mazePoint[0].length];for(inti=0;i