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

学生实验报告 实验课名称：人工智能 实验名 称 : 八数码 专 业 名 称：计算机科学与技术 班 级： 学 号： 学 生 姓 名： 教 师 姓 名： 2010 年 10 月 20日 实验内容 用OPEN表和CLOSED表解决有哪些信誉好的足球投注网站问题。 二．实验题目 采用启发式算法（如A*算法）求解八数码问题。 三．实验要求 必须使用OPEN表和CLOSED表。 明确给出问题描述。系统初始状态。目标状态和启发式函数。 除了初始状态以外，至少有哪些信誉好的足球投注网站四层。 给出解路径（解图）。 四． 实验过程 ① 问题：初始状态到目标状态是否可解如何判断？ 答：实验过程自己给出的初始状态使用A*算法求解，并不是所有的初始状态都可解到达目标状态。因为八数码问题其实是0~9的一个排列，而排列有奇排列和偶排列，从奇排列不能转化为偶排列或者相反。例如： 函数f(s)表示s前比s小的数字的数目（s不等于0）. 则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数码中的某一个数码。棋盘中留有一个空格，允许周围的某一个将牌向空格移动，这样通过移动将牌就可以不断地改变将牌的布局。这种游戏的求解的问题是：给定一种处世的将牌布局或结构和一个目标的布局，问如何移动将牌，实现从从初始状态到目标状态的转变。 下面给出初始状态和目标状态： 2 8 3 1 6 4 7 5 初始状态： 1 2 3 8 4 7 6 5 目标状态： 评价函数f(n)形式为：f(n)=g(n)+h(n),其中g(n)是节点所处的深度，h(n)是启发式函数，这里启发式函数h(n)表示“不在位”的将牌个数，这时f(n)可估计出通向目标结点的希望的程度。 注意：移动规则为左-(上(右(下。 ③有哪些信誉好的足球投注网站过程： 如下图-1为八数码问题的有哪些信誉好的足球投注网站树： 图-1 2 8 3 1 6 4 7 5 2 8 3 1 6 4 7 5 2 8 3 1 6 4 7 5 2 8 3 1 4 7 6 5 2 8 3 1 4 7 6 5 2 3 1 8 4 7 6 5 2 8 3 1 4 7 6 5 8 3 2 1 4 7 6 5 2 8 3 7 1 4 6 5 2 3 1 8 4 7 6 5 2 3 1 8 4 7 6 5 1 2 3 8 4 7 6 5 1 2 3 8 4 7 6 5 1 2 3 7 8 4 6 5 表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) S0 4 S1 0 6 S2 0 4 S3 0 6 S4 1 5 S5 1 5 S6 1 6 S7 2 6 S8 2 7 S9 3 5 S10 3 7 S11 4 5 S12 5 5 S13 5 7 CLOSED表 编号 结点 父结点编号 评价函数f(n) 0 S0 4 1 S2 0 4 2 S4 1 5 3 S5 1 5 4 S9 3 5 5 S11 4 5 6 S12 5 5 结论：由以上分析,可以从CLOSED表中可知从初始状态到结束状态的有哪些信誉好的足球投注网站路径为： S0(S2(S5(S9(S11