昆明理工大学人工智能导论实验报告模板.doc

PAGE PAGE 1 —— 《人工智能导论》 测控 陈文武 —— 昆明理工大学信息工程与自动化学院学生实验报告 （ 2013—— 2014 学年 第 一 学期 ） 课程名称：人工智能导论 开课实验室：信自楼234室 2013 年级、专业、班 2011级 测控专业 学号 201110402137 姓名 陈文武 成绩 实验项目 名称 状态空间搜索实验—八数码问题求解 指导 教师 教师评语 该同学是否了解实验原理： A.了解□ B.基本了解□ C.不了解□ 该同学的实验能力： A.强 □ B.中等 □ C.差 □ 该同学的实验是否达到要求 ： A.达到□ B.基本达到□ C.未达到□ 实验报告是否规范： A.规范□ B.基本规范□ C.不规范□ 实验过程是否详细记录： A.详细□ B.一般 □ C.没有 □ 教师签名： 年 月 日  目 录 TOC \o "1-3" \h \z \u 一、实验问题 2 二、实验目的 2 三、实验原理 2 A搜索的原理： 2 估价函数： 2 重要程序分析： 3 四、程序框图 4 五、实验结果及分析 5 随机检验1 5 随机检验2 6 随机检验3 7 随机检验4 7 六、结论 9 七、源程序及注释 10 一、实验问题 八数码问题的求解，及程序设计。具体要求如下 在3*3的方格中的棋盘中任意摆放1到8个自然数和一个空格，其初始状态如下： 2 5 4 3 0 7 1 8 6 a初始状态 1 2 3 8 0 4 7 6 5 b目标状态 请选择一种盲目搜索的算法或选择一种启发式搜索的算法编程求解八数码问题，初始状态任选，并对使用进行合理分析做出合理结果。 二、实验目的 1、熟悉人工智能系统中的问题求解过程； 2、熟悉状态空间的满目搜索和启发式搜索算法的运用； 3、熟悉对八码数问题的建模、求解及编程语言的运用； 三、实验原理 经过分析，8数码问题中可采用的搜速策略共有： 1.广度优先搜索 2.深度优先搜索 2.有界深度优先搜索 4.最好优先搜索 5.局部择优搜索 一共五种。其中，广度优先搜索法是可采纳的，有界深度优先搜索法是不完备的，最好优先和局部择优搜索法是启发式搜索法。在实验时，我采用了启发式搜索中的最好优先来实现。启发式搜索算法有A算法、A*算法。本次实验采用了A算法得到结果。 A搜索的原理： A算法搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。 估价函数： 计算一个节点的估价函数，可以分成两个部分： 已经付出的代价（起始节点到当前节点）； 将要付出的代价（当前节点到目标节点）。 节点n的估价函数定义为从初始节点、经过n、到达目标节点的路径的最小代价的估计值，即 = + 。 是从初始节点到达当前节点n的实际代价； 是从节点n到目标节点的最佳路径的估计代价，体现出搜索过程中采用的启发式信息（背景知识），称之为启发函数。 所占的比重越大，越趋向于宽度优先或等代价搜索；反之，的比重越大，表示启发性能就越强。 本实验中我们使用函数，其值是节点n与目标状态节点相比较，每个错位棋牌在假设不受阻拦的情况下，移动到目标状态相应位置所需走步（移动次数）的总和。显然比更接近于，因为不仅考虑了错位因素，还考虑了错位的距离。 重要程序分析： 1.结点状态 我采用了struct Node数据类型 typedef struct _Node{ int digit[ROW][COL]; int dist; // distance between one state and the destination一个表和目的表的距离 int dep; // the depth of node深度 // So the comment function = dist + dep.估价函数值 int index; // point to the location of parent父节点的位置 } Node; 2.发生器函数 定义的发生器函数由以下的四种操作组成： (1)将当前状态的空格上移 Node node_up; Assign(node_up, index);//向上扩展的节点 int dist_up = MAXDISTANCE; (2)将当前状态的空格下移 Node node_down; Assign(node_down,