自己收藏的
觉得很有用
故上传到百度
与大家一起分享！
人工智能课程设计
题目:用A*算法解决8数码问题
学院:信息科学与技术学院
专业:计算机科学与技术
2005年12月
摘 要
本课题以人工智能两大支柱之一的搜索技术中的启发式搜索策略（即通过对向最终结果的逼近作评估来发现问题的解）为出发点
结合人工智能应用及其最新进展
阐述了人工智能搜索原理、启发式搜索算法和启发式函数等内容
本文讨论了各种状态空间搜索策略、启发式推理技术
并且以八数码问题为例着重讨论了各种启发式函数及其特点
分析它们在问题求解时所起的作用
关键词：人工智能
搜索策略
启发式函数
目 录
1. 概述
1.1 八数码问题
1.2 A*算法
1.3 A*算法的一般描述
1.3.1约定
1.3.2算法过程
2. A*算法在VC6.0开发环境下的实现
2.1类
2.1.1 CDisplay类
2.1.2 CMain类
2.1.3 其它类
2. 2数据结构
2.2.1 生成搜索树
3．主要程序代码及注释
4．其它
5. 结束语
参考文献
附件一
附件二
1. 概述
1.1 八数码问题
8数码问题是指在3X3的九宫棋盘上有标号为1～8的8个棋牌,和一个空白位,通过棋牌向空白位移动来改变棋盘布局,如何移动棋牌才能从初使布局到达目标布局.显然解答路径实际上就是一个合法的走步序列
1.2 A*算法
A*算法属于一种启发式搜索,它扩展结点的次序类似于广度优先搜索,但不同的是每生成一个子结点需要计算估价函数F,以估算起始结点的约束经过该结点至达目标结点的最佳路径代价;每当扩展结点时,意是在所有待扩展结点中选择具有最小F值的结点做为扩展对象,以便使搜索尽量沿最有希望的方向进行.A*算法只要求产生问题的全部状态空间的部分结点及关系,就可以求解问题了,搜索效率较高
2.3 A*算法的一般描述
1.3.1约定
S：指示初使状态节点（Note）；G：指示搜索图
OPEN：作为存放待扩展节点的表；SNS：子节点集合
CLOSE：作为存放已被扩展节点的表
Move_First(Open)：指示取Open表首节点作为当前要被扩展的节点n
同时将节点n移到CLOSE表；
F(n) = G(n) + H(n)：评价函数
用于排列节点在OPEN表中的位置
1.3.2算法过程
○1 G:=S; ○2 OPEN := (S), CLOSE := ();
○3 如果OPEN为空则算法失败
○4 n := Move_First(OPEN);
○5 如果n是目标结点
搜索完成
○6 扩展节点n
将非节点n祖先的子节点置于子点子集合SNS中
并插入G
对SNS每个子节点计算F(n,ni)=G(n,ni)+H(ni)
○7 标记与修改指针：
1.把SNS中的
子结点分为三类:全新结点,已出现于OPEN表的结点,已出现于CLOSE表的节点;2.加第一类子节点于OPEN表;3.由评价函数值,选择最优结点,并移动子结点指向父节点的指针,改为指向新父节点
○8 重新排序OPEN表中结点； ○9 返回语句○3
2. A*算法在VC6.0开发环境下的实现
2．1.类（可参见附件）
2.1 .1CDisplay类
由于结果以各种棋盘的布局来表示空白位的移动,因此建立这个类的目的是记录棋盘布局,并指出这个布局是否已经存在,是否正解,是否已扩展(已扩展并不表示是正解,正解一定表示已扩展).同时这个类的对象也是搜索树的节点
2.1.2 CMain类
这个类负责A*算法的全部过程,如:初值与结果的取得,空白位的移动,评价函数值的计算,选择当前最优移动方法,生成下一个棋盘布局,形成搜索树等
2.1.3 其它类
1.CAI3Doc类：VC6.0 AppWizard自动生成
在本程式中负责将CMain类对象的运算结果(搜索树)转换成可显示格式
2.CAI3View类:VC6.0 AppWizard自动生成,在本程序中负责将CAI3Doc类转换好的内容显示
3. CMainFrame类:VC6.0AppWizard自动生成,在本程序中负责异常处理（搜索出错
运算成功等）
4.CAI3App类：VC6.0 AppWizard自动生成,本程序中无特殊使用
5.CPtrList类：在本程式中预定义为List,它的对象用于树（搜索树
结果显示树）的存储
6.CPoint类：在本程式中预定义为Position,它的对象用于表示坐标
2.2数据结构：
在本程序中,棋盘布局以一个3X3的二元数组表示；CDisplay类的对象作为搜索树的节点
搜索树以链表形式存储（可参见附件）
程序流程图与相关说明：
2.2.1 生成搜索树
注一: Op1 ＝ Op2表示将Op2的内容全部复制到Op1中
注二: 标志为解状态的原因是为了找到解图；
标志为某状态为解状态的同时也标记此状态为已扩展
注三：取得空白位的位置在Op2初使化时就已完成
注四：由于G值对于子结点是相同的
因此只要比较H值就相当于比较了F值
3. 主要程序代码及注释
要想得到最优的就需要使用广度优先搜索
九宫的所以排列有９！种
也就是３６２８８０种排法
数据量是非常大的
我使用的广度搜索
需要记住每一个结点的排列形式
要是用数组记录的话会占用很多的内存
我们把数据进行适当的压缩
使用ＤＷＯＲＤ形式保存
压缩形式是每个数字用３位表示
这样就是３×９＝２７个字节
由于８的二进制表示形式１０００
不能用３位表示
我使用了一个小技巧就是将８表示位０００
然后用多出来的５个字表示８所在的位置
就可以用ＤＷＯＲＤ表示了
用移位和或操作将数据逐个移入
比乘法速度要快点
定义了几个结果来存储遍历到了结果和搜索完成后保存最优路
径
类结构如下：
class CNineGird
{
public:
struct PlaceList
{
DWORD Place;
PlaceList* Left;
PlaceList* Right;
};
struct Scanbuf
{
DWORD Place;
int ScanID;
};
struct PathList
{
unsigned char Path[9];
};
private:
PlaceList *m_pPlaceList;
Scanbuf *m_pScanbuf;
RECT m_rResetButton;
RECT m_rAutoButton;
public:
int m_iPathsize;
clock_t m_iTime;
UINT m_iStepCount;
unsigned char m_iTargetChess[9];
unsigned char m_iChess[9];
HWND m_hClientWin;
PathList *m_pPathList;
bool m_bAutoRun;
private:
inline bool AddTree(DWORD place , PlaceList*& parent);
void FreeTree(PlaceList*& parent);
inline void ArrayToDword(unsigned char *array , DWORD & data);
inline void DwordToArray(DWORD data , unsigned char *array);
inline bool MoveChess(unsigned char *array , int way);
bool EstimateUncoil(unsigned char *array);
void GetPath(UINT depth);
public:
void MoveChess(int way);
bool ComputeFeel();
void ActiveShaw(HWND hView);
void DrawGird(HDC hDC , RECT clientrect);
void DrawChess(HDC hDC , RECT clientrect);
void Reset();
void OnButton(POINT pnt , HWND hView);
public:
CNineGird();
~CNineGird();
};
计算随机随机数组使用了vector模板用random_shuffle（
）函数来打乱数组数据
并计算目标结果是什么
代码：
void CNineGird::Reset()
{
if(m_bAutoRun) return;
vector vs;
int i;
for (i = 1 ; i < 9 ; i ++)
vs.push_back(i);
vs.push_back(0);
random_shuffle(vs.begin(), vs.end());
random_shuffle(vs.begin(), vs.end());
for ( i = 0 ; i < 9 ; i ++)
{
m_iChess[i] = vs[i];
}
if (!EstimateUncoil(m_iChess))
{
unsigned char array[9] = {1,2,3,8,0,4,7,6,5};
memcpy(m_iTargetChess , array , 9);
}
else
{
unsigned char array[9] = {1,2,3,4,5,6,7,8,0};
memcpy(m_iTargetChess , array , 9);
}
m_iStepCount = 0;
}
数据压缩函数实现：
inline void CNineGird::ArrayToDword(unsigned char *array , DWORD& data)
{
unsigned char night = 0;
for ( int i = 0 ; i < 9 ; i ++)
{
if (array[i] == 8)
{
night = (unsigned char)i;
break;
}
}
array[night] = 0;
data = 0;
data = (DWORD)((DWORD)array[0] << 29 | (DWORD)array[1] << 26 |
(DWORD)array[2] << 23 | (DWORD)array[3] << 20 |
(DWORD)array[4] << 17 | (DWORD)array[5] << 14 |
(DWORD)array[6] << 11 | (DWORD)array[7] << 8 |
(DWORD)array[8] << 5 | night);
array[night] = 8;
}
解压缩时跟压缩真好相反
解压代码：
inline void CNineGird::DwordToArray(DWORD data , unsigned char *array)
{
unsigned char chtem;
for ( int i = 0 ; i < 9 ; i ++)
{
chtem = (unsigned char)(data >> (32 - (i + 1) * 3) & 0x00000007);
array[i] = chtem;
}
chtem = (unsigned char)(data & 0x0000001F);
array[chtem] = 8;
}
由于可扩展的数据量非常的大
加上我在保存的时候使用的是ＤＷＯＲＤ类型
将每一步数据都记录在一个排序二叉树中
按从小到大从左到有的排列
搜索的时候跟每次搜索将近万次的形式比较快几乎是Ｎ次方倍
把几个在循环
中用到的函数声明为内联函数
并在插入的时候同时搜索插入的数据会不会在树中有重复来加快总体速度
二叉树插入代码：
inline bool CNineGird::AddTree(DWORD place , PlaceList*& parent)
{
if (parent == NULL)
{
parent = new PlaceList();
parent->Left = parent->Right = NULL;
parent->Place = place;
return true;
}
if (parent->Place == place)
return false;
if (parent->Place > place)
{
return AddTree(place , parent->Right);
}
return AddTree(place , parent->Left);
}
移动到空格位的时候
只要计算是否会移动到框外面就可以了
并在移动的时候顺便计算一下是不是已经是目标结果
这是用来给用户手工移动是给与提示用的
代码：
inline bool CNineGird::MoveChess(unsigned char *array , int way)
{
int zero , chang;
bool moveok = false;
for ( zero = 0 ; zero < 9 ; zero ++)
{
if (array[zero] == 0)
break;
}
POINT pnt;
pnt.x = zero % 3;
pnt.y = int(zero / 3);
switch(way)
{
case 0 : //up
if (pnt.y + 1 < 3)
{
chang = (pnt.y + 1) * 3 + pnt.x ;
array[zero] = array[chang];
array[chang] = 0;
moveok = true;
}
break;
case 1 : //down
if (pnt.y - 1 > -1)
{
chang = (pnt.y - 1) * 3 + pnt.x ;
array[zero] = array[chang];
array[chang] = 0;
moveok = true;
}
break;
case 2 : //left
if (pnt.x + 1 < 3)
{
chang = pnt.y * 3 + pnt.x + 1;
array[zero] = array[chang];
array[chang] = 0;
moveok = true;
}
break;
case 3 : //right
if (pnt.x - 1 > -1)
{
chang = pnt.y * 3 + pnt.x - 1;
array[zero] = array[chang];
array[chang] = 0;
moveok = true;
}
break;
}
if (moveok && !m_bAutoRun)
{
m_iStepCount ++ ;
DWORD temp1 ,temp2;
ArrayToDword(array , temp1);
ArrayToDword(m_iTargetChess , temp2);
if (temp1 == temp2)
{
MessageBox(NULL , "搜索完成 恭喜恭喜找到结果！" , "^_^" , 0);
}
}
return moveok;
}
在进行广度搜索时候
将父结点所在的数组索引记录在子结点中了
所以得到目标排列的时候
我们只要从子结点逆向搜索就可以得到最优搜索路径了
用变量m_iPathsize来记录总步数
具体函数代码：
void CNineGird::GetPath(UINT depth)
{
int now = 0 , maxpos = 100 ;
UINT parentid;
if (m_pPathList != NULL)
{
delete[] m_pPathList;
}
m_pPathList = new PathList[maxpos];
parentid = m_pScanbuf[depth].ScanID;
DwordToArray(m_pScanbuf[depth].Place , m_pPathList[++now].Path);
while(parentid != -1)
{
if (now == maxpos)
{
maxpos += 10;
PathList * temlist = new PathList[maxpos];
memcpy(temlist , m_pPathList , sizeof(PathList) * (maxpos - 10));
delete[] m_pPathList;
m_pPathList = temlist;
}
DwordToArray(m_pScanbuf[parentid].Place , m_pPathList[++now].Path);
parentid = m_pScanbuf[parentid].ScanID;
}
m_iPathsize = now;
}
动态排列的演示函数了
为了让主窗体有及时刷新的机会
启动了一个线程在需要主窗体刷新的时候
用Ｓｌｅｅ（ＵＩＮＴ）函数来暂停一下线程就可以了
代码：
unsigned __stdcall MoveChessThread(LPVOID pParam)
{
CNineGird * pGird = (CNineGird *)pParam;
RECT rect;
pGird->m_iStepCount = 0;
::GetClientRect(pGird->m_hClientWin , &rect);
for ( int i = pGird->m_iPathsize ; i > 0 ; i --)
{
memcpy(pGird->m_iChess , pGird->m_pPathList[i].Path , 9);
pGird->m_iStepCount ++;
InvalidateRect( pGird->m_hClientWin , &rect , false);
Sleep(300);
}
char msg[100];
sprintf(msg , "^_^ ! 搞定了!\r\n计算步骤用时%d毫秒" , pGird->m_iTime);
MessageBox(NULL , msg , "~_~" , 0);
pGird->m_bAutoRun = false;
return 0L;
}
重要函数的介绍结束
下面是程序的运行结果和运算结果：
4．其它
改变程序中MaxItem的设定和相关输入方式（主要指对话框）
本程序可以用来计算Maxitem*MaxItem-1数码问题（本程序中MaxItem等于3）
5. 结束语
A*算法在运行过程中,也不可避免的用到了穷举(比如取得空白位的移动方式）
但由于评价函数的存在使A*算法能够减少许多类似于穷举的工作
因此它只求解了问题的全部状态空间中的部分状态
提高了效率和减少了用于处理的空间
另外A*算法是AI的基本算法之一
我们也可以这么说：人工智能的精髓就是穷举
人工智能的关键就是控制策略
通过本课题的探讨
使我对人工智能这一领域有更深的了解和认识
虽然我只是讨论了人工智能的一个核心部分--搜索（主要是基于信息的启发性的搜索）及一个主要应用领域--问题求解和规划（主要针对八数码难题）
本课题旨在讨论八数码难题的启发式函数对其求解过程所起的作用和影响
所用的这六个启发式函数是我结合已有的经典启发式函数和构思新的启发式函数的成果
并且通过自编的程序对它们进行比较、分析和讨论
总结出对于启发式函数的特性及其选择的关键和依据
同时
我还针对八数码难题的特殊性
构想出一套新的解题思路
但由于时间仓促
对于这个设想的启发式函数考虑的还不够成熟
还有待于今后的改进
参考文献
[ 1 ] 陆汝铃
《人工智能》
科学出版社
1996
[ 2 ] 施鹏飞
姚远
《人工智能教程》
上海交通大学出版社
1993
[ 3 ] 蔡自兴、徐光柚
《人工智能及其应用》
清华大学出版社
1996
[ 4 ] 田盛丰
《人工智能原理及应用》
北京理工大学出版社
1993
附件一: 结构与存储格式
CDisplay结构 搜索树的节点结构
状态描述数组
状态位置标记
节点状态
状态是否可解
空白位位置
其它方法
.......
CPtrList链表结构： 搜索树的链式存储表示（虚双箭头线代表链表指针）
对象指针
前结点指针
后结点指针
结点计数值
相关方法......
附件二：CDisplay类
CMain类
CAI3Doc类的关系调用
3