基于廣度優(yōu)先搜索的八數(shù)碼問題解決方案

摘要：介紹了一種基于廣度優(yōu)先搜索的八數(shù)碼問題解決方案。

關(guān)鍵詞：八數(shù)碼問題 人工智能 廣度優(yōu)先搜索 VC

中圖分類號：TP311.1 文獻(xiàn)標(biāo)識碼：B 文章編號：1002-2422(2008)01-0045-02

1 八數(shù)碼問題

八數(shù)碼問題也稱為九宮問題，類似于平時所玩的拼圖游戲，它是在一個3x3的空格中任意放置1-8這8個數(shù)及一個空格(如圖1)。要求玩家通過空格來移動數(shù)據(jù)，將這8個數(shù)字排列成有序格式(如圖2)，這個格式在后文中稱為目標(biāo)格式。移動的規(guī)則是：每次只能將與空格(上、下、或左、右)相鄰的一個數(shù)字平移到空格中。

2 數(shù)據(jù)結(jié)構(gòu)

定義結(jié)點(diǎn)node由以下成員組成：數(shù)組a[3][3]存儲當(dāng)前結(jié)點(diǎn)中3*3個空格內(nèi)的數(shù)字；4個node指針u，d，l，r分別指向當(dāng)前結(jié)點(diǎn)向上下左右4個方向移動后新成立的結(jié)點(diǎn)，若在某個方向上無法移動，則相應(yīng)的指針指向NULL；指針P指向當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)，找到目標(biāo)結(jié)點(diǎn)后可沿著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)==1)

{

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)==1)

{

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)==1)

{

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；

}

}

結(jié)點(diǎn)queue用來組成隊(duì)列，定義其由以下成員組成：指針data指向的node結(jié)點(diǎn)中保存著九宮圖的排列及5個指針，指針next指向隊(duì)列中的下一個結(jié)點(diǎn)。

typcdd strum queue

{

node*data；

queue*next；

}；

3 廣度優(yōu)先搜索

廣度優(yōu)先搜索的基本思想是：從初始結(jié)點(diǎn)h開始，逐層地對結(jié)點(diǎn)進(jìn)行擴(kuò)展并考察它是否為目標(biāo)結(jié)點(diǎn)，若不是目標(biāo)結(jié)點(diǎn)，則放入待考察隊(duì)列中：在第n層的結(jié)點(diǎn)沒有全部擴(kuò)展并考察之前，不對第n+1層的結(jié)點(diǎn)進(jìn)行擴(kuò)展。隊(duì)列中的結(jié)點(diǎn)總是按進(jìn)入的先后順序排列，先進(jìn)入的結(jié)點(diǎn)排在前面，后進(jìn)入的排在后面。其搜索過程如下：

(1)初始化結(jié)點(diǎn)h放入隊(duì)列中，隊(duì)頭指針front=h：

(2)若front==NULL，則問題無解，退出；

(3)取出隊(duì)頭結(jié)點(diǎn)front，n=front，front指向隊(duì)列中的下一個結(jié)點(diǎn)：

(4)考察結(jié)點(diǎn)n是否為目標(biāo)結(jié)點(diǎn)，若是，則問解求得，退出；

(5)考察結(jié)點(diǎn)n在上下左右四個方向上是否可擴(kuò)展，將其可擴(kuò)展的子結(jié)點(diǎn)放入隊(duì)尾，然后轉(zhuǎn)步驟2。

以下是采用廣度優(yōu)先搜索方法實(shí)現(xiàn)八數(shù)碼問題求解的程序，在程序中以數(shù)字0來代表空格。

4 重要函數(shù)

以下是在search()函數(shù)中出現(xiàn)的幾個重要函數(shù)。

heel fluee(node*np)

{

if(np>a[0][0]!=1)retum 1；

if(np->a[0][1]!=2)return 1；

if(np->a[0][2]!=3)return 1；

if(np->a[1][0]!=4)return 1；

if(np->a[1][1]!=5)return 1；

if(np->a[1][2]!=6)return 1；

if(np->8[2][0]!=7)return 1；

if(np->a[2][1]l=8)return 1；

if(np->a[2][2]!=O)return 1；

return true；

}

∥tcopy(node*t1，node*t2)：將t1中的數(shù)據(jù)復(fù)制到t2中

void teopy(node*t1，node*t2)

{

for(int i=0；i<3；i++)

for(iat j=0；j<3；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 1；

}

5 結(jié)束語

采用廣度優(yōu)先搜索方法求解八數(shù)碼問題的方法，可保證所得到的解決方案具有最優(yōu)性，同時，在搜索過程中加入了檢查重復(fù)結(jié)點(diǎn)的功能可大大降低需考察的結(jié)點(diǎn)數(shù)，加快程序運(yùn)行速度。