(人工智能导论.doc

昆明理工大学信息工程与自动化学院学生实验报告 （ 2014—— 2015 学年 第 一 学期 ） 课程名称：人工智能导论 开课实验室：信自楼室 2014年 9月30日 年级、专业、班 学号 姓名 成绩 实验项目 名称 状态空间搜索实验—八数码问题求解 指导 教师 教师评语 该同学是否了解实验原理： A.了解□ B.基本了解□ C.不了解□ 该同学的实验能力： A.强 □ B.中等 □ C.差 □ 该同学的实验是否达到要求 ： A.达到□ B.基本达到□ C.未达到□实验报告是否规范： A.规范□ B.基本规范□ C.不规范□实验过程是否详细记录： A.详细□ B.一般 □ C.没有 □ 教师签名： 年 月 日 一、实验内容和要求 八数码问题：在3×3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。 例如： 2 8 3 1 2 3 1 6 4 8 4 7 5 0 7 6 5 (a) 初始状态 (b) 目标状态 图1 八数码问题示意图 请任选一种盲目搜索算法（广度优先搜索或深度优先搜索）或任选一种启发式搜索方法（全局择优搜索，加权状态图搜索，A 算法或 A* 算法）编程求解八数码问题（初始状态任选）。选择一个初始状态，画出搜索树，填写相应的OPEN表和CLOSED表，给出解路径，对实验结果进行分析总结，得出结论。 二、实验目的 1. 熟悉人工智能系统中的问题求解过程； 2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用； 3. 熟悉对八数码问题的建模、求解及编程语言的应用。 三、实验算法 把起始状态添加到开启列表。 重复如下工作： a) 寻找开启列表中f值最低的节点，我们称它为BESTNOE b) 把它切换到关闭列表中。 c) 对相邻的4个节点中的每一个 *如果它不在开启列表，也不在关闭列表，把它添加到开启列表中。把BESTNODE作为这一节点的父节点。记录这一节点的f和g值 *如果它已在开启或关闭列表中，用g值为参考检查新的路径是否更好。更低的g值意味着更好的路径。如果这样，就把这一节点的父节点改为BESTNODE，并且重新计算这一节点的f和g值，如果保持开启列表的f值排序，改变之后需要重新对开启列表排序。 　　d) 停止 　　 把目标节点添加到关闭列表，这时候路径被找到，或者没有找到路径，开启列表已经空了，这时候路径不存在。 保存路径。从目标节点开始，沿着每一节点的父节点移动直到回到起始节点。这就是求得的路径。 数据结构 采用结构体来保存八数码的状态、f和g的值以及该节点的父节点； struct Node{ int s[3][3];//保存八数码状态，0代表空格 int f,g;//启发函数中的f和g值 struct Node * next; struct Node *previous;//保存其父节点 }; 四、程序框图 A*算法流程图,如下图 五、实验结果及分析 六、结论 　　　通过本次实验，我更加深入的了解了A*算法、启发函数以及搜索方法。使用A*算法，也要懂得构建估价函数，不同的估计函数对实验结果影响很大。比如该实验，对于f(n)的考虑最简单的便是比较每个状态与目标状态相比错位的牌数。这个启发意味着如果其他条件相同，那么错位的牌数最少的状态可能最接近目标状态。然而这个启发没有使用从棋盘格局中可以得到的所有信息，因为它没有把牌必要的移动距离纳入考虑。一个“更好一点”的启发是对错位的牌必须要移动的距离求和，为了达到这个目的，每张牌必须要移动的每个方格算为一个距离单位。这两种启发都存在一种不足，就是没有认识到点到牌的难度。也就是说，如果两张牌是彼此相邻的，而且目标是要求互相颠倒它们的位置，那么要把它们放到适当的位置需要远不止两次的移动，因为各张牌必须相互绕来绕去。这个实验中，我采取的是把距离加上深度，来作为估价函数值。除此之外，还有很多细节都可以影响实验，这里就不一一列举了。 七、源程序及注释 //----------------------------------------------------------------------------- //代码：利用A*算法求解八数码问题。 //八数码问题的启发函数设计为：f(n)=d(n)+p(n),其中A*算法中的g(n)根据具体情况设计为d(n