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

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

2、有的初始状态都可解到达目标状态。因为八数码问题其实是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数码中的某一个数码。棋盘中留有一个空格，允许周围的某一个将牌向空格移动，这样通过移动将牌就可以不断地改变将牌的布局。这种游戏的求解的问

3、题是：给定一种处世的将牌布局或结构和一个目标的布局，问如何移动将牌，实现从从初始状态到目标状态的转变。下面给出初始状态和目标状态：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

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)

5、,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表中可知从初始状态到结束状态的搜索路径为：s0às2às5às9às11às12.五、实验体会 通过本次实验又将课本内容熟悉了一遍，而且通过互联网了解