基于广度优先搜索的八数码问题解决方案
开篇：润墨网以专业的文秘视角，为您筛选了一篇基于广度优先搜索的八数码问题解决方案范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
关键词：八数码问题 人工智能 广度优先搜索 VC
中图分类号：TP311.1 文献标识码：B 文章编号：1002-2422(2008)01-0045-02
1 八数码问题
八数码问题也称为九宫问题，类似于平时所玩的拼图游戏，它是在一个3x3的空格中任意放置1-8这8个数及一个空格(如图1)。要求玩家通过空格来移动数据，将这8个数字排列成有序格式(如图2)，这个格式在后文中称为目标格式。移动的规则是：每次只能将与空格(上、下、或左、右)相邻的一个数字平移到空格中。
2 数据结构
定义结点node由以下成员组成：数组a[3][3]存储当前结点中3*3个空格内的数字；4个node指针u，d，l，r分别指向当前结点向上下左右4个方向移动后新成立的结点，若在某个方向上无法移动，则相应的指针指向NULL；指针P指向当前结点的父结点，找到目标结点后可沿着p指针逐层向上生成解决步骤。
typed struet node
{
int a[3][3]；
node*u；
node*d：
node*I：
node*r：
node*p；
void search(node*&h)
{
queue*front，*rear；
queue*qq，*Qtemp，*Qfront；
node*tu，*td，*tl，*tr；
node*np；
int temp；
front=new queue；
front->data=h；front->next=NULL；
rear=front；
Qfront=front；
np=front->data；
while(suec(np)==false)
{
if(np->a[0][0]==O)
{
np->d=NULL；np->r=NULL；
tumnew node；
tcopy(np，tu)；
move_up(tu，0，0)；
if(IsExist(Qfront，tu)==false)
{
np->u=tu；
tu->p=np；
qq=new qucuc；
qq->data=tu；qq->next=NULL；
rear->next=qq；rear=qq；
}
else
{
delete tu：
np->u=NULL；
}
tl=new node；
tcopy(np，tl)：
move_left(tl，0，0)；
if(IsExist(Qfront，tl)==false)
{
np->l=tl；
tl->p=np；
qq=new queue；
qq->data=tl； qq->next=NULL；
rear->next=qq；rear=qq；
Tent++；
}
else
{
delete tl；
np->l=NULL；
}
}
if(np->a[0][1]==0)
{
}
if(np->a[0][2]==0)
{
∥代码略，可参考(0，0)位置上的操作
}
if(np->a[1][0]==0)
{
}
if(np->a[1][1]==0)
{
}
if(np->a[1][2]==o)
{
}
if(np->a[2][0]==0)
{
}
if(np->a[2][1]==0)
{
}
if(np->a[2][2]==0)
{
}
front=front->next；
if(front==NULL)
{
cout
return；
}
npffront->data；
}
while(np)
{
print(np)；
np=np->p；
}
}
结点queue用来组成队列，定义其由以下成员组成：指针data指向的node结点中保存着九宫图的排列及5个指针，指针next指向队列中的下一个结点。
typcdd strum queue
{
node*data；
queue*next；
}；
3 广度优先搜索
广度优先搜索的基本思想是：从初始结点h开始，逐层地对结点进行扩展并考察它是否为目标结点，若不是目标结点，则放入待考察队列中：在第n层的结点没有全部扩展并考察之前，不对第n+1层的结点进行扩展。队列中的结点总是按进入的先后顺序排列，先进入的结点排在前面，后进入的排在后面。其搜索过程如下：
(1)初始化结点h放入队列中，队头指针front=h：
(2)若front==NULL，则问题无解，退出；
(3)取出队头结点front，n=front，front指向队列中的下一个结点：
(4)考察结点n是否为目标结点，若是，则问解求得，退出；
(5)考察结点n在上下左右四个方向上是否可扩展，将其可扩展的子结点放入队尾，然后转步骤2。
以下是采用广度优先搜索方法实现八数码问题求解的程序，在程序中以数字0来代表空格。
4 重要函数
以下是在search()函数中出现的几个重要函数。
heel fluee(node*np)
{
if(np>a[0][0]!=1)retum false；
if(np->a[0][1]!=2)return false；
if(np->a[0][2]!=3)return false；
if(np->a[1][0]!=4)return false；
if(np->a[1][1]!=5)return false；
if(np->a[1][2]!=6)return false；
if(np->8[2][0]!=7)return false；
if(np->a[2][1]l=8)return false；
if(np->a[2][2]!=O)return false；
return true；
}
∥tcopy(node*&t1，node*&t2)：将t1中的数据复制到t2中
void teopy(node*&t1，node*&t2)
{
for(int i=0；i
for(iat j=0；j
t2->a[i][j]=t1->a[i][j]；
}
void move_up(node*&t，int i，int j)
{
int temp=t->a[i][j]；
t->a[i]=t->a[i+1][j]；
t->a[i+1][j]=temp；}
void move_down(node*&t，int i，int j){
}
void move_left(node*at，int i，int j){}
void nlove_right(node*&t，int i，int j){}
heel IsExist(queue*Qfront，node*t){
queue*p；
p=Qraont；
while(p){
if((p->data->a[0][0]==t->a[O][0])&&(p->data->a[0][1]==t->a[0]
[1])&&(p->data->a[0][2]-t->a[0][2])&&
(p->data->a[1][0]==t->a[1][0])&&(p->data->a[1][1]==t->a[1][1])
&&(p->data->a[1][2]==t->a[1][2])&&
(p->data->a[2][0]==t->a[2][0])&&(p->data->a[2][1]==t->a[2][1])
&&(p->data->a[2][2]==t->a[2][2]))
return true；
p=p->next；
}
return false；
}
5 结束语
采用广度优先搜索方法求解八数码问题的方法，可保证所得到的解决方案具有最优性，同时，在搜索过程中加入了检复结点的功能可大大降低需考察的结点数，加快程序运行速度。