人工智能第二次實(shí)驗(yàn)

1、. 實(shí)驗(yàn)二 用廣度優(yōu)先搜索算法實(shí)現(xiàn)九宮圖1 實(shí)驗(yàn)內(nèi)容： 運(yùn)用廣度優(yōu)先搜索的基本原理和方法實(shí)現(xiàn)對(duì)九宮圖的查找，實(shí)現(xiàn)具體的編程要能顯示正確的結(jié)果和圖形。2 實(shí)驗(yàn)原理 基本思想： 從初節(jié)點(diǎn)S0開(kāi)始，按層對(duì)接點(diǎn)進(jìn)行擴(kuò)展，并考察它是否為目標(biāo)節(jié)點(diǎn)，在第N層的節(jié)點(diǎn)沒(méi)有擴(kuò)展之前，不對(duì)第N+1層的節(jié)點(diǎn)進(jìn)行擴(kuò)展。 Open表中節(jié)點(diǎn)總是按進(jìn)入的順序排列，也就是采用隊(duì)列的結(jié)構(gòu)。 基本過(guò)程： 1 把初節(jié)點(diǎn)S0放入OPEN表中2如果OPEN表為空，則問(wèn)題無(wú)解，退出。3把OPEN表的第一個(gè)節(jié)點(diǎn)取出放入CLOSE表（記為N）4考察節(jié)點(diǎn)是否為目標(biāo)節(jié)點(diǎn)，若是，問(wèn)題解決，退出。5 若是該節(jié)點(diǎn)不能擴(kuò)展，轉(zhuǎn)向26 擴(kuò)展節(jié)點(diǎn)N，將不包括

2、祖先節(jié)點(diǎn)的子節(jié)點(diǎn)放入OPEN表的尾部，并為每一個(gè)子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)第二步。3 實(shí)驗(yàn)分析：用廣度優(yōu)先的算法實(shí)現(xiàn)九宮重排時(shí)要注意以下問(wèn)題： 1 對(duì)于OPEN表應(yīng)采用什么樣的數(shù)據(jù)結(jié)構(gòu)，由于為廣度優(yōu)先，需采用隊(duì)列的結(jié)構(gòu)。 2要用算法實(shí)現(xiàn)時(shí)，需要注意產(chǎn)生的節(jié)點(diǎn)不得與祖先節(jié)點(diǎn)相同，必須用相應(yīng)的函數(shù)去實(shí)現(xiàn)匹配，不相同的才能放入OPEN表中。 3由于廣度優(yōu)先是完備的，故必有解。實(shí)驗(yàn)代碼如下： 代碼簡(jiǎn)單分析： 其中有兩個(gè)頭文件。 頭文件# include list.h中主要實(shí)現(xiàn)的功能是把open表建造成隊(duì)列的形式，并且實(shí)現(xiàn)對(duì)新節(jié)點(diǎn)的插入insertback(const string & val

3、ue)，為其分配父節(jié)點(diǎn)指針，以及將表中第一個(gè)節(jié)點(diǎn)移動(dòng)到CLOSE表中removefront()。 頭文件# include jgwt.h中實(shí)現(xiàn)九宮圖放入左，中，右，下的移動(dòng)函數(shù)，以及實(shí)現(xiàn)CLOSE表中的節(jié)點(diǎn)的擴(kuò)展cjgwt:iskuozhan()；還有實(shí)現(xiàn)比較拋棄那些與祖先節(jié)點(diǎn)相同的節(jié)點(diǎn)函數(shù)cjgwt:isInsertOpen(string &str)/ 判斷是否與祖先接點(diǎn)相同，不同則插入。還有對(duì)于目標(biāo)的輸出功能void cjgwt:print()。 主函數(shù)只要實(shí)現(xiàn)動(dòng)態(tài)輸入初始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)，然后調(diào)用頭文件里的各函數(shù)。# include list.h# include jgwt.h# incl

4、ude # include using namespace std;int main()string yuanstr,mustr;cout例如：283104765 回車(chē) 123804765 endl; cout 初始數(shù)據(jù):yuanstr;cout 目標(biāo)數(shù)據(jù):mustr;cjgwt tr(mustr,yuanstr);tr.cpjg();return 0;# ifndef jgwt_h# define jgwt_h# include # include # include list.hclass cjgwtpublic:cjgwt(string &,string &);void cpjg();b

5、ool operate();void iskuozhan();bool isEqualDads(string &);void swap(string &,int ,int);void isInsertOpen(string &);void print();void output(cnode *); int jds;private:string yuan;string mubiao;clist open;clist closed;cjgwt:cjgwt(string &str1,string &str2) :yuan(str1),mubiao(str2),jds(0) void cjgwt:cp

6、jg()int flag=0;open.insertfront(yuan);/ 在OPEN中放致初接點(diǎn)S0；flag=operate();cout擴(kuò)展的節(jié)點(diǎn)數(shù)為： ;coutjds個(gè)endl;if(flag=1)print();else cout對(duì)不起，在1000步之內(nèi)做不出GetData()=mubiao)/ 判斷CLOSED表中的LASTPTR是否為目標(biāo)接點(diǎn)flag=1;break;else /*if(iskuozhan()=0)/continue;elsezhankai();*/iskuozhan();/判斷是否能展開(kāi)，若能則展開(kāi)，不能則做下一次循環(huán)i+;if(i=1000)break;

7、/coutiGetData();string str1,str2,str3,str4;str1=str2=str3=str4=temp;type=temp.find(0)+1;switch(type)case 1:/string str1=temp,str2=temp;swap(str1,0,1);isInsertOpen(str1);swap(str2,0,3); isInsertOpen(str2);break;case 2:/string str1=temp,str2=temp,str3=temp;swap(str1,1,0);isInsertOpen(str1);swap(str2,1

8、,2);isInsertOpen(str2);swap(str3,1,4);isInsertOpen(str3);break;case 3:swap(str1,2,1);isInsertOpen(str1);swap(str2,2,5);isInsertOpen(str2);break;case 4:swap(str1,3,0);isInsertOpen(str1);swap(str2,3,4);isInsertOpen(str2);swap(str3,3,6);isInsertOpen(str3);break;case 5:swap(str1,4,1);isInsertOpen(str1);

9、swap(str2,4,3);isInsertOpen(str2);swap(str3,4,5);isInsertOpen(str3);swap(str4,4,7);isInsertOpen(str4);break;case 6:swap(str1,5,2);isInsertOpen(str1);swap(str2,5,4);isInsertOpen(str2);swap(str3,5,8);isInsertOpen(str3);break;case 7:swap(str1,6,3);isInsertOpen(str1);swap(str2,6,7);isInsertOpen(str2);br

10、eak;case 8:swap(str1,7,4);isInsertOpen(str1);swap(str2,7,6);isInsertOpen(str2);swap(str3,7,8);isInsertOpen(str3);break;case 9:swap(str1,8,5);isInsertOpen(str1);swap(str2,8,7);isInsertOpen(str2);break;default:couttypesetDadptr(closed.lastptr);jds+;/open.lastptr-dadptr=closed.lastptr;/value=1;bool cjg

11、wt:isEqualDads(string &str)/是否與祖先接點(diǎn)相同函數(shù)/*cnode *currptr=closed.lastptr;string temp=currptr-GetData();while(currptr!=NULL & temp!=str)currptr=currptr-getDadptr();if(currptr=NULL)return 0;else return 1;*/cnode *currptr=closed.lastptr;string temp;while(currptr!=NULL)temp=currptr-GetData();if(temp!=str)

12、currptr=currptr-getDadptr();else break;if(currptr!=NULL)return 1;else return 0;void cjgwt:print()cnode *currptr=closed.lastptr;while(currptr!=NULL)output(currptr);currptr=currptr-getDadptr();void cjgwt:output(cnode *value)string temp=value-GetData();for(int i=0;i9;i+)if(tempi=0)cout ;if(i=8 | i=5 |

13、i=2)coutendl;elsecouttempi ; if(i=2 | i=5 |i=8)coutendl;cout*endl;# endif# ifndef clist_h# define clist_h# include # include node.h# include # include # include using namespace std;class clistfriend class cjgwt;public:clist();clist();void insertfront(const string &);void insertfront(cnode *);void in

14、sertback(const string &);void insertback(cnode *);cnode *removefront();bool removeback(string &);string firstvalue() return firstptr-data;bool isempty() const;void print() const;private:cnode *firstptr;cnode *lastptr;cnode *getnew(const string &);clist:clist():firstptr(0),lastptr(0) ;clist:clist()if

15、(!isempty()/coutdestroying nodesnextptr;delete tempptr;void clist:insertfront(const string & value)cnode *newptr=getnew(value);if(isempty()firstptr=lastptr=newptr;elsenewptr-nextptr=firstptr;firstptr=newptr;void clist:insertfront(cnode * value)if(isempty()firstptr=lastptr=value;elsevalue-nextptr=fir

16、stptr;firstptr=value;void clist:insertback(const string & value)cnode *newptr=getnew(value);if(isempty()firstptr=lastptr=newptr;elselastptr-nextptr=newptr;lastptr=newptr;newptr-nextptr=NULL;void clist:insertback(cnode *value)if(isempty()firstptr=lastptr=value;elselastptr-nextptr=value;lastptr=value;

17、value-nextptr=NULL;cnode *clist:removefront()if(isempty()/return false;elsecnode *tempptr;/value=firstptr-data;tempptr=firstptr;firstptr=firstptr-nextptr;/delete tempptr;/return true;return tempptr;bool clist:removeback( string & value)if(isempty()return false;elsecnode *currentptr=firstptr,*tempptr

18、=lastptr;if(firstptr=lastptr)firstptr=lastptr=NULL;elsewhile(currentptr-nextptr!=lastptr)currentptr=currentptr-nextptr; lastptr=currentptr;currentptr-nextptr=NULL;value=tempptr-data;delete tempptr;return true;bool clist:isempty() constreturn firstptr=NULL;void clist:print() constcnode *currentptr=firstptr;while(currentptr!=NULL)coutdatanextptr;coutendl;cnode *clist:getnew(const string & value)cnode *