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

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'()board.pos[zero[0]-1][zero[1]-2]; NewNode->board.pos[zero[0]-1][zero[1]-2]=0; break; case 2: //向右移，不能出界：zero[1]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]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("\t\t\t八 数 码 问 题 求 解\n"); printf("\n请输入初始状态："); for(i=0;iboard.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",NodeQTY); printf("\t最佳路径如下所示：\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]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]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",++Step,q->board.move);

} } } } for(i=0;inext; printf("到达目标状态！\n"); else printf("该问题无法求解！\n");

2. 输出结果：

2.1 A算法：

2.2 A*算法：