《(完整word版)迷宫寻路实验报告.doc》由会员分享，可在线阅读，更多相关《(完整word版)迷宫寻路实验报告.doc（4页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、人工智能实验报告实验三 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到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低，但能得到最优解。如果估价值大于实
2、际值，搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。三、实验内容： 1、参考实验系统给出的迷宫求解核心代码，观察求解过程与思路。 2、画出用A*算法求解迷宫最短路径的流程图。 3、尝试改变启发式算法提高迷宫搜索速度。 4、分析不同启发式函数对迷宫寻路速度的提升效果。四、实验报告要求： 1、画出A*算法求解迷宫最短路径问题的流程图。 2、试分析不同启发式函数对迷宫寻路求解的速度提升效果。: gn = 0;fn = abs(Ei-ci)+abs(Ej-cj); fn1 = abs(Ei-ni)+abs(Ej-nj)+gn1;: gn = 0;fn = 0;fn1 = 0;: gn = 0
3、;fn = 0; fn1 = abs(Ei-ni)*abs(Ej-nj) + abs(Ej-nj)*abs(Ej-nj) +gn1;调节g(n)和h(n)函数影响搜索策略。使启发式算法效率提高。 3、分析启发式函数中g(n)和h(n)求解方法不同对A*算法的影响。 g(n)和h(n)求解方法不同将直接影响A*算法的效率，好的解决方法不仅能够使路径变短，而且在求解过程中所搜索和产生的节点数也会尽量的少；而比较差的解决方法则可能导致所找到的路径未必是最短的，尽管它在求解过程中所搜索和产生的节点数也比较少。五、实验心得与体会 A*算法作为启发式算法的重要组成部分在实际应用中有很大的作用。通过这次实验，我对g(n)和h(n)这两个函数对于A*算法的影响有了更进一步的了解，同时也认识到编写好的g(n)和h(n)对于A*算法的性能提高是十分关键的。