八数码实验报告 人工智能课设报告

《八数码实验报告 人工智能课设报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2402070333张辉学生实验报告实验课名称：人工智能实验名称:八数码专业名称：计算机科学与技术班级：学号：学生姓名：教师姓名：2010年10月20日2402070333张辉一．实验内容用OPEN表和CLOSED表解决搜索问题。二．实验题目采用启发式算法（如A*算法）求解八数码问题。三．实验要求1.必须使用OPEN表和CLOSED表。2.明确给出问题描述。系统初始状态。目标状态和启发式函数。3.除了初始状态以外，至少搜索四层。4.给出解路径（解图）。四．实验过程①问题：初始状态到目标状态是否可解如何判断？答：实验过程自己给出的初始状态使用

2、A*算法求解，并不是所有的初始状态都可解到达目标状态。因为八数码问题其实是0~9的一个排列，而排列有奇排列和偶排列，从奇排列不能转化为偶排列或者相反。例如：函数f(s)表示s前比s小的数字的数目（s不等于0）.13428657则f(7)=6,f(5)=4,f(6)=4,f(8)=4,f(2)=1,f(4)=2,f(3)=1,f(1)=0当f(a8)+f(a7)+……+f(a1)为偶数时才能重排成，所以嘛,上面那个有解的.②问题描述：在3X3的九宫格棋盘上，摆有8个将牌，每一个将牌都刻有1~8数码中的某一个数码。棋盘中留有一个空格，允许周围的

3、某一个将牌向空格移动，这样通过移动将牌就可以不断地改变将牌的布局。这种游戏的求解的问题是：给定一种处世的将牌布局或结构和一个目标的布局，问如何移动将牌，实现从从初始状态到目标状态的转变。下面给出初始状态和目标状态：28316475初始状态：12384765目标状态：评价函数f(n)形式为：f(n)=g(n)+h(n),其中g(n)是节点所处的深度，h(n)是启发式函数，这里启发式函数h(n)表示“不在位”的将牌个数，这时f(n)可估计出通向目标结点的希望的程度。注意：移动规则为左-à上à右à下。③搜索过程：如下图-1为八数码问题的搜索树：2

4、402070333张辉S(4)图-128S0316475S1S3283164752831647528314765S2A(6)B(4)C(6)S4S628314765S52318476528314765D(5)F(6)E(5)S7S8S9S108G(6)321476528H(7)3714652I(5)31847652318J(7)476512384765S11K(5)S131238476512378465S12L(5)M(7)表1搜索过程的OPEN表和CLOSED表OPEN表CLOSED表初始化（S(4)）（）第1循环结束（B(4),A(6)

5、,C(6)）（S(4)）第2循环结束（D(5),E(5),A(6),C(6),F(6)）（S(4),B(4)）第3循环结束（E(5),A(6),C(6),F(6),G(6),H(7)）（S(4),B(4),D(5)）第4循环结束（I(5),A(6),C(6),F(6),G(6),H(7),J(7)）（S(4),B(4),D(5),E(5)）第5循环结束（K(5),A(6),C(6),F(6),G(6),H(7),J(7)）（S(4),B(4),D(5),E(5),I(5)）第6循环结束（L(5),A(6),C(6),F(6),G(6),H(

6、7),J(7),M(7)）（S(4),B(4),D(5),E(5),I(5),K(5)）第7循环结束成功退出2402070333张辉因此可得解路径：S(4)àB(4)àD(5)àE(5)àI(5)àK(5)àL(5).④得到OPEN表和CLOSED表OPEN表结点父结点编号评价函数f(n)S04S106S204S306S415S515S616S726S827S935S1037S1145S1255S1357CLOSED表编号结点父结点编号评价函数f(n)0S041S2042S4153S5154S9355S11456S1255结论：由以上分析,

7、可以从CLOSED表中可知从初始状态到结束状态的搜索路径为：S0àS2àS5àS9àS11àS12.五、实验体会通过本次实验又将课本内容熟悉了一遍，而且通过互联网了解了更多的关于八数码问题，如读过网上用VC++编写八数码问题的源代码，虽然理解不是很深，但基本思想也是有所体会；同时也对广度优先搜索算法，深度优先算法，双向广度优先算法及A*算法有更深的掌握。