启发式搜索实验.doc

启发式搜索实验.doc

ID:48924080

大小:157.50 KB

页数:11页

时间:2020-02-07

启发式搜索实验.doc_第1页
启发式搜索实验.doc_第2页
启发式搜索实验.doc_第3页
启发式搜索实验.doc_第4页
启发式搜索实验.doc_第5页
资源描述:

《启发式搜索实验.doc》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、.实验三搜索推理技术启发式搜索算法—A*算法1.实验目的(1)了解搜索推理的相关技术;(2)掌握启发式搜索算法或者基于规则推理的分析方法。2.实验内容(2个实验内容可以选择1个实现)(1)启发式搜索算法。熟悉和掌握启发式搜索的定义、估价函数和算法过程,并求解博弈问题,理解求解流程和搜索顺序;(2)产生式系统实验。熟悉和掌握产生式系统的运行机制,掌握基于规则推理的基本方法。3.实验报告要求(1)简述实验原理及方法,并请给出程序设计流程图。(A-Star)算法是一种静态路网中求解最短路最有效的直接搜索方法。公式表示为:f(n)=g(n)+h(

2、n),其中f(n)是从初始点经由节点n到目标点的估价函数,g(n)是在状态空间中从初始节点到n节点的实际代价,h(n)是从n到目标节点最佳路径的估计代价。保证找到最短路径(最优解的)条件,关键在于估价函数h(n)的选取:估价值h(n)<=n到目标节点的距离实际值,这种情况下,搜索的点数多,搜索范围大,效率低。但能得到最优解。并且如果h(n)=d(n),即距离估计h(n)等于最短距离,那么搜索将严格沿着最短路径进行,..此时的搜索效率是最高的。然后我们通过图文结合的形式来解释下,如下图:图中有这么几个要点先需要了解:1、类似迷宫图,分开始节

3、点(start)、障碍物、结束节点(end),我们需要从start节点探寻一条到end节点的路线2、对于探寻的每一步,都会以当前节点为基点,扫描其相邻的八个节点3、计算当前节点与start节点及到end的距离4、计算出最短路径如果明白了上面的场景描述,下面就可以进行分析了。在A*算法中,核心思想是一个公式,上面已经提到过:f(n)=g(n)+h(n)(2)源程序清单:..packagecom.itxxz.ui.suanfa.astar;importjava.util.Iterator;importjava.util.LinkedList;

4、importjava.util.Queue;importcom.itxxz.ui.suanfa.astar.Point;publicclassItxxzAstar{//开始节点privatePointstartPoint=null;//当前节点privatePointendPoint=null;//结束节点privatePointcurrentPoint=null;//最短距离坐标节点privatePointshortestFPoint=null;//迷宫数组地图privatestaticfinalint[][]mazeArray={{1

5、,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[][]mazePoint=null;//开启队列,用于存放待处理的节点QueueopenQueue=null;//关闭队列,用于存放已经处理过的节点QueueclosedQueue=null;//起始节点到某个节点的距离int[][]FList=null;//某个节点到目的节点的距离int[][]GList

6、=null;//起始节点经过某个节点到目的节点的距离int[][]HList=null;/**..*构造函数**@parammaze*迷宫图*@paramstartPoint*起始节点*@paramendPoint*结束节点*/publicItxxzAstar(Point[][]mazePoint,PointstartPoint,PointendPoint){this.mazePoint=mazePoint;this.startPoint=startPoint;this.endPoint=endPoint;openQueue=newLin

7、kedList();openQueue.offer(startPoint);closedQueue=newLinkedList();FList=newint[mazePoint.length][mazePoint[0].length];GList=newint[mazePoint.length][mazePoint[0].length];HList=newint[mazePoint.length][mazePoint[0].length];for(inti=0;i

8、or(intj=0;j

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。