八數(shù)碼問題(共22頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上課 程 論 文論文名稱八數(shù)碼問題姓 名班 級學(xué) 號課程名稱人工智能任課教師學(xué) 期所在院系專心-專注-專業(yè)摘 要八數(shù)碼問題也稱為九宮問題。在3×3的棋盤，擺有八個棋子，每個棋子上標(biāo)有1至8的某一數(shù)字，不同棋子上標(biāo)的數(shù)字不相同。棋盤上還有一個空格，與空格相鄰的棋子可以移到空格中。要求解決的問題是：給出一個初始狀態(tài)和一個目標(biāo)狀態(tài)，找出一種從初始轉(zhuǎn)變成目標(biāo)狀態(tài)的移動棋子步數(shù)最少的移動步驟。所謂問題的一個狀態(tài)就是棋子在棋盤上的一種擺法。棋子移動后，狀態(tài)就會發(fā)生改變。解八數(shù)碼問題實(shí)際上就是找出從初始狀態(tài)到達(dá)目標(biāo)狀態(tài)所經(jīng)過的一系列中間過渡狀態(tài)。 八數(shù)碼問題一般使用搜索法來

2、解。 搜索法有廣度優(yōu)先搜索法、深度優(yōu)先搜索法、A*算法等。這里詳細(xì)講述A*算法。關(guān)鍵詞:八數(shù)碼問題；空間狀態(tài)；搜索法；A*算法一、 實(shí)驗(yàn)?zāi)康睦斫獠⑹煜ふ莆誂*算法。二、 實(shí)驗(yàn)內(nèi)容九宮格中有8個數(shù)碼，其中只有一個空，規(guī)則是只能把一個數(shù)碼移動到空的格子中，要求從一個初始狀態(tài)移動到一個目標(biāo)狀態(tài)所要花費(fèi)的最少步數(shù)三、問題的搜索形式描述（4要素） 初始狀態(tài)：8個數(shù)字將牌和空格在九宮格棋盤上的所有格局組成了問題的狀態(tài)空間。其中，狀態(tài)空間中的任一種狀態(tài)都可以作為初始狀態(tài)。后繼函數(shù)：通過移動空格（上、下、左、右）和周圍的任一棋子一次，到達(dá)新的合法狀態(tài)。目標(biāo)測試：比較當(dāng)前狀態(tài)和目標(biāo)狀態(tài)的格局是否一致。路徑消耗：

3、每一步的耗散值為1，因此整個路徑的耗散值是從起始狀態(tài)到目標(biāo)狀態(tài)的棋子移動的總步數(shù)。四、解決方案介紹（原理） 常用的狀態(tài)空間搜索有深度優(yōu)先和廣度優(yōu)先。廣度優(yōu)先是從初始狀態(tài)一層一層向下找，直到找到目標(biāo)為止。深度優(yōu)先是按照一定的順序前查找完一個分支，再查找另一個分支，以至找到目標(biāo)為止。 廣度和深度優(yōu)先搜索有一個很大的缺陷就是他們都是在一個給定的狀態(tài)空間中窮舉。這在狀態(tài)空間不大的情況下是很合適的算法，可是當(dāng)狀態(tài)空間十分大，且不預(yù)測的情況下就不可取了。由于八數(shù)碼問題狀態(tài)空間共有9!個狀態(tài)，對于八數(shù)碼問題如果選定了初始狀態(tài)和目標(biāo)狀態(tài)，有9!/2個狀態(tài)要搜索，考慮到時間和空間的限制，在這里采用A*算法作為搜

4、索策略。在這里就要用到啟發(fā)式搜索啟發(fā)中的估價是用估價函數(shù)表示的，如：f(n) = g(n) + h(n)其中f(n) 是節(jié)點(diǎn)n的估價函數(shù)，g(n)是在狀態(tài)空間中從初始節(jié)點(diǎn)到n節(jié)點(diǎn)的實(shí)際代價，h(n)是從n到目標(biāo)節(jié)點(diǎn)最佳路徑的估計(jì)代價。 在此八數(shù)碼問題中，顯然g(n)就是從初始狀態(tài)變換到當(dāng)前狀態(tài)所移動的步數(shù)，估計(jì)函數(shù)f(n)我們就可采用當(dāng)前狀態(tài)各個數(shù)字牌不在目標(biāo)狀態(tài)未知的個數(shù)，即錯位數(shù)。 五、算法介紹5.1 搜索算法一般介紹在本實(shí)驗(yàn)中使用A*算法求解。A*搜索是一種效的搜索算法，它把到達(dá)節(jié)點(diǎn)的耗散g(n)和從該節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的消耗h(n)結(jié)合起來對節(jié)點(diǎn)進(jìn)行評價：f(n)=g(n)+h(n)。當(dāng)h

5、(n)是可采納時，使用Tree-Search的A*算法將是最優(yōu)的。5.2 算法偽代碼算法的功能：產(chǎn)生8數(shù)碼問題的解(由初始狀態(tài)到達(dá)目標(biāo)狀態(tài)的過程）輸入：初始狀態(tài)，目標(biāo)狀態(tài)輸出：從初始狀態(tài)到目標(biāo)狀態(tài)的一系列過程算法描述：Begin：讀入初始狀態(tài)和目標(biāo)狀態(tài)，并計(jì)算初始狀態(tài)評價函數(shù)值f；根據(jù)初始狀態(tài)和目標(biāo)狀態(tài)，判斷問題是否可解；If(問題可解)把初始狀態(tài)假如open表中；While（未找到解&&狀態(tài)表非空）在open表中找到評價值最小的節(jié)點(diǎn)，作為當(dāng)前結(jié)點(diǎn)；判斷當(dāng)前結(jié)點(diǎn)狀態(tài)和目標(biāo)狀態(tài)是否一致，若一致，跳出循環(huán)；否則跳轉(zhuǎn)到；對當(dāng)前結(jié)點(diǎn)，分別按照上、下、左、右方向移動空格位置來擴(kuò)展新的狀態(tài)

6、結(jié)點(diǎn)，并計(jì)算新擴(kuò)展結(jié)點(diǎn)的評價值f并記錄其父節(jié)點(diǎn)；對于新擴(kuò)展的狀態(tài)結(jié)點(diǎn)，判斷其是否重復(fù)，若不重復(fù)，把其加入到open表中；把當(dāng)前結(jié)點(diǎn)從open表中移除；End whileEnd if輸出結(jié)果；End開始算法流程如下：讀入棋局初始狀態(tài)否o是否可解是o初始狀態(tài)加入open表在open表中找到評價值最小的節(jié)點(diǎn)，作為當(dāng)前結(jié)點(diǎn)是o是目標(biāo)節(jié)點(diǎn)否o擴(kuò)展新狀態(tài)，把不重復(fù)的新狀態(tài)加入open表中當(dāng)前結(jié)點(diǎn)從open表移除輸出結(jié)果結(jié)束六、 算法實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)static int target9=1,2,3,4,5,6,7,8,0; 全局靜態(tài)變量，表示目標(biāo)狀態(tài)class eight_numprivate:int num

7、9; 定義八數(shù)碼的初始狀態(tài)int not_in_position_num; 定義不在正確位置八數(shù)碼的個數(shù)int deapth; 定義了搜索的深度int eva_function; 評價函數(shù)的值，每次選取最小的進(jìn)行擴(kuò)展public:eight_num* parent; 指向節(jié)點(diǎn)的父節(jié)點(diǎn)eight_num* leaf_next; 指向open表的下一個節(jié)點(diǎn)eight_num* leaf_pre; 指向open 表的前一個節(jié)點(diǎn) 初始狀態(tài)的構(gòu)造函數(shù) eight_num(int init_num9); eight_num(int num1,int num2,int num3,int num4,int n

8、um5,int num6,int num7,int num8,int num9)eight_num(void) 計(jì)算啟發(fā)函數(shù)g(n)的值void eight_num:cul_para(void)顯示當(dāng)前節(jié)點(diǎn)的狀態(tài)void eight_num:show()復(fù)制當(dāng)前節(jié)點(diǎn)狀態(tài)到一個另數(shù)組中void eight_num:get_numbers_to(int other_num9)設(shè)置當(dāng)前節(jié)點(diǎn)狀態(tài)(欲設(shè)置的狀態(tài)記錄的other數(shù)組中)void eight_num:set_num(int other_num9)eight_num& eight_num:operator=(eight_num&

9、; another_8num)eight_num& eight_num:operator=(int other_num9)int eight_num:operator=(eight_num& another_8num)int eight_num:operator=(int other_num9)空格向上移int move_up(int num9)空格向下移int move_down(int num9)空格向左移int move_left(int num9)空格向右移int move_right(int num9)判斷可否解出int icansolve(int num9,int

10、target9)判斷有無重復(fù)int existed(int num9,eight_num *where)尋找估價函數(shù)最小的葉子節(jié)點(diǎn)eight_num* find_OK_leaf(eight_num* start)七、結(jié)果分析目標(biāo)狀態(tài)默認(rèn)為1 2 3 4 5 6 7 8 0a) 初始狀態(tài)是1 2 3 4 5 6 7 0 8，用h作為啟發(fā)函數(shù)結(jié)果都如下：b)初始狀態(tài)是1 2 3 4 5 6 0 7 8，用h作為啟發(fā)函數(shù)結(jié)果都如下：b)初始狀態(tài)是 2 1 3 4 5 6 7 8 0，用h作為啟發(fā)函數(shù)結(jié)果都如下：八、實(shí)驗(yàn)體會這次試驗(yàn)讓我更加深入了解了什么是人工智能，讓我了解了人工智能的作用以及含義和人

11、工智能的使用范圍以及對于我們未來生活得作用的廣大。用機(jī)器語言解決實(shí)際問題的，提高了動手能力。九、參考文獻(xiàn)1 Artificial IntelligenceA Modern Approach. Stuart Russell, Peter Norvig. 人民郵電出版社,20042 Artificial Intelligence, Rob Callan. 電子工業(yè)出版社,2004附錄源代碼及其注釋#include "iostream.h" /輸入輸出流#include <time.h> /頭文件#include <stdio.h> /頭文件#includ

12、e <dos.h> /頭文件#include <conio.h> /頭文件static int target9= 1,2,3,4,5,6,7,8,0; /全局靜態(tài)變量，表示目標(biāo)狀態(tài)/class definitionclass eight_num /定義類private:int num9; /定義八數(shù)碼的初始狀態(tài)int not_in_position_num; /定義不在正確位置八數(shù)碼的個數(shù)int deapth; /定義了搜索的深度int eva_function; /評價函數(shù)的值，每次選取最小的進(jìn)行擴(kuò)展public:eight_num* parent; /指向節(jié)點(diǎn)的父節(jié)

13、點(diǎn)eight_num* leaf_next; /指向open表的下一個節(jié)點(diǎn)eight_num* leaf_pre; /指向open 表的前一個節(jié)點(diǎn) eight_num(int init_num9); /初始狀態(tài)的構(gòu)造函數(shù)eight_num(int num1,int num2,int num3,int num4,int num5,int num6,int num7,int num8,int num9) /定義目標(biāo)狀態(tài)num0=num1; /定義數(shù)組第一個元素num1=num2; /定義數(shù)組第二個元素num2=num3; /定義數(shù)組第三個元素num3=num4; /定義數(shù)組第四個元素num4=nu

14、m5; /定義數(shù)組第五個元素num5=num6; /定義數(shù)組第六個元素num6=num7; /定義數(shù)組第七個元素num7=num8; /定義數(shù)組第八個元素num8=num9; /定義數(shù)組第九個元素eight_num(void) /計(jì)算啟發(fā)函數(shù)g(n)的值for (int i=0;i<9;i+) / for循環(huán)語句numi=i; void cul_para(void); /顯示當(dāng)前節(jié)點(diǎn)狀態(tài) void get_numbers_to(int other_num9); /設(shè)置當(dāng)前節(jié)點(diǎn)狀態(tài)int get_nipn(void) /定義返回類型return not_in_position_num; /

15、返回int get_deapth(void) /定義深度return deapth; /返回深度int get_evafun(void) /定義return eva_function; /返回void set_num(int other_num9); /定義返回值 void show(void); /定義狀態(tài)eight_num& operator=(eight_num&); /設(shè)置當(dāng)前節(jié)點(diǎn)狀態(tài)eight_num& operator=(int other_num9); /設(shè)置當(dāng)前節(jié)點(diǎn)狀態(tài)int operator=(eight_num&); /設(shè)置當(dāng)前節(jié)點(diǎn)狀態(tài)int

16、 operator=(int other_num9); /設(shè)置當(dāng)前節(jié)點(diǎn)狀態(tài);void eight_num:cul_para(void) /顯示當(dāng)前節(jié)點(diǎn)的狀態(tài)int i; /輸入iint temp_nipn=0; /定義初始節(jié)點(diǎn)for (i=0;i<9;i+) / for循環(huán)if (numi!=targeti) /判斷是否可解temp_nipn+; /移向下一個節(jié)點(diǎn)not_in_position_num=temp_nipn; /加入nipnif (this->parent=NULL) /判斷deapth=0; /深度0else /另一種情況deapth=this->parent

17、->deapth+1; /非底層eva_function=not_in_position_num+deapth; /構(gòu)造函數(shù)1eight_num:eight_num(int init_num9) /定義目前狀態(tài)for (int i=0;i<9;i+) /循環(huán)numi=init_numi; /輸入數(shù)組 /顯示當(dāng)前節(jié)點(diǎn)的狀態(tài)void eight_num:show() /輸入cout<<num0;/ /輸入數(shù)組中第一個數(shù)字cout<<" " /空格cout<<num1; /輸入數(shù)組中第二個數(shù)字cout<<" &

18、quot; /空格 cout<<num2; /輸入數(shù)組中第三個數(shù)字cout<<"n" /空格cout<<num3; /輸入數(shù)組中第四個數(shù)字cout<<" " /空格cout<<num4; /輸入數(shù)組中第五個數(shù)字cout<<" " /空格cout<<num5; /輸入數(shù)組中第六個數(shù)字cout<<"n" /空格cout<<num6; /輸入數(shù)組中第七個數(shù)字cout<<" " /空格

19、cout<<num7; /輸入數(shù)組中第八個數(shù)字cout<<" " /空格cout<<num8; /輸入數(shù)組中第九個數(shù)字cout<<"n" /復(fù)制當(dāng)前節(jié)點(diǎn)狀態(tài)到一個另數(shù)組中void eight_num:get_numbers_to(int other_num9)for (int i=0;i<9;i+) /循環(huán)other_numi=numi; /設(shè)置當(dāng)前節(jié)點(diǎn)狀態(tài)(欲設(shè)置的狀態(tài)記錄的other數(shù)組中)void eight_num:set_num(int other_num9)for (int i=0;i&l

20、t;9;i+) /循環(huán)numi=other_numi; /設(shè)置當(dāng)前節(jié)點(diǎn)狀態(tài)(欲設(shè)置的狀態(tài)記錄的other數(shù)組中)eight_num& eight_num:operator=(eight_num& another_8num)/for (int i=0;i<9;i+) /循環(huán)numi=another_8num.numi; /移動not_in_position_num=another_8num.not_in_position_num; /deapth=another_8num.deapth+1; /到下一層eva_function=not_in_position_num+dea

21、pth; /到下一層return *this; /返回目前狀態(tài)eight_num& eight_num:operator=(int other_num9)for (int i=0;i<9;i+) /循環(huán)numi=other_numi; /賦值return *this; /返回目前狀態(tài)int eight_num:operator=(eight_num& another_8num)int match=1; for (int i=0;i<9;i+) /循環(huán)if(numi!=another_8num.numi) /判斷當(dāng)前狀態(tài)與目標(biāo)狀態(tài)是否一致match=0; break;

22、 /跳出循環(huán) if (match=0) /盤點(diǎn)一致不一致return 0; /一致else return 1; /不一致int eight_num:operator=(int other_num9)int match=1; /目前狀態(tài)與目標(biāo)狀態(tài)不一致 for (int i=0;i<9;i+) /循環(huán) if(numi!=other_numi) /判斷目前狀態(tài)與目標(biāo)狀態(tài)是否一致match=0; /一致break; /跳出循環(huán)if (match=0) /一致return 0; /返回0else return 1; /返回1 int move_up(int num9) /空格向上移for (in

23、t i=0;i<9;i+) /循環(huán)if (numi=0) /判斷break; /跳出循環(huán)if (i<3) /判斷return 0; /返回elsenumi=numi-3; /將第（i-3）賦值給第（i）個numi-3=0; /為（i-3）賦值return 1; /返回 /空格向下移int move_down(int num9) /向下移動for (int i=0;i<9;i+) /循環(huán)if (numi=0) /判斷break; /跳出循環(huán)if (i>5) /判斷return 0; /返回elsenumi=numi+3; /將第（i+3）的值賦給第（i）個numi+3=0

24、; /第（i+3）賦值return 1; /返回int move_left(int num9) /空格向左移for (int i=0;i<9;i+) /循環(huán)if (numi=0) /判斷break; /跳出循環(huán)if (i=0|i=3|i=6) /判斷return 0; /返回elsenumi=numi-1; /賦值numi-1=0; /賦值return 1; /返回int move_right(int num9) /空格向右移for (int i=0;i<9;i+) /循環(huán)if (numi=0) /判斷break; /跳出循環(huán)if (i=2|i=5|i=8) /判斷return 0

25、; /返回elsenumi=numi+1; /賦值numi+1=0; /賦值return 1; /返回int icansolve(int num9,int target9) /判斷可否解出int i,j; /定義兩個整型變量int count_num,count_target; /定義總步數(shù)，目標(biāo)數(shù)for (i=0;i<9;i+) /循環(huán)for (j=0;j<i;j+) /循環(huán)if(numj<numi&&numj!=0) /判斷狀態(tài)數(shù)count_num+; /狀態(tài)數(shù)自加if(targetj<targeti&&targetj!=0) /判斷

26、評價數(shù)count_target+; /評價數(shù)自加if(count_num+count_target)%2 = 0) /判斷return 1; /返回elsereturn 0; /返回int existed(int num9,eight_num *where) /判斷有無重復(fù)eight_num *p; /指向父節(jié)點(diǎn)for(p=where;p!=NULL;p=p->parent) /循環(huán)if(*p=num) /判斷return 1; /返回return 0; /返回eight_num* find_OK_leaf(eight_num* start) /尋找估價函數(shù)最小的葉子節(jié)點(diǎn)eight_nu

27、m *p,*OK; /指向父節(jié)點(diǎn)p=OK=start; /父節(jié)點(diǎn)開始int min=start->get_evafun(); for(p=start;p!=NULL;p=p->leaf_next) /從父節(jié)點(diǎn)向下一個節(jié)點(diǎn)循環(huán)if(min>p->get_evafun() /判斷OK=p; /節(jié)點(diǎn)賦值min=p->get_evafun(); /指向下一個節(jié)點(diǎn)return OK; /返回int main(void) /主函數(shù)開始double time; /定義雙精度clock_t Start,Finish;int memery_used=0,step=0;int num

28、9; /定義整型數(shù)組int flag=0;/是否輸入錯誤標(biāo)志，1表示輸入錯誤int bingo=0;/是否查找成功標(biāo)志，1表示成功int i,j; /定義整型變量cout<<"Please input the number(0 for the blank):n" /鍵盤輸入數(shù)字for (i=0;i<9;i+) /循環(huán)flag=0; cin>>numi; /輸入for(j=0;j<i;j+) /循環(huán)if(numi=numj) /判斷flag=1; /輸入錯誤if (numi<0|numi>8|flag=1) /判斷i-;cout

29、<<"Illegle number!tReinput!n" /輸出eight_num S(num),Target(target); /目標(biāo)狀態(tài)S.parent=S.leaf_next=S.leaf_pre=NULL; /父節(jié)點(diǎn)只想下一層左節(jié)點(diǎn)S.cul_para(); memery_used+; /自加cout<<"Now the initial numbers are:n" /輸出S.show();cout<<"And the Target is:n" /輸出Target.show();if(!i

30、cansolve(num,target) /判斷cout<<"No one can solve it!n" /輸出cin>>i; /輸入return 1; /返回Start=clock( );eight_num *OK_leaf=&S,*leaf_start=&S,*new_8num,*p; /節(jié)點(diǎn)狀態(tài)變化while(OK_leaf!=NULL&&bingo!=1) /判斷OK_leaf=find_OK_leaf(leaf_start); /左節(jié)點(diǎn)賦值if(*OK_leaf=Target) /判斷bingo=1; /查

31、找成功break; /跳出循環(huán)p=OK_leaf->leaf_pre; /左節(jié)點(diǎn)作為父節(jié)點(diǎn)OK_leaf->get_numbers_to(num); /節(jié)點(diǎn)狀態(tài)if(move_up(num)&&!existed(num,OK_leaf) /判斷new_8num=new eight_num; /新的狀態(tài)new_8num->set_num(num); /指向評價值new_8num->parent=OK_leaf; /指向父節(jié)點(diǎn)new_8num->cul_para(); new_8num->leaf_pre=p; /指向左節(jié)點(diǎn)if(p=NULL)

32、/判斷l(xiāng)eaf_start=new_8num; /新的狀態(tài)是否與目標(biāo)狀態(tài)一致elsep->leaf_next=new_8num; /指向下一節(jié)點(diǎn)p=new_8num; /指針賦值memery_used+; /自加OK_leaf->get_numbers_to(num); /指針指向if(move_down(num)&&!existed(num,OK_leaf) /判斷new_8num=new eight_num; /新的狀態(tài)new_8num->set_num(num); /指向評價值new_8num->parent=OK_leaf; /指向父節(jié)點(diǎn)new_

33、8num->cul_para();new_8num->leaf_pre=p; /指向左節(jié)點(diǎn)if(p=NULL) /判斷節(jié)點(diǎn)是否為空leaf_start=new_8num; /新的狀態(tài)是否與目標(biāo)狀態(tài)一致elsep->leaf_next=new_8num; /指向下一節(jié)點(diǎn)p=new_8num; /指針賦值memery_used+; /自加OK_leaf->get_numbers_to(num); /指針指向if(move_left(num)&&!existed(num,OK_leaf) /判斷new_8num=new eight_num; /新的狀態(tài)new_8num->set_num(num); /指向評價值new_8num->parent=OK_leaf; /指向父節(jié)點(diǎn)new_8num->cul_para();new_8num->leaf_pre=p; /指向左節(jié)點(diǎn)if(p=NULL) /判斷節(jié)點(diǎn)是否為空leaf_start=new_8n