利用人工智能技术解决八数码游戏问题 1．八数码游戏问题简介 九宫排字问题（又称八数码问题）是人工智能当中有名的难题之一。问题是在 3×3方格盘上，放有八个数码，剩下第九个为空，每一空格其上下左右的数码可移至空格。问题给
定初始位置和目标位置，要求通过一系列的数码移动，将初始位置转化为目标位置。 2．八数码游戏问题的状态空间法表示 ①建立一个只含有初始节点s0的搜索图g，把s0放入open表中 ②建立closed表，且置为空表 ③判断open表是否为空表，若为空，则问题无解，退出 ④选择open表中的第一个节点，把它从open表移出，并放入closed表中，将此节点记为节点n
⑤考察节点n是否为目标节点，若是，则问题有解，成功退出。问题的解就是沿着n到
s0的路径得到。若不是转⑥ ⑥扩展节点n生成一组不是n的祖先的后继节点，并将它们记为集合m，将m中的这些
节点作为n的后继节点加入图g中 ⑦对未在g中出现过的（open和closed表中未出现过的）集合m中的节点, 设置一个指向父节点n的指针，并把这些节点放入open表中；对于已在g中出现过的m中的节点，确定是否需要修改指向父节点的指针；对于已在g中出现过并已在closed表中的m中的节点，
确定是否需要修改通向他们后继节点的指针。 ⑧ 按某一任意方式或某种策略重排open表中节点的顺序 ⑨ 转③
3．八数码游戏问题的盲目搜索技术 宽度优先搜索： 1、定义
如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索
(breadth-first search)。 2、特点
这种搜索是逐层进行的；在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。
3、宽度优先搜索算法
(1) 把起始节点放到open表中(如果该起始节点为一目标节点，则求得一个解答)。 (2) 如果open是个空表，则没有解，失败退出；否则继续。 (3) 把第一个节点(节点n)从open表移出，并把它放入closed的扩展节点表中。 (4) 扩展节点n。如果没有后继节点，则转向上述第(2)步。 (5) 把n的所有后继节点放到open表末端，并提供从这些后继节点回到n的指针。 (6) 如果n的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第(2)步。
流程图： 性质：
当问题有解时，一定能找到解。 当问题为单位消耗值，且问题有解时，一定能找到最优解。 算法与问题无关，具有通用性。 时间效率和空间效率都比较低。 深度优先搜索：
1、定义
在此搜索中，首先扩展最新产生的(即最深的)节点。深度相等的节点可以任意排列。这
种盲目(无信息)搜索叫做深度优先搜索(depth-first search)。 2、特点
首先，扩展最深的节点的结果使得搜索沿着状态空间某条单一的路径从起始节点向下进
行下去；只有当搜索到达一个没有后裔的状态时，它才考虑另一条替代的路径。 3、深度界限 为了避免考虑太长的路径(防止搜索过程沿着无益的路径扩展下去)，往往给出一个节点扩展的最大深度界限。任何节点如果达到了深度界限，那么都将把它们作为没有后继节点处理。
4、深度优先搜索算法
(1) 把起始节点放到open表中(如果该起始节点为一目标节点，则求得一个解答)。 (2) 如果open是个空表，则没有解，失败退出；否则继续。 (3) 把第一个节点(节点n)从open表移出，并把它放入closed的扩展节点表中。 (4) 考察节点n是否为目标节点，若是，则找到问题的解，用回溯法求解路径，退出 （5）如果没有后继节点，则转向上述第(2)步。 (6) 扩展节点n，把n的所有后继节点放到open表前端，并提供从这些后继节点回到n
的指针。转向第(2)步。
流程图： 性质：
一般不能保证找到最优解。 当深度限制不合理时，可能找不到解。 最坏情况时，搜索空间等同于穷举。 4．八数码游戏问题的启发式搜索技术 （给出你所采用估价函数，并介绍算法的基本原理和流程图） 估价函数:
f(n) = g(n) + h(n)是对下列函数的一种估计或近似： f*(n) = g*(n) + h*(n) f*(n)：从初始节点到节点n的一条最佳路径的实际代价加上从节点n到目标节点的最佳路径的代价之和。
g*(n)：从初始节点到节点n之间最小路径的实际代价 h*(n)：从节点n到目标节点的最小代价路径上代价 定义
利用与问题有关的知识（即：启发信息）来引导搜索，达到减少搜索范围，降低问题复
杂度的搜索过程称为启发式搜索方法。 核心问题：
启发信息应用，启发能力度量和如何获得启发信息。 启发信息的强度
强：降低搜索工作量，但可能导致找不到最优解。 弱：一般导致工作量加大，极限情况下变为盲目搜索，但可能可以找到最优解。 全局最佳优先搜索 ：
(1) 把起始节点放到open表中，并计算估价函数f(s0)。 (2) 如果open是个空表，则没有解，失败退出；否则继续。 (3) 把open表中的第一个节点（股价函数最小的节点n），移入closed表。
(4) 如果n是目标节点，问题得解，退出。否则继续。 (5) 判断节点n是否可扩展。若否则转向第(2)步，若是则转向(6)。 (6) 对节点n进行扩展，并对其所有后继节点计算估价函数f（n）的值，并为每个后继节点设置指向n节点的指针。把这些后继节点都送入open表，然后对open表中的全部节点
按照估价函数值从小到大的顺序排序。 (7) 转向第(2)步。
流程图： 5．例子及分析
双向宽度优先搜索： 深度优先搜索： 启发式搜索：篇二：人工智能实验报告 八数码问题 实验一 启发式搜索算法 姓名：徐维坚 学号：2220103484 日期：2012/6/29 一、实验目的：
熟练掌握启发式搜索a?算法及其可采纳性。 二、实验内容：
使用启发式搜索算法求解8数码问题。 1) 编制程序实现求解8数码问题a?算法，采用估价函数 ??w?n?， f?n??d?n?????p?n? 其中：d?n?是搜索树中结点n的深度；w?n?为结点n的数据库中错放的棋子个数；p?n?
为结点n的数据库中每个棋子与其目标位置之间的距离总和。 2) 分析上述⑴中两种估价函数求解8数码问题的效率差别，给出一个是p?n?的上界 的
h?n?的定义，并测试使用该估价函数是否使算法失去可采纳性。 三、实验原理： 1. 问题描述： 八数码问题也称为九宫问题。在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格（以数字0来表示），与空格
相邻的棋子可以移到空格中。 要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状
态的移动棋子步数最少的移动步骤。 所谓问题的一个状态就是棋子在棋盘上的一种摆法。解八数码问题实际上就是找出从初
始状态到达目标状态所经过的一系列中间过渡状态。 2. 原理描述：
2.1 有序搜索算法： （1）原理： 在搜索过程中，open表中节点按照其估价函数值以递增顺序排列，选择open表中具有
最小估价函数值的节点作为下一个待扩展的节点，这种搜索方法称为有序搜索。 在本例中，估价函数中的g(n)取节点深度d(n)，h(n)为节点n的状态与目标状态之间错
放的个数，即函数?(n)。 （2）算法描述：
① 把起始节点s放到open表中，并计算节点s的f(s)； ② 如果open是空表，则失败退出，无解； ③ 从open表中选择一个f值最小的节点i。如果有几个节点值相同，当其中有一个 为
目标节点时，则选择此目标节点；否则就选择其中任一个节点作为节点i；
④ 把节点i从 open 表中移出，并把它放入 closed 的已扩展节点表中； ⑤ 如果i是个目标节点，则成功退出，求得一个解； ⑥ 扩展节点i，生成其全部后继节点。对于i的每一个后继节点j： 计算f(j)；如果j 既不在open表中，又不在cloced表中，则用估价函数f把 它添入open表中。从j加一指向其父节点i的指针，以便一旦找到目标节点时记住一个解答路径；如果j已在open表或closed表中，则比较刚刚对j计算过的f和前面计算过的该节点在表
中的f值。如果新的f较小，则 (i)以此新值取代旧值。
(ii)从j指向i，而不是指向他的父节点。 (iii)如果节点j在closed表中，则把它移回open表中。 ⑦ 转向②，即goto②。
（3）算法流程图： 2.2启发式搜索技术
（1）原理 启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发
式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。 （2）估价函数
计算一个节点的估价函数，可以分成两个部分： 1、 已经付出的代价（起始节点到当前节点）； 2、 将要付出的代价（当前节点到目标节点）。 节点n的估价函数f(n)定义为从初始节点、经过n、到达目标节点的路径的最小代价的
估计值，即f*(n) = g*(n)+ h*(n)。 g*(n)是从初始节点到达当前节点n的实际代价； h*(n)是从节点n到目标节点的最佳路径的估计代价，体现出搜索过程中采用的启发式信息（背景知识），称之为启发函数。 g*(n)所占的比重越大，越趋向于宽度优先或等代价搜索；反之，h*(n)的比重越大，表示启发性能就越强。 本实验中我们使用函数p(n)，其值是节点n与目标状态节点相比较，每个错位棋牌在假设不受阻拦的情况下，移动到目标状态相应位置所需走步（移动次数）的总和。显然p(n)比?(n)
更接近于h*(n)，因为p(n)不仅考虑了错位因素，还考虑了错位的距离。 （3）算法描述：
参考有序搜索算法描述，基本相同。流程图亦参考有序算法流程图。 四、实验程序及其说明：
1）int goal[n][n]，struct chessboard： 试验中我定义goal数组为目标状态——{1,2,3,8,0,4,7,6,5}。结构体chessboard记录棋盘信息，其中变量pos数组坐标记录每个数码a的位置，其值为数码a。d表示该棋盘的深度，f为启发函数值，move为父节点移动到该节点的方式，以便在输出时告诉用户该如何移
动棋子知道目标状态。 2）struct lnode： 定义节点lnode结构体，存放该节点状态时的棋盘信息board，和指向父节点、下一节点的指针(*parent,*next)，以及标记量flag——值为true时表示该节点是最佳路径上的节点。
3）int* findzero(lnode* &node)：
为方便找到空格，我设计了找到该函数findzero(*&node)，以便找到当前节点空格
所在位置以利于接下来的程序执行。返回值为空格所在的行和列。 4）int wrong(lnode *node)和int pick(lnode *node)： 分别为函数?(n)和p(n)。
5）lnode* extend(lnode *node,int depth,int zero[2],int moveflag,int choose) 树形方式扩展节点。node为要扩展的当前节点，depth为当前深度，zero存放该节点空
格位置信息，moveflag即扩展节点的移动方式，choose为选择函数?(n)还是p(n)。 6）void initlist(lnode* &open,lnode* &close)和int listinsert(list
&l,lnode* newnode)
分别为表open、close的创建和表的插入操作。 7）lnode* getminf(list &l) 主要是实现从open表中选择一个f值最小的节点i。如果有几个节点值相同，当其中 有
一个为目标节点时，则选择此目标节点；否则就选择其中任一个节点作为节点i。 五、实验小结
通过本次试验，我对启发式搜索有了更加深入的了解。 在实验中，通过对两种启发式搜索所扩在的节点数来看，p(n)看来比?(n)更加有效，能在复杂情况下求得更加优质的解，避免不必要的节点的扩展。但是对于估价函数h*(n)来说，它的定义趋向多元化，p(n)只是它的一个比较好的特例，对一复杂的搜索问题，如国际象棋
问题，他就显得较简单。所以，要更好地定义一个估价函数还有待深入讨论。 在寻找最佳扩展路径的过程中我发现，最佳扩展路基上的节点均在closed表中，利用标志flag，以及它们之间的父子关系，我很容易的就找到了扩展路径，避免了再用一个路径指
针path来找到路径，这样节省了存储空间，更利于搜索。 通过实验结果来看，这两个函数都是可采纳的，尽管?(n)存在不必要的扩展。 六、实验代码及输出结果 1. 源代码：
#include<stdio.h> #include<malloc.h> #include<stdlib.h> #define overflow 1 #define n 3
int goal[n][n]={1,2,3,8,0,4,7,6,5}; int zero[2],nodeqty=0;
int *z=zero;//记录0的位置，zero[0]:r行；zero[1]:c列 typedef int piece;
struct chessboard{//棋盘信息 };
struct lnode{ };
typedef lnode* list;
int* findzero(lnode* &node) { chessboard board; lnode *parent,*next; bool flag; piece pos[n][n];//记录每个数码a的位置r行c列 int d,f,move;//d:深度；f:启发函数值 ；move:父节点移动到该
节点的方式 } int i,j,zr[2]; int *z=zr; for(i=0;i<n;i++){ } return z;