人工智能实验报告 八数码问题

实验一 启发式搜索算法

姓名：徐维坚 学号：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 #include #include #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;ifor(j=0;jif(Node->board.pos[i][j]==0){ }

zr[0]=i+1; zr[1]=j+1; break;

int Wrong(LNode *Node) { }

int pick(LNode *Node) {

int w=0,i,j,ii,jj; for(i=0;ifor(j=0;jif(Node->board.pos[i][j]!=goal[i][j]&&Node->board.pos[i][j]!=0){

for(ii=0;iifor(jj=0;jjif(Node->board.pos[i][j]==goal[ii][jj]){

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

int w=0,i,j; for(i=0;ifor(j=0;jif(Node->board.pos[i][j]!=goal[i][j]&&Node->board.pos[i][j]!=0)

w++;

}

}

}

}

}

return w;

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

LNode* NewNode=new LNode; for(int i=0;iswitch(moveflag) {

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

for(int j=0;jNewNode->board.pos[i][j]=Node->board.pos[i][j];

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){ }

NewNode->board.move=moveflag; NewNode->parent=Node; NodeQTY++; return NewNode;

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

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

int ListInsert(List &L,LNode* NewNode) { }

LNode* Getminf(List &L) {

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

min=q;//p,q寻找f最小值的指针，r指向表L中min前一个元素 List p=L; while(p->next){ }

NewNode->next=p->next; p->next=NewNode; return true;

p=p->next;

Open=(List)malloc(sizeof(LNode)); Close=(List)malloc(sizeof(LNode)); if(!Open&&!Close)

exit(Overflow);

Open->next=NULL; Close->next=NULL;

}

if(!q)

return NULL;

while(q) { }

r->next=min->next; min->next=NULL; return min;

if(min->board.f>q->board.f){ } p=q; q=q->next;

r=p; min=q;

int main() {

int i,j,choose; List Open,Close; LNode *Best,*current; LNode *Start=new LNode;

printf(\"\\\八 数 码 问 题 求 解\\n\"); printf(\"\\n请输入初始状态：\"); for(i=0;iprintf(\"(注:The flag of movement--1:左移;2:右移;3:上移;4:下移)\\n\"); printf(\"初始棋盘状态：\\n\"); for(i=0;ifor(j=0;jprintf(\"|%d\for(j=0;jscanf(\"%d\

}

printf(\"|\\n\");

InitList(Open,Close);

printf(\"请选择(1:A算法;2:A*算法):\"); scanf(\"%d\ 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){ }

printf(\"本算法搜索图中总共扩展的节点数为：%d\\n\ printf(\"\最佳路径如下所示：\\n\");

Best=Getminf(Open); ListInsert(Close,Best);

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

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)); printf(\"$$$******有解！******$$$\\n\"); break;

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));

if(Open->next) {

while(Best->parent){ }

List p=Close->next,q=Close->next; if(p==Start) q=p->next; else

exit(1); Best->flag=1; Best=Best->parent;

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\

}

}

}

}

for(i=0;ip=q;//记住父节点

for(j=0;jprintf(\"|%d\

printf(\"|\\n\");

q=q->next;

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

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

2. 输出结果： 2.1 A算法：

2.2 A*算法：