啟發(fā)式搜索實驗

《啟發(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