《人工智能实验报告》word版.docx

中南大学信息科学与工程学院人工智能实验报告学生姓名 谢小炜 学 号 0909080926指导教师 黄芳专业班级 计科0802时 间 2011年11月搜索策略实验群一、 实验目的：熟悉和掌握启发式搜索的定义、估价函数和算法过程，并 利用A*算法求解N数码难题，理解求解流程和搜索顺序。二、 实验原理:A*算法是一种有序搜索算法，其特点在于对估价函数的定义上。对于一般的有序搜索，总是选择f值最小的节点作为扩展节点。因此，f是根据需要找到一条最小代价路径 的观点来估算节点的，所以，可考虑每个节点n的估价函数值为两个分 量：从起始节点到节点n的代价以及从节点n到 达目标节点的代价。三、 实验条件：搜索策略可视化实验环境:下图是该环境运行中的一个画面.四、 实验内容：1、 分别以各种搜索算法为例演示搜索过程。2、 分析各种算法中的OPEN表CLOSE表的生成过程。3、 分析估价函数对搜索算法的影响。4、 分析估价函数对搜索算法 的影响。5、 分析某种启发式搜索算法 的特点。五、 实验步骤：1、开始演示。进入搜索策略演示程序，可从多种不同搜索算法选择装载相关源文件。2、选择不同的搜索算法，点 击“autosearch” 观察搜索过程。3、设置不同属性，观察搜索 过程的变化。4、观察运行过程和搜索顺序，理解启发式搜索的原理。5、算法流程的任一时刻的相 关状态,以算法流程高亮、open表、close表、节点静态图、当前扩展节点移动图等5种形式在按钮上方同步显示,便于深入学习理解搜索算 法。6、根据程序运行过程画出搜 索算法框图。7、若要自己设计改进算法并运行，可参考帮助文件。六、 实验过程：1、进入实验环境，点击“file”，选择“Load Sample Graph” 2、选择“简单搜索树” 3、点击“Search Algorithms”，选择“Depth First” 4、接下来不断点击“Step”直到搜索结束，Open表与Close表的变化如下： OpenS, CloseNULL Open1, 2, CloseS Open3, 4, 2, Close1, S Open7, 4, 2, Close3, 1, S Open4, 2, Close7, 3, 1, S Open8， 2， Close4, 7, 3, 1, S Open2, Close8, 4, 7, 3, 1, S Open5, 6, Close2, 8, 4, 7, 3, 1, S Open9, G, 6, Close5, 2, 8, 4, 7, 3, 1, S OpenG, 6, Close9, 5, 2, 8, 4, 7, 3, 1, S 到达目标节点，搜索结束5、点击“Search Algorithms”，选择“A*”，点击左边的“Reset Search”，点“Search Options”后选上“Show Edge costs”与“Show Node Heuristics”,接下来不断点击“Step”直到搜索结束 OpenS, CloseNULL Open1, 2, CloseS Open5, 6, 1, Close2, S Open3, 4, 5, 6, Close1, 2, S Open9, G, 3, 4, 6, Close5, 1, 2, S Open10, 9, G, 3, 4, Close6, 5, 1, 2, S Open8, 10, 9, G, 3, Close4, 6, 5, 1, 2, S 到达目标节点，搜索结束七、A*算法流程图：开始将开始节点加入Open表否否是是程序结束，未能找到目标节点Open表是否为空将该节点加入Close表,并将该节点所有不在Close表中的邻接节点加入Open表从表中取出f(n)=g(n)+h(n)最大的节点程序结束,成功找到目标节点是否目标节点八、实验结论：从实验可以看出,A*算法搜索过程一般来说优于盲目搜索,而这又取决于估价函数的设计,一个好的估价函数可以大大地优化搜索过程,而一个坏的估价函数也可能导致极差的搜索附：搜索策略实验报告表:姓名 谢小炜年级 大四计科0802指导老师黄芳日期2011-10-2