人工智能实验一报告 题目：采用A*算法解决八数码问题
姓 名：学 号： 10S003028
专 业： 计算机科学与技术
提交日期： 2011-05-04
目录
1问题描述 ............................................................................................................ - 2 -
1.1待解决问题的解释 ................................................................................... - 2 -
1.2问题的搜索形式描述 ................................................................................. - 2 -
1.3解决方案介绍（原理） ............................................................................. - 3 - 2算法介绍 ............................................................................................................ - 4 -
2.1A*搜索算法一般介绍 ................................................................................. - 4 -
2.2 算法伪代码 .............................................................................................. - 4 - 3算法实现 ............................................................................................................ - 5 -
3.1 实验环境与问题规模 ................................................................................ - 5 -
3.2 数据结构 ................................................................................................. - 5 -
3.3 实验结果 ................................................................................................. - 6 -
3.4系统中间及最终输出结果 .......................................................................... - 6 - 4参考文献 ............................................................................................................ - 7 - 5附录—源代码及其注释 ....................................................................................... - 7 -
- 1 -
1问题描述
所谓八数码问题是指这样一种游戏：将分别标有数字1，2，3，…，8 的八块正方形数码牌任意地放在一块3×3 的数码盘上。放牌时要求不能重叠。于是，在3×3 的数码盘上出现了一个空格。现在要求按照每次只能将与空格相邻的数码牌与空格交换的原则，不断移动该空格方块以使其和相邻的方块互换，直至达到所定义的目标状态。空格方块在中间位置时有上、下、左、右4个方向可移动，在四个角落上有2个方向可移动，在其他位置上有3个方向可移动，问题描述如下图1-1所示：
初始状态 中间状态 目标状态
图1-1 八数码问题的求解过程
1.1待解决问题的解释
首先，八数码问题包括一个初始状态(START) 和目标状态(END)，所谓解决八数码问题就是在两个状态间寻找一系列可过渡状态：
（START>STATE1>STATE2>...>END）
这个状态是否存在就是我们要解决的第一个问题：Q1：每一个状态及每一次操作的表示方法？有许多表示方法，比如一个3*3 的八数码盘可以压缩成一个int 值表示，但不适用于15 puzzle或大于8 的puzzle 问题。如果对空间要求很高，应该还可以再压缩。本文采用一个int 表示的方法。表示方法如下：由于int 的表示范围大于1e9，所以我们取一个int 的低9 位，为了方便寻找空格的位置，int 的个位我们用来放空格的位置（19）。而前8 位，按照行从上到下，列从左到右的顺序依次记录对应位置上的数字。
1.2问题的搜索形式描述
八数码问题形式化描述：
初始状态：
初始状态向量：规定向量中各分量对应的位置，各位置上的数字。把3×3的棋盘按从左到右，从上到下的顺序写成一个一维向量。我们可以设定初始状态：
<1,5,2,4,0,3,6,7,8>
- 2 -
后继函数：
按照某种规则移动数字得到的新向量。例如：
<1,5,2,4,0,3,6,7,8>?<1,0,2,4,5,3,6,7,8>
目标测试：
新向量是都是目标状态。即<1,2,3,4,5,6,7,8,0>是目标状态？
路径耗散函数：
每次移动代价为1，每执行一条规则后总代价加1。
1.3解决方案介绍（原理）
该问题是一个搜索问题。它是一种状态到另一种状态的变换。要解决这个问题，必须先把问题转化为数字描述。由于八数码是一个3*3的矩阵，但在算法中不实用矩阵，而是将这个矩阵转化为一个一维数组，使用这个一维数组来表示八数码，但是移动时要遵守相关规则。
(1) 可用如下形式的规则来表示数字通过空格进行移动：
<a1,a2,a3,a4,a5,a6,a7,a8,a9>→<b1,b2,b3,b4,b5,b6,b7,b8,b9>
(2)共24条移动规则，对应与每个位置的移动规则。
(3)搜索顺序举例：
<1>优先移动行数小的棋子(数字) <2>同一行中优先移动列数大的棋子
八数码的节点扩展应当遵循棋子的移动规则。按规则，每一次可以将一个与空格相邻的棋子移动到空格中，实际上也可以看做空格的相反方向移动。空格的移动方向可以是上下左右，当然不能出边界。棋子的位置，也就是保存状态的数组元素的下标，空格移动后，相应位置发生变化，在不移出边界的条件下，空格向右，下，左，上移动后，新位置是原位置分别加上1,3，-1，-3。在这里，空格可以用任意数字表示。操作本文用u r d l 分别表示空格的向上向右向下向左四个操作。
图的搜索策略：经分析，8数码问题的搜索策略共有：1.广度优先搜索、2.深度优先搜索、3.有界深度优先搜索、4.最好优先搜索、5.局部择优搜索，等等。其中广度优先搜索法是可采纳的，有界深度优先搜索法是不完备的，最好优先和局部择优搜索法是启发式搜索法。
本实验采用启发式A*搜索算法来实现。 (4)约束规则：不使离开既定位置的数字数增加
- 3 -
2算法介绍
问题的求解实际上就是在这个图中找到一条路径可以从开始到结果。这个寻找的过程就是状态空间搜索。常用的状态空间搜索有深度优先和广度优先。广度优先是从初始状态一层一层向下找，直到找到目标为止。深度优先是按照一定的顺序前查找完一个分支，再查找另一个分支，以至找到目标为止。
启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无畏的搜索路径，提高了效率。
2.1A*搜索算法一般介绍
A* 算法实际是一种启发式搜索，所谓启发式搜索，就是利用一个估价函数评估每次的的决策的价值，决定先尝试哪一种方案，这样可以极大的优化普通的广度优先搜索。一般来说，从出发点(A)到目的地(B)的最短距离是固定的，我们可以写一个函数 judge() 估计 A 到 B 的最短距离，如果程序已经尝试着从出发点 A 沿着某条路线移动到了 C 点, 那么我们认为这个方案的 A B 间的估计距离为 A 到 C 实际已经行走了的距离 H 加上用 judge() 估计出的 C 到
B 的距离。
如此，无论我们的程序搜索展开到哪一步，都会算出一个评估值，每一次决策后，将评估值和等待处理的方案一起排序，然后挑出待处理的各个方案中最有可能是最短路线的一部分的方案展开到下一步，一直循环到对象移动到目的地，或所有方案都尝试过却没有找到一条通向目的地的路径则结束。
A*算法是一个可采纳的最好优先算法。A*算法的估价函数可表示为：
f'(n) = g'(n) + h'(n)
这里，f'(n)是估价函数，g'(n)是起点到终点的最短路径值，h'(n)是n到目标的最断路经的启发值。由于这个f'(n)其实是无法预先知道的，所以我们用前面的估价函数f(n)做近似。g(n)代替g'(n)，但g(n)>=g'(n)才可（大多数情况下都是满足的，可以不用考虑），h(n)代替h'(n)，但h(n)<=h'(n)才可。可以证明应用这样的估价函数是可以找到最短路径的，也就是可采纳的。
2.2 算法伪代码
首先定义两个表，open表用于存放已经生成，且已用启发式函数进行过估计或评价，但尚未产生它们的后继节点的那些结点，这些结点也称未考察结点；
- 4 -
closed表用于存放已经生成，且已考察过的结点。设S0为初态，Sg为目标状态。 具体过程如下：
(1) 把S0放入open表，记为f=h，令closed为空表；
(2)重复下列过程，直至找到目标结点为止。若open为空表，则失败；
(3)选取open表中未设置过的具有最小f值的结点为最佳节点，并放入closed表中
(4)若最佳节点不是目标节点，则扩展之，产生后继节点。
(5)对每个后继结点进行下列过程：
? 建立从该后继结点返回最佳节点的指针；
? 计算g（后继结点）=g（最佳节点）+k（最佳节点，后继结点）；
? Ss：如果该后继节点∈open，则称此节点为old，并把它添加至最佳节点
的后继节点中
? 比较新旧路径代价，如果个g（后继节点）<g(old),则重新确定old的父
亲节点
? 若至old节点的代价比较低或一样，则停止扩展节点
? 若后继节点不再open表中，则看其是否在closed中
? 若后继节点在open表中，则转向Ss；
? 若后继节点既不在open表中，又不在closed表中，则把它放入open表
中，并填入最佳节点的后裔表，然后走下一步
(6)计算f值
(7)GO LOOP
3算法实现
3.1 实验环境与问题规模
(1)实验环境：Windows XP
(2)实验编程工具：VC++6.0
(3)问题规模算法规模小，最大搜索深度不超过32。
3.2 数据结构
本实验主要采用链表，队列，堆：
struct Chess//棋盘
{
- 5 -
int cell[N][N];//数码数组
int Value;//评估值
Direction BelockDirec;//所屏蔽方向
struct Chess * Parent;//父节点
};
queue<struct Chess *> Queue;//队列
stack<Chess *>Stack;//堆
Chess *p=ChessList;
p=p->Parent;//链表
3.3 实验结果
经测试，程序运行良好，结果正确。输入测试数据，初试状态<1 4 0 3 5 2 6 7 8>，目标状态<0 1 2 3 4 5 6 7 8>，运行结果有解，共经过四步。
3.4系统中间及最终输出结果
3.4.1输入数据结果如下图3-1所示：
图3-1输入数据结果
3.4.2运行中间及最终结果如下图3-2所示
- 6 -
图3-2程序运行结果
4参考文献
1．《Artificial intelligence :;a modern approach 人工智能 : 一种现代方法》 作者：Russell, Stuart J. 出版社：清华大学出版社
2． CSDN博客
5附录—源代码及其注释
/*栗丽霞 2011-04-29*/
#include <iostream>
#include "stdio.h"
#include "stdlib.h"
#include "time.h"
#include "string.h"
- 7 -
#include <queue>
#include <stack>
using namespace std;
const int N=3;//3*3棋盘
const int Max_Step=32;//最大搜索深度
enum Direction{None,Up,Down,Left,Right};//方向，分别对应上下左右
struct Chess//棋盘
{
int chessNum[N][N];//棋盘数码
int Value;//评估值
Direction BelockDirec;//所屏蔽方向
struct Chess * Parent;//父节点
};
void PrintChess(struct Chess *TheChess);//打印棋盘
struct Chess * MoveChess(struct Chess * TheChess,Direction Direct,bool CreateNewChess);//移动棋盘数字
int Appraisal(struct Chess * TheChess,struct Chess * Target);//估价函数
struct Chess * Search(struct Chess* Begin,struct Chess * Target);//A*搜索函数
int main()
{
//本程序的一组测试数据为
/*初始棋盘
*1 4 0* *3 5 2* *6 7 8* */
/*目标棋盘
*0 1 2* *3 4 5* *6 7 8* */
- 8 -
Chess Target;
Chess *Begin,*ChessList;
Begin=new Chess; int i; cout<<"请输入初始棋盘，各数字用空格隔开："<<endl; for(i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
cin>>Begin->chessNum[i][j];
}
}
cout<<"请输入目标棋盘，各数字用空格隔开："<<endl; for(i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
cin>>Target.chessNum[i][j];
}
}
//获取初始棋盘
Appraisal(Begin,&Target);
Begin->Parent=NULL;
Begin->BelockDirec=None;
Target.Value=0;
cout<<"初始棋盘:";
PrintChess(Begin);
cout<<"目标棋盘:";
PrintChess(&Target);
ChessList=Search(Begin,&Target);//搜索
//打印
if(ChessList)
{
/*将返回的棋盘列表利用栈将其倒叙*/
Chess *p=ChessList;
- 9 -
stack<Chess *>Stack;
while(p->Parent!=NULL)
{
Stack.push(p);
p=p->Parent;
}
cout<<"搜索结果:"<<endl;
int num=1;
while(!Stack.empty())
{
cout<<"第"<<num<<"步: "; num++;
PrintChess(Stack.top());
Stack.pop();
}
cout<<"\n完成!"<<endl;
}else
cout<<"搜索不到结果，搜索深度大于32\n"<<endl;
}
//打印棋盘
void PrintChess(struct Chess *TheChess)
{
cout<<"(评估值为"; cout<<TheChess->Value; cout<<")"<<endl; return 0;
for(int i=0;i<N;i++)
{
cout<<" ";
for(int j=0;j<N;j++)
{
cout<<TheChess->chessNum[i][j]<<" "; }
cout<<endl;
}
- 10 -
}
//移动棋盘
struct Chess * MoveChess(struct Chess * TheChess,Direction Direct,bool CreateNewChess) {
struct Chess * NewChess;
//获取空闲格位置
int i,j;
for(i=0;i<N;i++)
{
bool HasGetBlankCell=false;
for(j=0;j<N;j++)
{
if(TheChess->chessNum[i][j]==0)
{
HasGetBlankCell=true;
break;
}
}
if(HasGetBlankCell)
break;
}
bool AbleMove=true;
//判断是否可以移动 int ii=i,jj=j;
switch(Direct)
{
case Up:
i++;
if(i>=N)
AbleMove=false;
break;
case Down:
i--;
- 11 -
if(i<0)
AbleMove=false;
break;
case Left:
j++;
if(j>=N)
AbleMove=false;
break;
case Right:
j--;
if(j<0)
AbleMove=false;
break;
};
if(!AbleMove)//不可以移动则返回原节点
{
return TheChess;
}
if(CreateNewChess)
{
NewChess=new Chess();
for(int x=0;x<N;x++)
{
for(int y=0;y<N;y++)
NewChess->chessNum[x][y]=TheChess->chessNum[x][y];//创建新棋盘，此时值与原棋盘一致
}
}
else
NewChess=TheChess;
NewChess->chessNum[ii][jj] = NewChess->chessNum[i][j];//移动数字
NewChess->chessNum[i][j]=0;//将原数字位置设置为空格
return NewChess;
- 12 -
}
//估价函数
int Appraisal(struct Chess * TheChess,struct Chess * Target) {
int Value=0;
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
if(TheChess->chessNum[i][j]!=Target->chessNum[i][j]) Value++;
}
}
TheChess->Value=Value;
return Value;
}
//A*搜索函数
struct Chess * Search(struct Chess* Begin,struct Chess * Target) {
Chess *p1,*p2,*p;
int Step=0;//深度
p=NULL;
queue<struct Chess *> Queue;
Queue.push(Begin);//初始棋盘入队
//搜索
do{
p1=(struct Chess *)Queue.front();
Queue.pop();//出队
for(int i=1;i<=4;i++)//分别从四个方向推导出新子节点 {
Direction Direct=(Direction)i;
if(Direct==p1->BelockDirec)//跳过屏蔽方向 continue;
p2=MoveChess(p1,Direct,true);//移动数码
- 13 -
if(p2!=p1)//数码是否可以移动
{
Appraisal(p2,Target);//对新节点估价
if(p2->Value<=p1->Value)//是否为优越节点 {
p2->Parent=p1;
switch(Direct)//设置屏蔽方向,防止往回推 {
case Up:p2->BelockDirec=Down;break; case Down:p2->BelockDirec=Up;break; case Left:p2->BelockDirec=Right;break; case Right:p2->BelockDirec=Left;break; }
Queue.push(p2);//存储节点到待处理队列 if(p2->Value==0)//为0则,搜索完成 {
p=p2;
i=5;
}
}
else
{
delete p2;//为劣质节点则抛弃
p2=NULL;
}
}
}
Step++;
if(Step>Max_Step)
return NULL;
}while(p==NULL || Queue.size()<=0);
return p;
}
- 14 -