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

2402070333 张辉学生实验报告实验课名称：人工智能 实验名 称 : 八数码专 业 名 称：计算机科学与技术班 级：学 号：学 生 姓 名： 教 师 姓 名： 2010 年 10 月 20日 一 实验内容 用OPEN表和CLOSED表解决搜索问题。二实验题目 采用启发式算法（如A*算法）求解八数码问题。三实验要求1. 必须使用OPEN表和CLOSED表。2. 明确给出问题描述。系统初始状态。目标状态和启发式函数。3. 除了初始状态以外，至少搜索四层。4. 给出解路径（解图）。四 实验过程 问题：初始状态到目标状态是否可解如何判断？ 答：实验过程自己给出的初始状态使用A*算法求解，并不是所有的初始状态都可解到达目标状态。因为八数码问题其实是09的一个排列，而排列有奇排列和偶排列，从奇排列不能转化为偶排列或者相反。例如： 函数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个将牌，每一个将牌都刻有18数码中的某一个数码。棋盘中留有一个空格，允许周围的某一个将牌向空格移动，这样通过移动将牌就可以不断地改变将牌的布局。这种游戏的求解的问题是：给定一种处世的将牌布局或结构和一个目标的布局，问如何移动将牌，实现从从初始状态到目标状态的转变。下面给出初始状态和目标状态：28316475初始状态：12384765 目标状态： 评价函数f(n)形式为：f(n)=g(n)+h(n),其中g(n)是节点所处的深度，h(n)是启发式函数，这里启发式函数h(n)表示“不在位”的将牌个数，这时f(n)可估计出通向目标结点的希望的程度。注意：移动规则为左-上右下。搜索过程：如下图-1为八数码问题的搜索树：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),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(7),J(7),M(7)）（S(4),B(4),D(5),E(5),I(5),K(5)）第7循环结束 成功退出因此可得解路径：S(4)B(4)D(5)E(5)I(5)K(5)L(5).得到OPEN表和CLOSED表 OPEN表结点父结点编号评价函数f(n)S04S106S204S306S415S515S616S726S827S935S1037S1145S1255S1357 CLOSED表编号结点父结点编号评价函数f(n)0S041S2042S4153S5154S9355S11456S1255结论：由以上分析,可以从CLOSED表中可知从初始状态到结束状态的搜索路径为：S0S2S5S9S11S12.五、实验体会 通过本次实验又将课本内容熟悉了一遍，而且通过互联网了解了更多的