利用人工智能技术解决八数码游戏问题

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．例子及分析

双向宽度优先搜索：

深度优先搜索：

启发式搜索：

6．体会与致谢

这次事件让我的编程能力有了很大的提高，查阅资料等能力也有很大的提升。让我对人工智能技术有了进一步的认识。在解决问题和算法设计上的能力也极大地提高。这次作业我花了近10天的事件收集相关材料阅读并消化，并写出双向宽度遍历，深度遍历以及启发式搜索算法。本来想用C#进行界面化，由于其他编程作业的需要所以我想在以后学习之余将其完善，期望老师能够给我一个高分。

7．实验程序简单说明

1.       宽度优先遍历：我才用了双向宽度优先遍历，从起始节点和目标节点同时开始宽度搜索，当有交集时停止，这大大减少了时间复杂度。我对八数码采用char类型的记录，例：“123456780”，并且对待起始节点和目标节点采用计算两者的逆序值快速判断其实节点能否到达目标节点，采用hash表避免重复访问一个状态。

本例中没有用随机产生初始节点的方法，而是在程序中定好，应为一般的mcm题目都是给出了起始节点和目标节点。

2.       深度优先遍历：深度优先遍历我为了自动生成起始节点错误率高的现象，有目标节点随机移动步数得到起始节点。

3.       启发式所搜：启发式搜索是在路径搜索问题中很实用的搜索方式，通过设计一个好的启发式函数来计算状态的优先级，优先考虑优先级高的状态，可以提早搜索到达目标态的时间。

   A*是一种启发式搜索的，他的启发式函数 f'()=g'()+h'()能够应用到八数码问题中来。

g ' （）从起始状态到当前状态的实际代价g*()的估计值，g' ()>=g*()

   h' ()从当前状态到目标状态的实际代价 h*()的估计值，h'()<=h*()

   注意两个限制条件：

  （1）h'()<= h*()（2）任意状态的f '()值必须大于其父状态的 f'()值，即 f'()单调递增。其 中，   g' ()是搜索的深度， h' ()则是一个估计函数，用以估计当前态到目标态可能的步数。解八数码问题时一般有两种估计函数。比较简单的是difference(Statusa, Statusb)，其返回值是a和b状态各位置上数字不同的次数。另一种比较经典的是曼哈顿距离manhattan(Statusa, Statusb)，其返回的是各个数字从 a的位置到 b的位置的距离。

其他和宽度优先遍历类似。

启发式搜索我是在双向宽度搜索的基础上改进而得，使用了队列的方法存储扩展出来的有效的节点。

 

第二篇：人工智能实验报告 八数码问题

实验一  启发式搜索算法

姓名：徐维坚学号：2220103484 日期：20##/6/29

一、实验目的：

熟练掌握启发式搜索算法及其可采纳性。

二、实验内容：

使用启发式搜索算法求解8数码问题。

1)        编制程序实现求解8数码问题算法，采用估价函数

，

其中：是搜索树中结点的深度；为结点的数据库中错放的棋子个数；为结点的数据库中每个棋子与其目标位置之间的距离总和。

2)        分析上述⑴中两种估价函数求解8数码问题的效率差别，给出一个是的上界

的的定义，并测试使用该估价函数是否使算法失去可采纳性。

三、实验原理：

1.   问题描述：

八数码问题也称为九宫问题。在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格（以数字0来表示），与空格相邻的棋子可以移到空格中。

要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。

所谓问题的一个状态就是棋子在棋盘上的一种摆法。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。

2.        原理描述：

2.1 有序搜索算法：

（1）原理：

在搜索过程中，OPEN表中节点按照其估价函数值以递增顺序排列，选择OPEN表中具有最小估价函数值的节点作为下一个待扩展的节点，这种搜索方法称为有序搜索。

在本例中，估价函数中的取节点深度，为节点n的状态与目标状态之间错放的个数，即函数。

（2）算法描述：

①       把起始节点S放到OPEN表中，并计算节点S的；

②       如果OPEN是空表，则失败退出，无解；

③       从OPEN表中选择一个值最小的节点。如果有几个节点值相同，当其中有一个

为目标节点时，则选择此目标节点；否则就选择其中任一个节点作为节点；

④       把节点从 OPEN 表中移出，并把它放入 CLOSED 的已扩展节点表中；

⑤       如果是个目标节点，则成功退出，求得一个解；

⑥       扩展节点，生成其全部后继节点。对于的每一个后继节点：

计算；如果 既不在OPEN表中，又不在CLOCED表中，则用估价函数把

它添入OPEN表中。从加一指向其父节点的指针，以便一旦找到目标节点时记住一个解答路径；如果已在OPEN表或CLOSED表中，则比较刚刚对计算过的和前面计算过的该节点在表中的值。如果新的较小，则

(I)以此新值取代旧值。

(II)从指向，而不是指向他的父节点。

(III)如果节点在CLOSED表中，则把它移回OPEN表中。

⑦       转向②，即GOTO②。

（3）算法流程图：

2.2启发式搜索技术

（1）原理

启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。

（2）估价函数

计算一个节点的估价函数，可以分成两个部分：

1、  已经付出的代价（起始节点到当前节点）；

2、  将要付出的代价（当前节点到目标节点）。

节点n的估价函数定义为从初始节点、经过n、到达目标节点的路径的最小代价的估计值，即 = + 。

是从初始节点到达当前节点n的实际代价；

是从节点n到目标节点的最佳路径的估计代价，体现出搜索过程中采用的启发式信息（背景知识），称之为启发函数。

所占的比重越大，越趋向于宽度优先或等代价搜索；反之，的比重越大，表示启发性能就越强。

本实验中我们使用函数，其值是节点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)：

分别为函数和。

5）LNode* extend(LNode *Node,int depth,int zero[2],int moveflag,int Choose)

树形方式扩展节点。Node为要扩展的当前节点，depth为当前深度，zero存放该节点空格位置信息，moveflag即扩展节点的移动方式，Choose为选择函数还是。

6）void InitList(LNode* &Open,LNode* &Close)和int ListInsert(List &L,LNode* NewNode)

分别为表OPEN、CLOSE的创建和表的插入操作。

7）LNode* Getminf(List &L)

主要是实现从OPEN表中选择一个值最小的节点。如果有几个节点值相同，当其中

有一个为目标节点时，则选择此目标节点；否则就选择其中任一个节点作为节点。

五、实验小结

通过本次试验，我对启发式搜索有了更加深入的了解。

在实验中，通过对两种启发式搜索所扩在的节点数来看，看来比更加有效，能在复杂情况下求得更加优质的解，避免不必要的节点的扩展。但是对于估价函数来说，它的定义趋向多元化，只是它的一个比较好的特例，对一复杂的搜索问题，如国际象棋问题，他就显得较简单。所以，要更好地定义一个估价函数还有待深入讨论。

在寻找最佳扩展路径的过程中我发现，最佳扩展路基上的节点均在CLOSED表中，利用标志flag，以及它们之间的父子关系，我很容易的就找到了扩展路径，避免了再用一个路径指针path来找到路径，这样节省了存储空间，更利于搜索。

通过实验结果来看，这两个函数都是可采纳的，尽管存在不必要的扩展。

六、实验代码及输出结果

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{//棋盘信息

       Piece pos[N][N];//记录每个数码a的位置r行c列

       int d,f,move;//d:深度；f:启发函数值 ；move:父节点移动到该节点的方式

};

struct LNode{

       Chessboard board;

       LNode *parent,*next;

       bool flag;

};

typedef LNode* List;

int* Findzero(LNode* &Node)

{

       int i,j,zr[2];

       int *z=zr;

       for(i=0;i<N;i++){

              for(j=0;j<N;j++){

                     if(Node->board.pos[i][j]==0){

                            zr[0]=i+1;

                            zr[1]=j+1;

                            break;

                     }

              }

       }

       return z;

}

int Wrong(LNode *Node)

{

       int w=0,i,j;

       for(i=0;i<N;i++){

              for(j=0;j<N;j++){

                     if(Node->board.pos[i][j]!=goal[i][j]&&Node->board.pos[i][j]!=0)

                            w++;

              }

       }

       return w;

}

int pick(LNode *Node)

{

       int w=0,i,j,ii,jj;

       for(i=0;i<N;i++){

              for(j=0;j<N;j++){

                     if(Node->board.pos[i][j]!=goal[i][j]&&Node->board.pos[i][j]!=0){

                            for(ii=0;ii<N;ii++)

                                   for(jj=0;jj<N;jj++)

                                          if(Node->board.pos[i][j]==goal[ii][jj]){

                                                 w=w+abs(ii-i)+abs(jj-j);

                                                 break;    

                                          }

                     }

              }

       }

       return w;

}

LNode* extend(LNode *Node,int depth,int zero[2],int moveflag,int Choose)

{

       LNode* NewNode=new LNode;

       for(int i=0;i<N;i++){

              for(int j=0;j<N;j++){

                     NewNode->board.pos[i][j]=Node->board.pos[i][j];

              }

       }

       switch(moveflag)

       {

              case 1:     //向左移，不能出界：zero[1]>=2

                            NewNode->board.pos[zero[0]-1][zero[1]-1]=NewNode->board.pos[zero[0]-1][zero[1]-2];

                            NewNode->board.pos[zero[0]-1][zero[1]-2]=0;

                            break;

              case 2:     //向右移，不能出界：zero[1]<=2

                            NewNode->board.pos[zero[0]-1][zero[1]-1]=NewNode->board.pos[zero[0]-1][zero[1]];

                            NewNode->board.pos[zero[0]-1][zero[1]]=0;

                            break;

              case 3:     //向上移，不能出界：zero[0]>=2

                            NewNode->board.pos[zero[0]-1][zero[1]-1]=NewNode->board.pos[zero[0]-2][zero[1]-1];

                            NewNode->board.pos[zero[0]-2][zero[1]-1]=0;

                            break;

              case 4:     //向下移，不能出界：zero[0]<=2

                            NewNode->board.pos[zero[0]-1][zero[1]-1]=NewNode->board.pos[zero[0]][zero[1]-1];

                            NewNode->board.pos[zero[0]][zero[1]-1]=0;

                            break;           

       }

       NewNode->board.d=depth+1;

       switch(Choose){

              case 1:NewNode->board.f=NewNode->board.d+Wrong(NewNode);break;

              case 2:NewNode->board.f=NewNode->board.d+pick(NewNode);break;

       }

       NewNode->board.move=moveflag;

       NewNode->parent=Node;

       NodeQTY++;

       return NewNode;

}

void InitList(LNode* &Open,LNode* &Close)

{

       Open=(List)malloc(sizeof(LNode));

       Close=(List)malloc(sizeof(LNode));

       if(!Open&&!Close)

              exit(Overflow);

       Open->next=NULL;

       Close->next=NULL;

}

int ListInsert(List &L,LNode* NewNode)

{

       List p=L;

       while(p->next){

              p=p->next;

       }

       NewNode->next=p->next;

       p->next=NewNode;

       return true;

}

LNode* Getminf(List &L)

{    

       List p=L,q=L->next,r=L,min;

       min=q;//p,q寻找f最小值的指针，r指向表L中min前一个元素

       if(!q)

              return NULL;

       while(q)

       {

              if(min->board.f>q->board.f){

                     r=p;

                     min=q;

              }

              p=q;

              q=q->next;

       }

       r->next=min->next;

       min->next=NULL;

       return min;

}

int main()

{

       int i,j,choose;

       List Open,Close;

       LNode *Best,*current;

       LNode *Start=new LNode;

       printf("\t\t\t八 数 码 问 题 求 解\n");

       printf("\n请输入初始状态：");

       for(i=0;i<N;i++){

              for(j=0;j<N;j++){

                     scanf("%d",&(Start->board.pos[i][j]));

              }

       }

       printf("(注:The flag of movement--1:左移;2:右移;3:上移;4:下移)\n");

       printf("初始棋盘状态：\n");

       for(i=0;i<N;i++){

              for(j=0;j<N;j++){

                     printf("|%d",Start->board.pos[i][j]);

              }

              printf("|\n");

       }

       InitList(Open,Close);

      printf("请选择(1:A算法;2:A*算法):");

      scanf("%d",&choose);  

      Start->board.d=0;

       switch(choose){

              case 1:Start->board.f=Start->board.d+Wrong(Start);break;

              case 2:Start->board.f=Start->board.d+pick(Start);break;

       } //  Start->board.f=0+Wrong(Start);

       Start->board.move=0;

       Start->parent=NULL;

       Start->next=NULL;

       Start->flag=1;

       ListInsert(Open,Start);//将S加入到Open表中

       while(Open->next){

              Best=Getminf(Open);

              ListInsert(Close,Best);

              if(!(Best->board.f-Best->board.d)){

                     printf("$$$******有解！******$$$\n");

                     break;

              }

              z=Findzero(Best);

              zero[0]=*(z+0);zero[1]=*(z+1);

              if(zero[1]>=N-1&&Best->board.move!=2) 

                     ListInsert(Open,extend(Best,Best->board.d,zero,1,choose));

              if(zero[1]<=N-1&&Best->board.move!=1) 

                     ListInsert(Open,extend(Best,Best->board.d,zero,2,choose));

              if(zero[0]>=N-1&&Best->board.move!=4) 

                     ListInsert(Open,extend(Best,Best->board.d,zero,3,choose));

              if(zero[0]<=N-1&&Best->board.move!=3) 

                     ListInsert(Open,extend(Best,Best->board.d,zero,4,choose));

       }

       printf("本算法搜索图中总共扩展的节点数为：%d\n",NodeQTY);

       printf("\t最佳路径如下所示：\n");

       if(Open->next)

       {

              while(Best->parent){

                     Best->flag=1;

                     Best=Best->parent;

              }

              List p=Close->next,q=Close->next;

              if(p==Start) q=p->next;

              else        exit(1);

              int Step=0;

              while(p&&q)//在Close表中依标记找到路径

              {

                     if(q->flag==1&&q->parent==p){

                            printf("Step %d:0 move as

the %d-flag of movement.\n",++Step,q->board.move);

                            for(i=0;i<N;i++){

                                   for(j=0;j<N;j++){

                                          printf("|%d",q->board.pos[i][j]);

                                   }    

                                   printf("|\n");

                            }

                            p=q;//记住父节点

                     }

                     q=q->next;    

              }

              printf("到达目标状态！\n");

       }

       else  printf("该问题无法求解！\n");

}

2. 输出结果：

2.1 A算法：

2.2 A*算法：