人工智能實(shí)驗(yàn) 八數(shù)碼

實(shí)驗(yàn)一圖搜索策略之八數(shù)碼問(wèn)題1．實(shí)驗(yàn)?zāi)康?1)加深對(duì)各種圖搜索策略概念的理解；(2)進(jìn)一步了解啟發(fā)式搜索、α-β剪枝等概念；(3)比較并分析各種圖搜索策略的實(shí)質(zhì)。2.實(shí)驗(yàn)設(shè)計(jì)八數(shù)碼游戲（八數(shù)碼問(wèn)題）描述為：在3×3組成的九宮格棋盤(pán)上，擺有八個(gè)將牌，每一個(gè)將牌都刻有1-8八個(gè)數(shù)碼中的某一個(gè)數(shù)碼。棋盤(pán)中留有一個(gè)空格，允許其周?chē)哪骋粋€(gè)將牌向空格移動(dòng)，這樣通過(guò)移動(dòng)將牌就可以不斷改變將牌的布局。這種游戲求解的問(wèn)題是：給定一種初始的將牌布局或結(jié)構(gòu)（稱(chēng)初始狀態(tài)）和一個(gè)目標(biāo)的布局（稱(chēng)目標(biāo)狀態(tài)），問(wèn)如何移動(dòng)將牌，實(shí)現(xiàn)從初始狀態(tài)到目標(biāo)狀態(tài)的轉(zhuǎn)變。初始狀態(tài)： 8個(gè)數(shù)字將牌和空格在九宮格棋盤(pán)上的所有格局組成了問(wèn)題的狀態(tài)空間。其中，狀態(tài)空間中的任一種狀態(tài)都可以作為初始狀態(tài)。后繼函數(shù)： 通過(guò)移動(dòng)空格（上、下、左、右）和周?chē)娜我黄遄右淮危竭_(dá)新的合法狀態(tài)。目標(biāo)測(cè)試： 比較當(dāng)前狀態(tài)和目標(biāo)狀態(tài)的格局是否一致。路徑消耗： 每一步的耗散值為1，因此整個(gè)路徑的耗散值是從起始狀態(tài)到目標(biāo)狀態(tài)的棋子移動(dòng)的總步數(shù)。其中啟發(fā)式搜索是在狀態(tài)空間中的搜索對(duì)每一個(gè)搜索的位置進(jìn)行評(píng)估，得到最好的位置，再?gòu)倪@個(gè)位置進(jìn)行搜索直到目標(biāo)。這樣可以省略大量無(wú)畏的搜索路徑，提到了效率。在啟發(fā)式搜索中，對(duì)位置的估價(jià)是十分重要的。采用了不同的估價(jià)可以有不同的效果。啟發(fā)中的估價(jià)是用估價(jià)函數(shù)表示的，如：f(n)=g(n)+h(n)

其中f(n)是節(jié)點(diǎn)n的估價(jià)函數(shù)，g(n)是在狀態(tài)空間中從初始節(jié)點(diǎn)到n節(jié)點(diǎn)的實(shí)際代價(jià)，h(n)是從n到目標(biāo)節(jié)點(diǎn)最佳路徑的估計(jì)代價(jià)。在此八數(shù)碼問(wèn)題中，顯然g(n)就是從初始狀態(tài)變換到當(dāng)前狀態(tài)所移動(dòng)的步數(shù)，估計(jì)函數(shù)f(n)我們就可采用當(dāng)前狀態(tài)各個(gè)數(shù)字牌不在目標(biāo)狀態(tài)未知的個(gè)數(shù)，即錯(cuò)位數(shù)。算法流程圖如下讀入棋局初始狀態(tài)讀入棋局初始狀態(tài)否o是否可解否o是否可解是o初始狀態(tài)加入open表是o初始狀態(tài)加入open表在open表中找到評(píng)價(jià)值最小的節(jié)點(diǎn)，作為當(dāng)前結(jié)點(diǎn)在open表中找到評(píng)價(jià)值最小的節(jié)點(diǎn)，作為當(dāng)前結(jié)點(diǎn)是o是目標(biāo)節(jié)點(diǎn)是o是目標(biāo)節(jié)點(diǎn)否o否o擴(kuò)展新?tīng)顟B(tài)，把不重復(fù)的新?tīng)顟B(tài)加入open表中擴(kuò)展新?tīng)顟B(tài)，把不重復(fù)的新?tīng)顟B(tài)加入open表中當(dāng)前結(jié)點(diǎn)從open表移除當(dāng)前結(jié)點(diǎn)從open表移除輸出結(jié)果輸出結(jié)果結(jié)束結(jié)束3.實(shí)驗(yàn)內(nèi)容和步驟實(shí)驗(yàn)的數(shù)據(jù)結(jié)構(gòu)staticinttarget[9]={1,2,3,8,0,4,7,6,5};全局靜態(tài)變量，表示目標(biāo)狀態(tài)classeight_num{private: intnum[9];定義八數(shù)碼的初始狀態(tài) intnot_in_position_num;定義不在正確位置八數(shù)碼的個(gè)數(shù) intdeapth;定義了搜索的深度 inteva_function;評(píng)價(jià)函數(shù)的值，每次選取最小的進(jìn)行擴(kuò)展public: eight_num*parent;指向節(jié)點(diǎn)的父節(jié)點(diǎn) eight_num*leaf_next;指向open表的下一個(gè)節(jié)點(diǎn) eight_num*leaf_pre;指向open表的前一個(gè)節(jié)點(diǎn)初始狀態(tài)的構(gòu)造函數(shù)eight_num(intinit_num[9]);eight_num(intnum1,intnum2,intnum3,intnum4,intnum5,intnum6,intnum7,intnum8,intnum9){}eight_num(void){}計(jì)算啟發(fā)函數(shù)g(n)的值voideight_num::cul_para(void){}顯示當(dāng)前節(jié)點(diǎn)的狀態(tài)voideight_num::show(){}復(fù)制當(dāng)前節(jié)點(diǎn)狀態(tài)到一個(gè)另數(shù)組中voideight_num::get_numbers_to(intother_num[9]){}設(shè)置當(dāng)前節(jié)點(diǎn)狀態(tài)(欲設(shè)置的狀態(tài)記錄的other數(shù)組中)voideight_num::set_num(intother_num[9]){}eight_num&eight_num::operator=(eight_num&another_8num){}eight_num&eight_num::operator=(intother_num[9]){}inteight_num::operator==(eight_num&another_8num){}inteight_num::operator==(intother_num[9]){}空格向上移intmove_up(intnum[9]){}空格向下移intmove_down(intnum[9]){}空格向左移intmove_left(intnum[9]){}空格向右移intmove_right(intnum[9]){}判斷可否解出inticansolve(intnum[9],inttarget[9]){}判斷有無(wú)重復(fù)intexisted(intnum[9],eight_num*where){}尋找估價(jià)函數(shù)最小的葉子節(jié)點(diǎn)eight_num*find_OK_leaf(eight_num*start){}4.實(shí)驗(yàn)結(jié)果設(shè)置初始狀態(tài)為231548076，結(jié)束狀態(tài)為123567804，則可以輸出以下結(jié)果?？梢?jiàn)總共花費(fèi)步數(shù)23步。而當(dāng)結(jié)束狀態(tài)為134267580，初始狀態(tài)為325689017時(shí)，該問(wèn)題不存在可行解。輸出結(jié)果如圖5.實(shí)驗(yàn)心得第一次上機(jī)題目相對(duì)而言還是較簡(jiǎn)單的，只不過(guò)由于之前比較忙，忙于考試等，沒(méi)有能夠好好的準(zhǔn)備?？偟膩?lái)說(shuō)按照課本上啟發(fā)函數(shù)的思路來(lái)設(shè)計(jì)并不難，不過(guò)對(duì)于數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)仍然存在很大的問(wèn)題，看來(lái)自己的基礎(chǔ)沒(méi)打好。接下來(lái)的實(shí)驗(yàn)需要繼續(xù)努力。各種搜索方式的比較：廣度優(yōu)先是從初始狀態(tài)一層一層向下找，直到找到目標(biāo)為止。深度優(yōu)先是按照一定的順序前查找完一個(gè)分支，再查找另一個(gè)分支，以至找到目標(biāo)為止。廣度和深度優(yōu)先搜索有一個(gè)很大的缺陷就是他們都是在一個(gè)給定的狀態(tài)空間中窮舉。這在狀態(tài)空間不大的情況下是很合適的算法，可是當(dāng)狀態(tài)空間十分大，且不預(yù)測(cè)的情況下就不可取了。而啟發(fā)式搜索是在狀態(tài)空間中的搜索對(duì)每一個(gè)搜索的位置進(jìn)行評(píng)估，得到最好的位置，再?gòu)倪@個(gè)位置進(jìn)行搜索直到目標(biāo)。這樣可以省略大量無(wú)畏的搜索路徑，提到了效率。附錄代碼：#include"stdafx.h"#include"iostream.h"#include<time.h>#include<stdio.h>#include<dos.h>#include<conio.h>inttarget[9]={0};//classdefinitionclasseight_num{private: intnum[9]; intnot_in_position_num; intdeapth; inteva_function;public: eight_num*parent; eight_num*leaf_next; eight_num*leaf_pre; eight_num(intinit_num[9]); eight_num(intnum1,intnum2,intnum3,intnum4,intnum5,intnum6,intnum7,intnum8,intnum9) { num[0]=num1;num[1]=num2;num[2]=num3;num[3]=num4;num[4]=num5;num[5]=num6;num[6]=num7;num[7]=num8;num[8]=num9; } eight_num(void) { for(inti=0;i<9;i++) num[i]=i; } voidcul_para(void); voidget_numbers_to(intother_num[9]); intget_nipn(void) {returnnot_in_position_num;} intget_deapth(void) {returndeapth;} intget_evafun(void) {returneva_function;} voidset_num(intother_num[9]); voidshow(void); eight_num&operator=(eight_num&); eight_num&operator=(intother_num[9]); intoperator==(eight_num&); intoperator==(intother_num[9]);};//計(jì)算啟發(fā)函數(shù)g(n)的值voideight_num::cul_para(void){ inti; inttemp_nipn=0; for(i=0;i<9;i++) if(num[i]!=target[i]) temp_nipn++; not_in_position_num=temp_nipn; if(this->parent==NULL) deapth=0; else deapth=this->parent->deapth+1; eva_function=not_in_position_num+deapth;}//構(gòu)造函數(shù)1eight_num::eight_num(intinit_num[9]){ for(inti=0;i<9;i++) num[i]=init_num[i];}//顯示當(dāng)前節(jié)點(diǎn)的狀態(tài)voideight_num::show(){ cout<<num[0]; cout<<""; cout<<num[1];cout<<"";cout<<num[2];cout<<"\n";cout<<num[3];cout<<"";cout<<num[4];cout<<"";cout<<num[5];cout<<"\n";cout<<num[6];cout<<"";cout<<num[7];cout<<"";cout<<num[8];cout<<"\n";}voideight_num::get_numbers_to(intother_num[9]){ for(inti=0;i<9;i++) other_num[i]=num[i];}//設(shè)置當(dāng)前節(jié)點(diǎn)狀態(tài)(欲設(shè)置的狀態(tài)記錄的other數(shù)組中)voideight_num::set_num(intother_num[9]){ for(inti=0;i<9;i++) num[i]=other_num[i];}eight_num&eight_num::operator=(eight_num&another_8num){ for(inti=0;i<9;i++) num[i]=another_8num.num[i]; not_in_position_num=another_8num.not_in_position_num; deapth=another_8num.deapth+1; eva_function=not_in_position_num+deapth; return*this;}eight_num&eight_num::operator=(intother_num[9]){ for(inti=0;i<9;i++) num[i]=other_num[i]; return*this;}inteight_num::operator==(eight_num&another_8num){ intmatch=1; for(inti=0;i<9;i++) if(num[i]!=another_8num.num[i]) { match=0; break; } if(match==0) return0; else return1;}inteight_num::operator==(intother_num[9]){ intmatch=1; for(inti=0;i<9;i++) if(num[i]!=other_num[i]) { match=0; break; } if(match==0) return0; else return1;}//空格向上移intmove_up(intnum[9]){ for(inti=0;i<9;i++) if(num[i]==0) break; if(i<3) return0; else { num[i]=num[i-3]; num[i-3]=0; return1; }}//空格向下移intmove_down(intnum[9]){ for(inti=0;i<9;i++) if(num[i]==0) break; if(i>5) return0; else { num[i]=num[i+3]; num[i+3]=0; return1; }}//空格向左移intmove_left(intnum[9]){ for(inti=0;i<9;i++) if(num[i]==0) break; if(i==0||i==3||i==6) return0; else { num[i]=num[i-1]; num[i-1]=0; return1; }}//空格向右移intmove_right(intnum[9]){ for(inti=0;i<9;i++) if(num[i]==0) break; if(i==2||i==5||i==8) return0; else { num[i]=num[i+1]; num[i+1]=0; return1; }}//判斷可否解出inticansolve(intnum[9],inttarget[9]){ inti,j; intcount_num,count_target; for(i=0;i<9;i++) for(j=0;j<i;j++) { if(num[j]<num[i]&&num[j]!=0) count_num++; if(target[j]<target[i]&&target[j]!=0) count_target++; } if((count_num+count_target)%2==0) return1; else return0;}//判斷有無(wú)重復(fù)intexisted(intnum[9],eight_num*where){ eight_num*p; for(p=where;p!=NULL;p=p->parent) if(*p==num) return1; return0;}//尋找估價(jià)函數(shù)最小的葉子節(jié)點(diǎn)eight_num*find_OK_leaf(eight_num*start){ eight_num*p,*OK; p=OK=start; intmin=start->get_evafun(); for(p=start;p!=NULL;p=p->leaf_next) if(min>p->get_evafun()) { OK=p; min=p->get_evafun(); } returnOK;}intmain(void){ intmemery_used=0,step=0; intnum[9]; intflag=0;//是否輸入錯(cuò)誤標(biāo)志，1表示輸入錯(cuò)誤 intbingo=0;//是否查找成功標(biāo)志，1表示成功 inti,j; cout<<"Pleaseinputthefinalnumber(0fortheblank):\n"; for(i=0;i<9;i++) { flag=0; cin>>target[i]; for(j=0;j<i;j++) if(target[i]==target[j]) flag=1; if(target[i]<0||target[i]>8||flag==1) { i--; cout<<"Illeglenumber!\tReinput!\n"; } } cout<<"Pleaseinputthenumber(0fortheblank):\n"; for(i=0;i<9;i++) { flag=0; cin>>num[i]; for(j=0;j<i;j++) if(num[i]==num[j]) flag=1; if(num[i]<0||num[i]>8||flag==1) { i--; cout<<"Illeglenumber!\tReinput!\n"; } } eight_numS(num),Target(target); S.parent=S.leaf_next=S.leaf_pre=NULL; S.cul_para(); memery_used++; cout<<"Nowtheinitialnumbersare:\n"; S.show(); cout<<"AndtheTargetis:\n"; Target.show(); if(!icansolve(num,target)) { cout<<"Noonecansolveit!\n"; cin>>i; return1; } eight_num*OK_leaf=&S,*leaf_start=&S,*new_8num,*p; while(OK_leaf!=NULL&&bingo!=1) { OK_leaf=find_OK_leaf(leaf_start); if(*OK_leaf==Target) { bingo=1; break; } p=OK_leaf->leaf_pre; OK_leaf->get_numbers_to(num); if(move_up(num)&&!existed(num,OK_leaf)) { new_8num=neweight_num; new_8num->set_num(num); new_8num->parent=OK_leaf; new_8num->cul_para(); new_8num->leaf_pre=p; if(p==NULL) leaf_start=new_8num; else p->leaf_next=new_8num; p=new_8num; memery_used++; } OK_leaf->get_numbers_to(num); if(move_down(num)&&!existed(num,OK_leaf)) { new_8num=neweight_num; new_8num->set_num(num); new_8num->parent=OK_leaf; new_8num->cul_para(); new_8num->leaf_pre=p; if(p==NULL) leaf_start=new_8num; else p->leaf_next=new_8num; p=new_8num; memery_used++; } OK_leaf->get_numbers_to(num); if(move_left(num)&&!existed(num,OK_leaf)) {