人工智能实验一报告 题目：采用A*算法解决八数码问题
姓 名：学 号： 081110317
专 业：提交日期： 2014-05-22
目录
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 实验结果 ............................................................................................................... - 5 -
3.4系统中间及最终输出结果 .................................................................................... - 7 - 4参考文献 ........................................................................................................................... - 8 - 5附录—源代码及其注释 ................................................................................................... - 8 -
- 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.2 数据结构
1)定义状态图中的结点数据结构
typedef struct Node
{
status data;//结点所存储的状态
- 5 -
struct Node *parent;//指向结点的父亲结点
struct SpringLink *child;//指向结点的后继结点
struct Node *next;//指向open或者closed表中的后一个结点
int fvalue;//结点的总的路径
int gvalue;//结点的实际路径
int hvalue;//结点的到达目标的苦难程度
}NNode , *PNode;
2)定义存储指向结点后继结点的指针的地址
typedef struct SpringLink
{
struct Node *pointData;//指向结点的指针
struct SpringLink *next;//指向兄第结点
}SPLink , *PSPLink;
3)初始化一个空链表
void initLink(PNode &Head)
3.3 实验结果
经测试，程序运行良好，结果正确。输入测试数据，初试状态<0,1,2,3,4,5,6,7，8>，目标状态<,1,4,2,3,5,8,6,7,0>，运行结果有解，共经过四步。
- 6 -
3.4系统中间及最终输出结果
图3-1程序运行中间结果
- 7 -
图3-2程序运行最终结果
4参考文献
1．《Artificial intelligence :;a modern approach 人工智能 : 一种现代方法》 作者：Russell, Stuart J. 出版社：清华大学出版社
2． CSDN博客
5附录—源代码及其注释
#include "iostream"
#include "stdlib.h"
#include "conio.h"
#define size 3
using namespace std;
//定义二维数组来存储数据表示某一个特定状态
- 8 -
typedef int status[size][size];
struct SpringLink;
//定义状态图中的结点数据结构
typedef struct Node
{
status data;//结点所存储的状态
struct Node *parent;//指向结点的父亲结点
struct SpringLink *child;//指向结点的后继结点
struct Node *next;//指向open或者closed表中的后一个结点 int fvalue;//结点的总的路径
int gvalue;//结点的实际路径
int hvalue;//结点的到达目标的苦难程度
}NNode , *PNode;
//定义存储指向结点后继结点的指针的地址
typedef struct SpringLink
{
struct Node *pointData;//指向结点的指针
struct SpringLink *next;//指向兄第结点
}SPLink , *PSPLink;
PNode open;
PNode closed;
//开始状态与目标状态
status startt = {0,1,2,3,4,5,6,7,8};
status target = {1,4,2,3,5,8,6,7,0};
//初始化一个空链表
void initLink(PNode &Head)
- 9 -
{
Head = (PNode)malloc(sizeof(NNode));
Head->next = NULL;
}
//判断链表是否为空
bool isEmpty(PNode Head)
{
if(Head->next == NULL)
return true;
else
return false;
}
//从链表中拿出一个数据
void popNode(PNode &Head , PNode &FNode)
{
if(isEmpty(Head))
{
FNode = NULL;
return;
}
FNode = Head->next;
Head->next = Head->next->next;
FNode->next = NULL;
}
//向结点的最终后继结点链表中添加新的子结点 void addSpringNode(PNode &Head , PNode newData) {
PSPLink newNode = (PSPLink)malloc(sizeof(SPLink));
- 10 -
newNode->pointData = newData;
newNode->next = Head->child;
Head->child = newNode;
}
//释放状态图中存放结点后继结点地址的空间 void freeSpringLink(PSPLink &Head)
{
PSPLink tmm;
while(Head != NULL)
{
tmm = Head;
Head = Head->next;
free(tmm);
}
}
//释放open表与closed表中的资源
void freeLink(PNode &Head)
{
PNode tmn;
tmn = Head;
Head = Head->next;
free(tmn);
while(Head != NULL)
{
//首先释放存放结点后继结点地址的空间 freeSpringLink(Head->child);
tmn = Head;
- 11 -
Head = Head->next;
free(tmn);
}
}
//向普通链表中添加一个结点
void addNode(PNode &Head , PNode &newNode) {
newNode->next = Head->next;
Head->next = newNode;
}
//向非递减排列的链表中添加一个结点
void addAscNode(PNode &Head , PNode &newNode) {
PNode P;
PNode Q;
P = Head->next;
Q = Head;
while(P != NULL && P->fvalue < newNode->fvalue) {
Q = P;
P = P->next;
}
//上面判断好位置之后，下面就是简单的插入了 newNode->next = Q->next;
Q->next = newNode;
}
//计算结点额h值
int computeHValue(PNode theNode)
- 12 -
{
int num = 0;
for(int i = 0 ; i < 3 ; i++)
{
for(int j = 0 ; j < 3 ; j++)
{
if(theNode->data[i][j] != target[i][j]) num++;
}
}
return num;
}
//计算结点的f，g，h值
void computeAllValue(PNode &theNode , PNode parentNode) {
if(parentNode == NULL)
theNode->gvalue = 0;
else
theNode->gvalue = parentNode->gvalue + 1;
theNode->hvalue = computeHValue(theNode);
theNode->fvalue = theNode->gvalue + theNode->hvalue; }
//初始化函数，进行算法初始条件的设置
void initial()
{
//初始化open以及closed表
initLink(open);
initLink(closed);
- 13 -
//初始化起始结点，令初始结点的父节点为空结点 PNode NULLNode = NULL;
PNode Start = (PNode)malloc(sizeof(NNode)); for(int i = 0 ; i < 3 ; i++)
{
for(int j = 0 ; j < 3 ; j++)
{
Start->data[i][j] = startt[i][j];
}
}
Start->parent = NULL;
Start->child = NULL;
Start->next = NULL;
computeAllValue(Start , NULLNode);
//起始结点进入open表
addAscNode(open , Start);
}
//将B节点的状态赋值给A结点
void statusAEB(PNode &ANode , PNode BNode) {
for(int i = 0 ; i < 3 ; i++)
{
for(int j = 0 ; j < 3 ; j++)
{
ANode->data[i][j] = BNode->data[i][j]; }
}
}
//两个结点是否有相同的状态
- 14 -
bool hasSameStatus(PNode ANode , PNode BNode) {
for(int i = 0 ; i < 3 ; i++)
{
for(int j = 0 ; j < 3 ; j++)
{
if(ANode->data[i][j] != BNode->data[i][j]) return false;
}
}
return true;
}
//结点与其祖先结点是否有相同的状态
bool hasAnceSameStatus(PNode OrigiNode , PNode AnceNode) {
while(AnceNode != NULL)
{
if(hasSameStatus(OrigiNode , AnceNode)) return true;
AnceNode = AnceNode->parent;
}
return false;
}
//取得方格中空的格子的位置
void getPosition(PNode theNode , int &row , int &col) {
for(int i = 0 ; i < 3 ; i++)
{
for(int j = 0 ; j < 3 ; j++)
{
- 15 -
if(theNode->data[i][j] == 0)
{
row = i;
col = j;
return;
}
}
}
}
//交换两个数字的值
void changeAB(int &A , int &B)
{
int C;
C = B;
B = A;
A = C;
}
//检查相应的状态是否在某一个链表中
bool inLink(PNode spciNode , PNode theLink , PNode &theNodeLink , PNode &preNode) {
preNode = theLink;
theLink = theLink->next;
while(theLink != NULL)
{
if(hasSameStatus(spciNode , theLink))
{
theNodeLink = theLink;
return true;
}
preNode = theLink;
- 16 -
theLink = theLink->next;
}
return false;
}
//产生结点的后继结点(与祖先状态不同)链表
void SpringLink(PNode theNode , PNode &spring)
{
int row;
int col;
getPosition(theNode , row , col);
//空的格子右边的格子向左移动
if(col != 2)
{
PNode rlNewNode = (PNode)malloc(sizeof(NNode));
statusAEB(rlNewNode , theNode);
changeAB(rlNewNode->data[row][col] , rlNewNode->data[row][col + 1]); if(hasAnceSameStatus(rlNewNode , theNode->parent))
{
free(rlNewNode);//与父辈相同，丢弃本结点
}
else
{
rlNewNode->parent = theNode;
rlNewNode->child = NULL;
rlNewNode->next = NULL;
computeAllValue(rlNewNode , theNode);
//将本结点加入后继结点链表
addNode(spring , rlNewNode);
}
}
- 17 -
//空的格子左边的格子向右移动
if(col != 0)
{
PNode lrNewNode = (PNode)malloc(sizeof(NNode));
statusAEB(lrNewNode , theNode);
changeAB(lrNewNode->data[row][col] , lrNewNode->data[row][col - 1]); if(hasAnceSameStatus(lrNewNode , theNode->parent))
{
free(lrNewNode);//与父辈相同，丢弃本结点
}
else
{
lrNewNode->parent = theNode;
lrNewNode->child = NULL;
lrNewNode->next = NULL;
computeAllValue(lrNewNode , theNode);
//将本结点加入后继结点链表
addNode(spring , lrNewNode);
}
}
//空的格子上边的格子向下移动
if(row != 0)
{
PNode udNewNode = (PNode)malloc(sizeof(NNode));
statusAEB(udNewNode , theNode);
changeAB(udNewNode->data[row][col] , udNewNode->data[row - 1][col]); if(hasAnceSameStatus(udNewNode , theNode->parent))
{
free(udNewNode);//与父辈相同，丢弃本结点
}
else
{
udNewNode->parent = theNode;
udNewNode->child = NULL;
udNewNode->next = NULL;
- 18 -
computeAllValue(udNewNode , theNode);
//将本结点加入后继结点链表
addNode(spring , udNewNode);
}
}
//空的格子下边的格子向上移动
if(row != 2)
{
PNode duNewNode = (PNode)malloc(sizeof(NNode));
statusAEB(duNewNode , theNode);
changeAB(duNewNode->data[row][col] , duNewNode->data[row + 1][col]); if(hasAnceSameStatus(duNewNode , theNode->parent))
{
free(duNewNode);//与父辈相同，丢弃本结点
}
else
{
duNewNode->parent = theNode;
duNewNode->child = NULL;
duNewNode->next = NULL;
computeAllValue(duNewNode , theNode);
//将本结点加入后继结点链表
addNode(spring , duNewNode);
}
}
}
//输出给定结点的状态
void outputStatus(PNode stat)
{
for(int i = 0 ; i < 3 ; i++)
{
for(int j = 0 ; j < 3 ; j++)
{
- 19 -
cout << stat->data[i][j] << " ";
}
cout << endl;
}
}
//输出最佳的路径
void outputBestRoad(PNode goal)
{
int deepnum = goal->gvalue;
if(goal->parent != NULL)
{
outputBestRoad(goal->parent);
}
cout << "第" << deepnum-- << "层的状态：" << endl;
outputStatus(goal);
}
void AStar()
{
PNode tmpNode;//指向从open表中拿出并放到closed表中的结点的指针
PNode spring;//tmpNode的后继结点链
PNode tmpLNode;//tmpNode的某一个后继结点
PNode tmpChartNode;
PNode thePreNode;//指向将要从closed表中移到open表中的结点的前一个结点的指针 bool getGoal = false;//标识是否达到目标状态
long numcount = 1;//记录从open表中拿出结点的序号
initial();//对函数进行初始化
initLink(spring);//对后继链表的初始化
tmpChartNode = NULL;
- 20 -
cout << "从open表中拿出的结点的状态及相应的值" << endl;
while(!isEmpty(open))
{
//从open表中拿出f值最小的元素,并将拿出的元素放入closed表中
popNode(open , tmpNode);
addNode(closed , tmpNode);
cout << "第" << numcount++ << "个状态是：" << endl;
outputStatus(tmpNode);
cout << "其f值为：" << tmpNode->fvalue << endl;
cout << "其g值为：" << tmpNode->gvalue << endl;
cout << "其h值为：" << tmpNode->hvalue << endl;
//如果拿出的元素是目标状态则跳出循环
if(computeHValue(tmpNode) == 0)
{
getGoal = true;
break;
}
//产生当前检测结点的后继(与祖先不同)结点列表，产生的后继结点的parent属性指向当前检测的结点
SpringLink(tmpNode , spring);
//遍历检测结点的后继结点链表
while(!isEmpty(spring))
{
popNode(spring , tmpLNode);
//状态在open表中已经存在，thePreNode参数在这里并不起作用 if(inLink(tmpLNode , open , tmpChartNode , thePreNode))
{
addSpringNode(tmpNode , tmpChartNode);
- 21 -
if(tmpLNode->gvalue < tmpChartNode->gvalue) {
tmpChartNode->parent = tmpLNode->parent; tmpChartNode->gvalue = tmpLNode->gvalue; tmpChartNode->fvalue = tmpLNode->fvalue; }
free(tmpLNode);
}
//状态在closed表中已经存在
else if(inLink(tmpLNode , closed , tmpChartNode , thePreNode)) {
addSpringNode(tmpNode , tmpChartNode);
if(tmpLNode->gvalue < tmpChartNode->gvalue) {
PNode commu;
tmpChartNode->parent = tmpLNode->parent; tmpChartNode->gvalue = tmpLNode->gvalue; tmpChartNode->fvalue = tmpLNode->fvalue; freeSpringLink(tmpChartNode->child);
tmpChartNode->child = NULL;
popNode(thePreNode , commu);
addAscNode(open , commu);
}
free(tmpLNode);
}
//新的状态即此状态既不在open表中也不在closed表中 else
{
addSpringNode(tmpNode , tmpLNode);
addAscNode(open , tmpLNode);
}
}
}
//目标可达的话，输出最佳的路径
- 22 -
if(getGoal)
{
cout << endl;
cout << "最佳路径长度为：" << tmpNode->gvalue << endl; cout << "最佳路径为：" <<endl;
outputBestRoad(tmpNode);
}
//释放结点所占的内存
freeLink(open);
freeLink(closed);
getch();
}
int main()
{
AStar();
return 0;
}
- 23 -