人工智能重排九宮

人工智能課內(nèi)實(shí)驗(yàn)報(bào)告重排九宮問(wèn)題班級(jí):姓名：學(xué)號(hào):重排九宮問(wèn)題搜索就是利用已知條件（知識(shí)）尋求解決問(wèn)題的辦法的過(guò)程。狀態(tài)空間搜索即為一種重要的搜索策略，其可分為盲目搜索和啟發(fā)式搜索。實(shí)驗(yàn)?zāi)康睦脿顟B(tài)空間搜索解決實(shí)際問(wèn)題，將理論應(yīng)用于實(shí)踐。加深對(duì)概念的理解、知識(shí)的掌握，并提高編程能力和動(dòng)手能力。實(shí)驗(yàn)原理重排九宮問(wèn)題在3*3的方格棋盤(pán)上放置分別標(biāo)有數(shù)字1，2,3,4,5,6,7,8的八張牌，確定初始狀態(tài)和目標(biāo)狀態(tài)?？墒褂玫乃惴锌崭褡笠?、空格上移、空格右移、空格下移，即它們只允許把位于空格左、上、右、下邊的牌移入空格。要求尋找從初始狀態(tài)到目標(biāo)狀態(tài)的路徑。狀態(tài)空間搜索狀態(tài)空間的一般搜索過(guò)程：（1） 把初始節(jié)點(diǎn)S0放入OPEN表，并建立目前只包含S0的圖，記為G；（2） 檢查OPEN表是否為空，若為空則問(wèn)題無(wú)解，退出；（3） 把OPEN表的第一個(gè)節(jié)點(diǎn)取出放入CLOSE表，并記該節(jié)點(diǎn)為n；（4） 考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了解，退出；（5） 擴(kuò)展節(jié)點(diǎn)n，生成一組子節(jié)點(diǎn)。把其中不是節(jié)點(diǎn)n先輩的那些子節(jié)點(diǎn)記做集合M，并把這些子節(jié)點(diǎn)作為節(jié)點(diǎn)n的子節(jié)點(diǎn)加入G中；（6） 針對(duì)M中子節(jié)點(diǎn)的不同情況，分別進(jìn)行如下處理：a） 對(duì)于那些未曾在G中出現(xiàn)過(guò)的M成員設(shè)置一個(gè)指向父節(jié)點(diǎn)（即節(jié)點(diǎn)n）的指針，并把它們放入OPEN表;（不在OPEN表）b） 對(duì)于那些先前已經(jīng)在G中出現(xiàn)過(guò)的M成員，確定是否需要修改它指向父節(jié)點(diǎn)的指針；（在OPEN表中）c） 對(duì)于那些先前已在G中出現(xiàn)并且已經(jīng)擴(kuò)展了的M成員，確定是否需要修改其后繼節(jié)點(diǎn)指向父節(jié)點(diǎn)的指針； （在CLOSE表中）（7） 按某種搜索策略對(duì)OPEN表中的節(jié)點(diǎn)進(jìn)行排序；（8） 轉(zhuǎn)第2步。廣度優(yōu)先搜索的基本思想：從初始節(jié)點(diǎn)S0開(kāi)始，逐層地對(duì)節(jié)點(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)入的先后順序排列，先進(jìn)入的節(jié)點(diǎn)排在前面，后進(jìn)入的排在后面。算法描述：（1）把初始節(jié)點(diǎn)S0放入OPEN表。如果OPEN表為空，則問(wèn)題無(wú)解，退出。把OPEN表的第一個(gè)節(jié)點(diǎn)(記為節(jié)點(diǎn)n)取出放入CLOSE表?？疾旃?jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問(wèn)題的解，退出。若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第2步。擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入OPEN表的尾部，并為每一個(gè)子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)第2步。A*搜索：如果一般搜索過(guò)程滿(mǎn)足如下限制，則它就稱(chēng)為A*算法：⑴把OPEN表中的節(jié)點(diǎn)按估價(jià)函數(shù)：f(x)=g(x)+h(x)f(x)的值從小至大進(jìn)行排序(一般搜索過(guò)程的第7步)。g(x)是從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)x的路徑的代價(jià)，g(x)是對(duì)g*(x)的估計(jì)，g(x)>0。h(x)是h*(x)的下界，即對(duì)所有的x均有：h(x)Wh*(x)。其中，g*(x)是從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)x的最小代價(jià)；h*(x)是從節(jié)點(diǎn)x到目標(biāo)節(jié)點(diǎn)的最小代價(jià)。算法描述：把初始節(jié)點(diǎn)S0放入OPEN表，并建立目前只包含S0的圖，記為G；檢查OPEN表是否為空，若為空則問(wèn)題無(wú)解，退出；把OPEN表的第一個(gè)節(jié)點(diǎn)取出放入CLOSE表，并記該節(jié)點(diǎn)為n；（4） 考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問(wèn)題的解，退出；（5） 擴(kuò)展節(jié)點(diǎn)n，生成一組子節(jié)點(diǎn)。把其中不是節(jié)點(diǎn)n先輩的那些子節(jié)點(diǎn)記做集合M，并把這些子節(jié)點(diǎn)作為節(jié)點(diǎn)n的子節(jié)點(diǎn)加入G中；（6） 針對(duì)M中子節(jié)點(diǎn)的不同情況，分別進(jìn)行如下處理：a） 對(duì)于那些未曾在G中出現(xiàn)過(guò)的M成員設(shè)置一個(gè)指向父節(jié)點(diǎn)（即節(jié)點(diǎn)n）的指針，并把它們放入OPEN表；（不在OPEN表）b） 對(duì)于那些先前已經(jīng)在G中出現(xiàn)過(guò)的M成員，確定是否需要修改它指向父節(jié)點(diǎn)的指針；（在OPEN表中，對(duì)g（x）進(jìn)行更新）c） 對(duì)于那些先前已在G中出現(xiàn)并且已經(jīng)擴(kuò)展了的M成員，確定是否需要修改其后繼節(jié)點(diǎn)指向父節(jié)點(diǎn)的指針；（在CLOSE表中，對(duì)節(jié)點(diǎn)n子節(jié)點(diǎn)的子節(jié)點(diǎn)更新g（x））⑺對(duì)OPEN表中的節(jié)點(diǎn)按估價(jià)函數(shù)進(jìn)行排序；（8）轉(zhuǎn)第2步。實(shí)驗(yàn)內(nèi)容（1） 編寫(xiě)程序，利用狀態(tài)空間搜索解決重排九宮問(wèn)題；（2） 分別采取廣度優(yōu)先搜索和A*算法實(shí)現(xiàn)，分析它們的優(yōu)缺點(diǎn)，對(duì)比盲目搜索和啟發(fā)式搜素。實(shí)驗(yàn)程序求解算法:publicclassMethod(publicstaticbooleanParity(inta[])(booleanparity=true;for(inti=0;i<a.length;i++){intk=i;for(intj=i+1;j<a.length;j++){if(a[k]>a[j]){k=j;}}if(k!=i){inttemp;temp=a[i];a[i]=a[k];a[k]=temp;parity=!parity;}}returnparity;}publicstaticbooleanisSolutionExist(intsrc[],intdest[],ints[][],intd[][] ){introw1=0,row2=0,clumn1=0,clumn2=0;booleanflag1,flag2;for(inti=0;i<3;i++){for(intj=0;j<3;j++){if(s[i][j]=0){row1=i;clumn1=j;}if(d[i][j]==0){row2=i;clumn2=j;}}}if((row1-row2+clumn1-clumn2)%2==0){flag1=true;}else{flag1=false;}if(Parity(src)==Parity(dest)){flag2=true;else(flag2=false;}if(flag1==flag2)(returntrue;}else(returnfalse;}}廣度優(yōu)先搜索節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)：privatestaticclassNode(intdata[][];//狀態(tài)introw;//0所在行intclumn;//0所在列Nodeparent;//父親節(jié)點(diǎn)Node(intdata[][],Nodeparent,introw,intclumn)(this.data=data;this.parent=parent;this.row=row;this.clumn=clumn;}A*算法節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)：privatestaticclassNode(intvalue; //估價(jià)函數(shù)的值intdiff=0;//當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最小代價(jià)intdepth=-1; //初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的代價(jià)intdata[][];introw;intclumn;Nodeparent;)(Node(intdata[][],Nodeparent,introw,intclumn,intdepth,intdiff)(this.data=data;this.parent=parent;this.row=row;this.clumn=clumn;this.depth=depth;this.diff=diff;this.value=depth+diff;}}5.實(shí)驗(yàn)結(jié)果輸入初始狀態(tài):輸入日標(biāo)狀態(tài):Cancel廣度優(yōu)先搜索結(jié)果：（紅色標(biāo)記為搜索路徑）A*搜索結(jié)果：（紅色標(biāo)記為搜索路徑）:結(jié)果分析：廣度優(yōu)先搜索：優(yōu)點(diǎn)是只要問(wèn)題有解，這種算法總可以得到解，而且得到的是最優(yōu)解。缺點(diǎn)是盲目性較大，當(dāng)日標(biāo)節(jié)點(diǎn)距離初始節(jié)點(diǎn)較遠(yuǎn)時(shí)將會(huì)產(chǎn)生許多無(wú)用節(jié)點(diǎn)，搜索效率低。A*算法