迷宫寻路实验报告

迷宫寻路实验报告A*算法实验II一、实验目的:熟悉和掌握A*算法实现迷宫寻路功能,要求掌握启发式函数的编写以及各类启发式函数效果的比较。二、实验原理:A*(A-Star)算法是一种静态路网中求解最短路最有效的方法。公式表示为:f(n)=g(n)+h(n),其中f(n)是节点n从初始点到目标点的估价函数,g(n)是在状态空间中从初始节点到n节点的实际代价,h(n)是从n到目标节点最佳路径的估计代价。保证找到最短路径(最优解的)条件,关键在于估价函数h(n)的选取:估价值h(n)小于等于n到目标节点的距离实际值,这种情况下,搜索的点数多,搜索范围大,效率低,但能得到最优解。如果估价值大于实际值,搜索的点数少,搜索范围小,效率高,但不能保证得到最优解。三、实验内容:1、参考实验系统给出的迷宫求解核心代码,观察求解过程与思路。2、画出用A*算法求解迷宫最短路径的流程图。3、尝试改变启发式算法提高迷宫搜索速度。4、分析不同启发式函数对迷宫寻路速度的提升效果。实验报告要求:1、画出A*算法求解迷宫最短路径问题的流程图。1.流程图否,失败是是,输出路径否2.fn1=abs(Ei-ni)+abs(Ej-nj)+gn1;fn1=abs(Ei-ni)*abs(Ej-nj)+abs(Ej-nj)*abs(Ej-nj)+gn1;3.分析估价函数中g(n)和h(n)求解方法不同对A*算法的影响估价函数g(n)和h(n)采用不同的求解方式会直接影响A*算法的效率,且两者之间互有联系,调整两种估价函数的会使搜索策略更加完善有效率。五、实验心得与体会通过这次实验,我对估价函数有了更进一步的了解,同时也认识到编写好的估价函数对于A*算法的性能提高是十分关键的,可以让A*算法更快的解决路径问题。