昆明理工大学人工智能导论实验报告模板-2013(新)

《昆明理工大学人工智能导论实验报告模板-2013(新)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、昆明理工大学信息工程与自动化学院学生实验报告（2013——2014学年第一学期）课程名称：人工智能导论开课实验室：信自楼234室2013年10月29日年级、专业、班2011级测控专业学号201110402137姓名陈文武成绩实验项目名称状态空间搜索实验—八数码问题求解指导教师教师评语该同学是否了解实验原理：A.了解□B.基本了解□C.不了解□该同学的实验能力：A.强□B.中等□C.差□该同学的实验是否达到要求：A.达到□B.基本达到□C.未达到□实验报告是否规范：A.规范□B.基本规范□C.不规范□实验过程是否详细记录：A.详细□B.一般□C.没

2、有□教师签名：年月日13——《人工智能导论》测控陈文武——目录一、实验问题2二、实验目的2三、实验原理2A搜索的原理：2估价函数：2重要程序分析：3四、程序框图4五、实验结果及分析5随机检验15随机检验26随机检验37随机检验47六、结论9七、源程序及注释1013——《人工智能导论》测控陈文武——一、实验问题八数码问题的求解，及程序设计。具体要求如下在3*3的方格中的棋盘中任意摆放1到8个自然数和一个空格，其初始状态如下：13——《人工智能导论》测控陈文武——254307186a初始状态123804765b目标状态13——《人工智能导论》测控陈文

3、武——请选择一种盲目搜索的算法或选择一种启发式搜索的算法编程求解八数码问题，初始状态任选，并对使用进行合理分析做出合理结果。二、实验目的1、熟悉人工智能系统中的问题求解过程；2、熟悉状态空间的满目搜索和启发式搜索算法的运用；3、熟悉对八码数问题的建模、求解及编程语言的运用；三、实验原理经过分析，8数码问题中可采用的搜速策略共有：1.广度优先搜索2.深度优先搜索2.有界深度优先搜索4.最好优先搜索5.局部择优搜索一共五种。其中，广度优先搜索法是可采纳的，有界深度优先搜索法是不完备的，最好优先和局部择优搜索法是启发式搜索法。在实验时，我采用了启发式搜

4、索中的最好优先来实现。启发式搜索算法有A算法、A*算法。本次实验采用了A算法得到结果。A搜索的原理：A算法搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。估价函数：计算一个节点的估价函数，可以分成两个部分：13——《人工智能导论》测控陈文武——1、已经付出的代价（起始节点到当前节点）；2、将要付出的代价（当前节点到目标节点）。节点n的估价函数定义为从初始节点、经过n、到达目标节

5、点的路径的最小代价的估计值，即=+。是从初始节点到达当前节点n的实际代价；是从节点n到目标节点的最佳路径的估计代价，体现出搜索过程中采用的启发式信息（背景知识），称之为启发函数。所占的比重越大，越趋向于宽度优先或等代价搜索；反之，的比重越大，表示启发性能就越强。本实验中我们使用函数，其值是节点n与目标状态节点相比较，每个错位棋牌在假设不受阻拦的情况下，移动到目标状态相应位置所需走步（移动次数）的总和。显然比更接近于，因为不仅考虑了错位因素，还考虑了错位的距离。重要程序分析：1.结点状态我采用了structNode数据类型typedefstruct

6、_Node{intdigit[ROW][COL];intdist;//distancebetweenonestateandthedestination一个表和目的表的距离intdep;//thedepthofnode深度//Sothecommentfunction=dist+dep.估价函数值intindex;//pointtothelocationofparent父节点的位置}Node;2.发生器函数定义的发生器函数由以下的四种操作组成：(1)将当前状态的空格上移Nodenode_up;Assign(node_up,index);//向上扩展的

7、节点intdist_up=MAXDISTANCE;(2)将当前状态的空格下移Nodenode_down;Assign(node_down,index);//向下扩展的节点intdist_down=MAXDISTANCE;(3)将当前状态的空格左移Nodenode_left;Assign(node_left,index);//向左扩展的节点13——《人工智能导论》测控陈文武——intdist_left=MAXDISTANCE;(4)将当前状态的空格右移Nodenode_right;Assign(node_right,index);//向右扩展的节点

8、intdist_right=MAXDISTANCE;通过定义结点状态和发生器函数，就解决了8数码问题的隐式图的生成问题。接下来就是搜索了