资源描述：
《人工智能实验报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、昆明理工大学信息工程与自动化学院学生上机实验报告（2012—2013学年第1学期）课程名称：人工智能导论实验地点：2012年11月13日年级、专业、班测控技术与仪器学号姓名成绩实验项目名称状态空间搜索策略研究----八数码问题求解指导教师教师评语教师签名：年月日一、实验问题八数码问题：在3×3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。初始状态:目标状态:123805746123804765请任选一种盲目搜索算法（深度优先搜索或宽度优先搜索）或任选一种启发式搜索方法（
2、A算法或A*算法）编程求解八数码问题（初始状态任选），并对实验结果进行分析,得出结论。二、实验目的1.熟悉人工智能系统中的问题求解过程；2.熟悉状态空间的盲目搜索和启发式搜索算法的应用；3.熟悉对八数码问题的建模、求解及编程语言的应用。三、实验原理常用的状态空间搜索有深度优先和广度优先。广度优先是从初始状态一层一层向下找，直到找到目标为止。深度优先是按照一定的顺序前查找完一个分支，再查找另一个分支，以至找到目标为止。广度和深度优先搜索有一个很大的缺陷就是他们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很合适的算法，可是当状态空间十分大，且不预测的情况下就不可取了。他的效率实在太
3、低，甚至不可完成。由于八数码问题状态空间共有9!个状态，对于八数码问题如果选定了初始状态和目标状态，有9!/2个状态要搜索，考虑到时间和空间的限制，在这里采用A*算法作为搜索策略。在这里就要用到启发式搜索 启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无畏的搜索路径，提到了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。启发中的估价是用估价函数表示的，如：f(n)=g(n)+h(n) 其中f(n)是节点n的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是从
4、n到目标节点最佳路径的估计代价。在此八数码问题中，显然g(n)就是从初始状态变换到当前状态所移动的步数，估计函数f(n)我们就可采用当前状态各个数字牌不在目标状态未知的个数，即错位数。四、程序框图算法流程如下：开始读入棋局初始状态否o是否可解是o初始状态加入open表在open表中找到评价值最小的节点，作为当前结点是o是目标节点否o扩展新状态，把不重复的新状态加入open表中当前结点从open表移除输出结果结束五、实验结果及分析{1,2,3,8,0,5,7,4,6}123805746A(4)123806745123850746123845706B(3)C(5)D(5)123850764123
5、856740123845760E(2)F(4)G(4)123840765H(0)OPENCLOSEDAB,C,DAE,C,DB,AH,C,DE,B,AH,E,B,A六、结论A*算法中，限制h(x)<=h*(x)的原因是是为了保证取得最优解。通过分析证明，如果问题存在最优解，则这样的限制就可保证能找到最优解。虽然这个限制可能产生无用搜索。实际上，当某一节点x的h(x)>h*(x)，则该节点就可能失去优先扩展的机会，因而导致得不到最优解。八数码问题是一个很难求解的问题，因为他需要用到复杂的C++程序编程知识，而自己在这个环节的运用上总体来说相对薄弱，所以开始时感觉很迷茫，无从下手，但是后来经过对
6、所学知识的回顾和复习，对此问题终于找到了出口。这次实验让我深刻意识到学习C++程序编程的重要性，如果学好了这门课程，那么在以后的学习中将会轻松很多，同时让我找到了自身存在的不足，朝着这个方向努力的改善和提高自己。七、源程序及注释#include"Stdio.h"#include"Conio.h"#include"stdlib.h"#include"math.h"voidCopy_node(structnode*p1,structnode*p2);voidCalculate_f(intdeepth,structnode*p);voidAdd_to_open(structnode*p);void
7、Add_to_closed(structnode*p);voidRemove_p(structnode*name,structnode*p);intTest_A_B(structnode*p1,structnode*p2);structnode*Solution_Astar(structnode*p);voidExpand_n(structnode*p);structnode*Search_A(structn
