文档介绍：启发式搜索实验实验三搜索推理技术启发式搜索算法—A*算法1(实验目的,1,了解搜索推理的相关技术,,2,掌握启发式搜索算法或者基于规则推理的分析方法。2(实验内容,2个实验内容可以选择1个实现,,1,启发式搜索算法。熟悉和掌握启发式搜索的定义、估价函数和算法过程~并求解博弈问题~理解求解流程和搜索顺序,,2,产生式系统实验。熟悉和掌握产生式系统的运行机制~掌握基于规则推理的基本方法。3(实验报告要求,1,简述实验原理及方法~并请给出程序设计流程图。,A-Star)算法是一种静态路网中求解最短路最有效的直接搜索方法。公式表示为:f(n)=g(n)+h(n),其中f(n)是从初始点经由节点n到目标点的估价函数~g(n)是在状态空间中从初始节点到n节点的实际代价~h(n)是从n到目标节点最佳路径的估计代价。保证找到最短路径,最优解的,条件~关键在于估价函数h(n)的选取:估价值h(n)<=n到目标节点的距离实际值~这种情况下~搜索的点数多~搜索范围大~效率低。但能得到最优解。并且如果h(n)=d(n)~即距离估计h(n)等于最短距离~那么搜索将严格沿着最短路径进行~此时的搜索效率是最高的。然后我们通过图文结合的形式来解释下~如下图:图中有这么几个要点先需要了解:1、类似迷宫图~分开始节点(start)、障碍物、结束节点(end)~我们需要从start节点探寻一条到end节点的路线2、对于探寻的每一步~都会以当前节点为基点~扫描其相邻的八个节点3、计算当前节点与start节点及到end的距离4、计算出最短路径如果明白了上面的场景描述~下面就可以进行分析了。在A*算法中~核心思想是一个公式~上面已经提到过:f(n)=g(n)+h(n),2,源程序清单:.;;;;.;lassItxxzAstar{//开始节点privatePointstartPoint=null;//当前节点privatePointendPoint=null;//结束节点privatePointcurrentPoint=null;//最短距离坐标节点privatePointshortestFPoint=null;//迷宫数组地图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[][]mazePoint=null;//开启队列,用于存放待处理的节点Queue<Point>openQueue=null;//关闭队列,用于存放已经处理过的节点Queue<Point>closedQueue=null;//起始节点到某个节点的距离int[][]FList=null;//某个节点到目的节点的距离int[][]GList=null;//起始节点经过某个节点到目的节点的距离int[][]HList=null;/***构造函数*****@parammaze*迷宫图****@paramstartPoint*起始节点****@paramendPoint*结束节点*/publicItxxzAstar(Point[][]mazePoint,PointstartPoint,PointendPoint){=mazePoint;=startPoint;=endPoint;openQueue=newLinkedList<Point>();(startPoint);closedQueue=newLinkedList<Point>();FList=newint[][mazePoint[0].length];GList=newint[][mazePoint[0].length];HList=newint[][mazePoint[0].length];for(inti=0;i<;i++){for(intj=0;j<mazePoint[0].length;j++){FList[i][j]=;GList[i][j]=;HList[i][j]=