九宮格的啟發(fā)式搜索

九宮格的啟發(fā)式搜索班級：計算機(jī)一班姓名：覃榮錦學(xué)號:目錄TOC\o"1-5"\h\z一、 實驗?zāi)康?3\o"CurrentDocument"二、 實驗語言環(huán)境 3\o"CurrentDocument"三、 實現(xiàn)設(shè)計 3\o"CurrentDocument"狀態(tài)表示： 3算法介紹： 3廣度優(yōu)先搜索： 3深度優(yōu)先搜索： .4\o"CurrentDocument"初始化節(jié)點以及判斷目標(biāo)節(jié)點 5\o"CurrentDocument"拓展節(jié)點 6\o"CurrentDocument"搜索算法 .7四、 程序全部代碼 8\o"CurrentDocument"五、 分析總結(jié) 15\o"CurrentDocument"數(shù)據(jù)結(jié)構(gòu)分析 15\o"CurrentDocument"拓展方法分析 15\o"CurrentDocument"搜索算法分析 15\o"CurrentDocument"六、 運行結(jié)果 16\o"CurrentDocument"七、 遇見的問題以及解決方法 16實驗?zāi)康募由顚植繐駜?yōu)搜索以及全局擇優(yōu)搜索的熟悉程度。了解局部擇優(yōu)搜索以及全局擇優(yōu)搜索的區(qū)別。二、 實驗語言環(huán)境系統(tǒng)：微軟Window?系統(tǒng)開發(fā)工具：visualc/c++6.0語言：c語言三、 實現(xiàn)設(shè)計狀態(tài)表示：九宮格狀態(tài)以一組一維數(shù)組表示。1~8分別表示8個對應(yīng)的數(shù)字，0表示空格，數(shù)據(jù)結(jié)構(gòu)如下：Typedefstruct{Intdata[9];}Data;九宮格節(jié)點為以線性表表示的樹的節(jié)點，因此需要加入指向該節(jié)點父母的指針，在這里用下標(biāo)表示，同時由于不同節(jié)點有不同的估值，因此需要加入表示其值變量。完整的數(shù)據(jù)結(jié)構(gòu)如下：typedefstruct{intdata[9];intparent;intvalue;}Data;算法介紹：1）局部擇優(yōu)搜索：第一步： 把初始節(jié)點S0放入open表。第二步： 如果open表為空，則問題無解，退出。第三步： 把OPEN表的第一個節(jié)點取出放入CLOSE表，記該節(jié)點為節(jié)點n。第四步：觀察節(jié)點n是否為目標(biāo)節(jié)點，若是，則求得問題的解，退出。第五步： 拓展節(jié)點n，將擴(kuò)展的的節(jié)點排序后放入open表，將合法節(jié)點放入open表中。然后轉(zhuǎn)到第二步。2）全局擇優(yōu)搜索：第一步： 把初始節(jié)點S0放入open表。第二步： 如果open表為空，則問題無解，退出。第三步： 把OPEN表的最后一個節(jié)點取出放入CLOSE表，記該節(jié)點為節(jié)點n。第四步：觀察節(jié)點n是否為目標(biāo)節(jié)點，若是，則求得問題的解，退出。第五步： 拓展節(jié)點n，將合法節(jié)點放入open表中。排序OPEN表。然后轉(zhuǎn)到第二步。輔助矩陣介紹在本程序中，為了執(zhí)行提高效率，在拓展和局面評估這兩部分采用了矩陣作為輔助。拓展輔助矩陣如下：conststaticintcheck[9][4]={{1,3,9,9},{0,2,4,9},{1,5,9,9},{0,4,6,9},{1,3,5,7},{2,4,8,9},{3,7,9,9},{4,6,8,9},{5,7,9,9}};在九宮格中，第0塊可以和1、3塊交換，第1塊可以和0、2、4塊交換……根據(jù)這個特點，本程序中生成如上的矩陣，對于第i塊，它的可交換塊為check[i][0]、check[i][1]、check[i][2]等等。評估輔助矩陣如下：conststaticinta[9][9]={0,1212323,4,//11Q1212323,//22,1,0,321,4,32//3123Q12L23//42,121,0,1,2,12//53,2,121,0,321,//6234,123,0,12//73,232,121,0,1,//8432,321,2,1,0,//9};該矩陣是一個二維矩陣，矩陣的值a[i][j]表示九宮格第i塊和第j塊的距離。這可以很方便地求出第i塊移動到目標(biāo)點的代價。比如，數(shù)字為n的塊當(dāng)前位置為p,則我們可以通過取a[n][p]的值直接求得它移動到目標(biāo)花費的代價。當(dāng)然，值為0的塊目標(biāo)位置是9,因此我們?yōu)樗≈祽?yīng)該為a[9][p]。初始化節(jié)點以及判斷目標(biāo)節(jié)點由于硬件的局限性，我們不能保證任何局面都能在一遍內(nèi)找到走法，因此我們在本程序中添加自動生成在當(dāng)前硬件條件下可破解的局面。思路為從目標(biāo)局面開始隨機(jī)移動30~40步生成一個初始局面。并將該初始局面作為初始節(jié)點。算法如下：voidInitData(intdata[9])//隨機(jī)生成可破解局面{srand((unsigned)time(NULL));//inta[9]={1,2,3,4,5,6,7,8,0};intk=rand()%10+30;intj,l,temp;while(k>=0){for(l=0;l<9;l++)if(a[l]==0)break;j=rand()%4;k--;if(check[l][j]!=9){temp=a[check[l][j]];a[check[l][j]]=a[l];a[l]=temp;}}for(j=0;j<9;j++)data[j]=a[j];}voidInit(intdata[9]){for(inti=0;i<9;i++)open[opentop].data[i]=data[i];open[opentop].parent=-1;open[opentop].value=GetValue(open[opentop].data);opentop++;}判斷目標(biāo)節(jié)點算法如下：boolCheckwin(intdata[9]){for(inti=0;i<8;i++)if(data[i]!=i+1)return0;return1;拓展節(jié)點拓展節(jié)點的思路為：對于當(dāng)前節(jié)點，利用上面介紹的輔助矩陣求出其接下來移動后可能生成的2~4個局面。判斷每個局面是否合法。方法是檢查open表和closed表，判斷該局面是否出現(xiàn)過，若出現(xiàn)過，則不合法，反之合法。得到新局面后，如果是局部擇優(yōu)，則將局面按從大到小排序，然后插入open表尾部(或從小到大排序，插入open表頭部)；如果是全局擇優(yōu)。則先放入open表，然后將open表從大到小排序。算法如下：voidQuanjuMakeMove(intdata[9],intparentvalue,intparent)//全局擇優(yōu)的拓展{inti=0,j,k;while(data[i]!=0)i++;for(j=0;j<4&&check[i][j]!=9;j++){for(k=0;k<9;k++){if(k==i)open[opentop].data[k]=data[check[i][j]];elseif(k==check[i][j])open[opentop].data[k]=data[i];elseopen[opentop].data[k]=data[k];}//if(狀態(tài)合法)opentop++;open[..].value=..if(!IsExist(open[opentop].data)){open[opentop].value=parentvalue+GetValue(open[opentop].data);open[opentop].parent=parent;opentop++;}}〃排序整個open表從小到大此處用選擇排序法Datatemp;if(opentop==0)return;for(i=0;i<opentop-1;i++){k=i;//設(shè)第i個是最大的for(j=i+1;j<opentop;j++)〃選擇出第i個之后的節(jié)點中最大的if(open[j].value>open[k].value)k=j;〃與第i個交換temp=open[k];open[k]=open[i];open[i]=temp;voidJubuMakeMove(intdata[9],intparentvalue,intparent)//局部擇優(yōu)的拓展{inti=0,j,k,m;m=opentop;while(data[i]!=0)i++;for(j=0;j<4&&check[i][j]!=9;j++){for(k=0;k<9;k++){if(k==i)open[opentop].data[k]=data[check[i][j]];elseif(k==check[i][j])open[opentop].data[k]=data[i];elseopen[opentop].data[k]=data[k];}//if(狀態(tài)合法)opentop++;open[..].value=..if(!IsExist(open[opentop].data)){open[opentop].value=parentvalue+GetValue(open[opentop].data);open[opentop].parent=parent;opentop++;}}〃排序open表中新添加的幾個從大到小此處用選擇排序法Datatemp;if(m==opentop)return;for(i=m;i<opentop-1;i++){k=i;//設(shè)第i個是最大的for(j=i+1;j<opentop;j++)〃選擇出第i個之后的節(jié)點中最大的if(open[j].value>open[k].value)k=j;〃與第i個交換temp=open[k];open[k]=open[i];open[i]=temp;}}搜索算法局部擇優(yōu)和全局擇優(yōu)在上面已經(jīng)介紹過，局部擇優(yōu)和全局擇優(yōu)的不同點僅在于他們拓展函數(shù)的不同。局部擇優(yōu)和全局擇優(yōu)算法如下：voidQuanju(){〃把初始節(jié)點放入open表searchmethod=1;Init(data);〃如果open表為空退出step2:if(opentop==0||opentop>99||closedtop>299){win=0;return;}〃把open表最后一節(jié)點放入close表closed[closedtop++]=open[--opentop];〃考察該節(jié)點，若是目標(biāo)節(jié)點則退出if(Checkwin(closed[closedtop-1].data)){win=1;return;}〃生成走法全局與局部的不同在于此步QuanjuMakeMove(closed[closedtop-1].data,closed[closedtop-1].value,closedtop-1);gotostep2;}voidJubu(){〃把初始節(jié)點放入open表searchmethod=1;Init(data);〃如果open表為空退出step2:if(opentop==0||closedtop==99){win=0;return;}〃把open表最后一節(jié)點放入close表closed[closedtop++]=open[--opentop];〃考察該節(jié)點，若是目標(biāo)節(jié)點則退出if(Checkwin(closed[closedtop-1].data)){win=1;return;}〃生成走法全局與局部的不同在于此步JubuMakeMove(closed[closedtop-1].data,closed[closedtop-1].value,closedtop-1);gotostep2;}程序全部代碼#include"stdio.h"#include"stdlib.h"#include"time.h"intGetValue(intdata[9]);typedefstruct{intdata[9];intparent;intvalue;}Data;Dataopen[100],closed[300];intopentop=0,closedtop=0,openrear=0;intsearchmethod;boolwin;intdata[9]={0,2,3,1,4,5,7,8,6};conststaticintcheck[9][4]={{1,3,9,9},{0,2,4,9},{1,5,9,9},{0,4,6,9},{1,3,5,7},{2,4,8,9},{3,7,9,9},{4,6,8,9},{5,7,9,9}};voidInitData(intdata[9])//隨機(jī)生成可破解局面{srand((unsigned)time(NULL));//inta[9]={1,2,3,4,5,6,7,8,0};intk=rand()%10+30;intj,l,temp;while(k>=0){for(l=0;l<9;l++)if(a[l]==0)break;j=rand()%4;k--;if(check[l][j]!=9){temp=a[check[l][j]];a[check[l][j]]=a[l];a[l]=temp;}}for(j=0;j<9;j++)data[j]=a[j];voidInit(intdata[9]){for(inti=0;i<9;i++)open[opentop].data[i]=data[i];open[opentop].parent=-1;open[opentop].value=GetValue(open[opentop].data);opentop++;}boolCheckwin(intdata[9]){for(inti=0;i<8;i++)if(data[i]!=i+1)return0;return1;}intGetValue(intdata[9]){conststaticinta[9][9]={0,1212323,4,//11Q1212323,//22,1,0,321,432,//3123Q12L23//42,121,0,1,2,12//53,2,121,0,321,//6234,123Q12//73,232,121,0,1,//8432,32121,0,//9};intsum=0;for(inti=0;i<9;i++){if(data[i])sum=sum+a[i][data[i]-1];elsesum=sum+a[i][8];}returnsum;}boolIsSame(int*data1,int*data2){inti;for(i=0;i<8;i++)if(data1[i]!=data2[i])return0;return1;}boolIsExist(intdata[9]){inti;for(i=openrear;i!=opentop;i=++i%100){if(IsSame(open[i].data,data))returntrue;}for(i=0;i<closedtop;i++){if(IsSame(closed[i].data,data))returntrue;}returnfalse;}voidQuanjuMakeMove(intdata[9],intparentvalue,intparent){inti=0,j,k;while(data[i]!=0)i++;for(j=0;j<4&&check[i][j]!=9;j++){for(k=0;k<9;k++){if(k==i)open[opentop].data[k]=data[check[i][j]];elseif(k==check[i][j])open[opentop].data[k]=data[i];elseopen[opentop].data[k]=data[k];}//if(狀態(tài)合法)opentop++;open[..].value=..if(!IsExist(open[opentop].data)){open[opentop].value=parentvalue+GetValue(open[opentop].data);open[opentop].parent=parent;opentop++;}}〃排序open表從小到大此處用選擇排序法Datatemp;if(opentop==0)return;for(i=0;i<opentop-1;i++){k=i;//設(shè)第i個是最大的for(j=i+1;j<opentop;j++)//選擇出第i個之后的節(jié)點中最大的if(open[j].value>open[k].value)k=j;〃與第i個交換temp=open[k];open[k]=open[i];open[i]=temp;}}voidJubuMakeMove(intdata[9],intparentvalue,intparent){inti=0,j,k,m;m=opentop;while(data[i]!=0)i++;for(j=0;j<4&&check[i][j]!=9;j++){for(k=0;k<9;k++){if(k==i)open[opentop].data[k]=data[check[i][j]];elseif(k==check[i][j])open[opentop].data[k]=data[i];elseopen[opentop].data[k]=data[k];}//if(狀態(tài)合法)opentop++;open[..].value=..if(!IsExist(open[opentop].data)){open[opentop].value=parentvalue+GetValue(open[opentop].data);open[opentop].parent=parent;opentop++;}}〃排序open表中新添加的幾個從小到大此處用選擇排序法Datatemp;if(m==opentop)return;for(i=m;i<opentop-1;i++){k=i;//設(shè)第i個是最大的for(j=i+1;j<opentop;j++)//選擇出第i個之后的節(jié)點中最大的if(open[j].value>open[k].value)k=j;〃與第i個交換temp=open[k];open[k]=open[i];open[i]=temp;}}voidQuanju(){〃把初始節(jié)點放入open表searchmethod=1;Init(data);〃如果open表為空退出step2:if(opentop==0||opentop>99||closedtop>299){win=0;return;}〃把open表最后一節(jié)點放入close表closed[closedtop++]=open[--opentop];〃考察該節(jié)點，若是目標(biāo)節(jié)點則退出if(Checkwin(closed[closedtop-1].data)){win=1;return;}〃生成走法全局與局部的不同在于此步QuanjuMakeMove(closed[closedtop-1].data,closed[closedtop-1].value,closedtop-1);gotostep2;}voidJubu(){〃把初始節(jié)點放入open表searchmethod=1;Init(data);〃如果open表為空退出step2:if(opentop==0||closedtop==99){win=0;return;}〃把open表最后一節(jié)點放入close表closed[closedtop++]=open[--opentop];〃考察該節(jié)點，若是目標(biāo)節(jié)點則退出if(Checkwin(closed[closedtop-1].data)){win=1;return;}〃生成走法全局與局部的不同在于此步JubuMakeMove(closed[closedtop-1].data,closed[closedtop-1].value,closedtop-1);gotostep2;}voidDisplay(intdata[9]){inti;for(i=0;i<9;i++){printf("%d",data[i]);if((i+1)%3==0)printf("\n");}voidmain(){/*intdata[9]={1,2,3,4,5,6,7,8