人工智能導(dǎo)論：狀態(tài)空間搜索實驗-八數(shù)碼問題求解解讀

1、昆明理工大學(xué)信息工程與自動化學(xué)院學(xué)生實驗報告20142015學(xué)年第一學(xué)期）年級、專業(yè)、班姓名成績實驗項目名稱狀態(tài)空間搜索實驗一八數(shù)碼問題求解指導(dǎo)教師胡蓉課程名稱：人工智能導(dǎo)論開課實驗室：該同學(xué)是否了解實驗原理:A.了解口C.不了解口年月日教師評語該同學(xué)的實驗?zāi)芰Γ涸撏瑢W(xué)的實驗是否達(dá)到要求：實驗報告是否規(guī)范：實驗過程是否詳細(xì)記錄：A.強(qiáng)口A.達(dá)到口A.規(guī)范口A.詳細(xì)口B.基本了解口B.中等口C.差口B.基本達(dá)到口B.基本規(guī)范口B.一般口C.未達(dá)到C.不規(guī)范C.沒有口教師簽名：年月一、實驗內(nèi)容和要求八數(shù)碼問題：在3X3的方格棋盤上，擺放著1到8這八個數(shù)碼，有1個方格是空的，其初始狀態(tài)如圖1所示，要

2、求對空格執(zhí)行空格左移、空格右移、空格上移和空格下移這四個操作使得棋盤從初始狀態(tài)到目標(biāo)狀態(tài)。例如：圖1八數(shù)碼問題示意圖請任選一種盲目搜索算法（廣度優(yōu)先搜索或深度優(yōu)先搜索）或任選一種啟發(fā)式搜索方法（全局擇優(yōu)搜索，加權(quán)狀態(tài)圖搜索，A算法或A*算法）編程求解八數(shù)碼問題（初始狀態(tài)任選）。選擇一個初始狀態(tài)，畫出搜索樹，填寫相應(yīng)的OPEN表和CLOSED表，給出解路徑，對實驗結(jié)果進(jìn)行分析總結(jié)，得出結(jié)論。實驗報告內(nèi)容格式要求：XXXXXXXXXXXX（中文：宋體，小四；英文：TimesNewRoman）。二、實驗?zāi)康氖煜と斯ぶ悄芟到y(tǒng)中的問題求解過程；熟悉狀態(tài)空間的盲目搜索和啟發(fā)式搜索算法的應(yīng)用熟悉對八數(shù)碼問題

3、的建模、求解及編程語言的應(yīng)用。三、實驗算法啟發(fā)函數(shù)設(shè)定由八數(shù)碼問題的部分狀態(tài)圖可以看出，從初始節(jié)點(diǎn)開始，在通向目標(biāo)節(jié)點(diǎn)的路徑上，各節(jié)點(diǎn)的數(shù)碼格局同目標(biāo)節(jié)點(diǎn)相比較，其數(shù)碼不同的位置個數(shù)在逐漸減少，最后為零，因此可以把數(shù)碼不同的位置個數(shù)作為標(biāo)志一個節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)距離遠(yuǎn)近的一個啟發(fā)性信息，利用這個信息來擴(kuò)展節(jié)點(diǎn)的選擇，減少搜索范圍，提高搜索速度。2、數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計數(shù)碼結(jié)構(gòu)體typedefstructnodeintformNN;intevalue;intudirec;右/八數(shù)碼結(jié)構(gòu)體/數(shù)碼組/評估值，差距/所屏蔽方向,防止往回推到上一狀態(tài),1上2下3左4structnode*parent;/父節(jié)點(diǎn)

4、Graph;Graph*QuMAX;隊列Graph*StMAX;堆棧搜索過程：（搜索采用廣度搜索方式，利用待處理隊列輔助，逐層搜索（跳過劣質(zhì)節(jié)點(diǎn)）a、把初始數(shù)碼組壓入隊列;b、從隊列中取出一個數(shù)碼組節(jié)點(diǎn)；c、擴(kuò)展子節(jié)點(diǎn)，即從上下左右四個方向移動空格，生成相應(yīng)子節(jié)點(diǎn):d、對子節(jié)點(diǎn)數(shù)碼組作評估，是否為優(yōu)越節(jié)點(diǎn)，即其評估值是否小于等于其父節(jié)點(diǎn)加一，是則將其壓入隊，否則拋棄。e、判斷壓入隊的子節(jié)點(diǎn)數(shù)碼組（優(yōu)越點(diǎn)）的評估值，為零則表示搜索完成,退出搜索；f、跳到步驟2；四、程序框圖五、實驗結(jié)果及分析采用深度優(yōu)先搜索方式并簡化搜索六、結(jié)論Open表close表01120234012456013目標(biāo)完成七、

5、源程序及注釋#include/設(shè)計了搜索深度范圍，防止隊列內(nèi)存越界#include6、運(yùn)行結(jié)果#include#defineN3/數(shù)碼組大小#defineMax_Step50/最大搜索深度#defineMAX50typedefstructnode/八數(shù)碼結(jié)構(gòu)體intformNN;/數(shù)碼組intevalue;/評估值intudirect;/所屏蔽方向，防止往回推到上已狀態(tài)，1上2下3左4右structnode*parent;/父節(jié)點(diǎn)/打印數(shù)碼組voidPrint(Graph*The_graph)inti,j;if(The_graph=NULL)prinTF(“圖為空n);elseprintF(n

6、);for(i=0;iN;i+)printF(|t);for(j=0;jFormij);/遍歷打印printF(t|n);printf=-vtvtvtBsMd/t-=Thegraphevalue)j、s知Iprint-h=n=)j一二一二一二看倉irrtEvaluate(G-5aph*Thelg-5aphJG-5aph宀IIirrtva1uteH、吊齊inrbijj-hor(iH0ji人Nji+)宀For(jHj人N-j+)宀i-h-Thelg-saphv-ho-smLij二HEndlg-saphv-ho-smLij)宀IIvalute+jThegraphvevalueuvalutejretu

7、rnvalute-二二二二一聲善廬Graph*Move(GraphDirectiirtc-seatNewIg-saph)宀IIGraph*舄產(chǎn)里3|3|1-、inrhHasGetBlankH0j、nMm朋姦artIrrtAb1eMoveH1j、淞審列炒inrbijjjtijtjjxjyj-hor(iH0ji人Nji+)、m朋姦妝圖Tj宀For(jHj人N-j+)宀i-h(Thegraph-hormi二jTH0)宀IHasGetBlankuljbreak-if(HasGetBlank=1)break;/printf(空格位置：d,%dn,i,j);t_i=i;t_j=j;/移動空格switch(

8、Direct)case1：/上t_i-;if(t_i=N)AbleMove=0;break;case3：/左t_j-;if(t_j=N)AbleMove=0;break;if(AbleMove=0)/不能移動則返回原節(jié)點(diǎn)returnThe_graph;if(CreatNew_graph=1)New_graph=(Graph*)malloc(sizeof(Graph);/生成節(jié)點(diǎn)for(x=0;xN;x+)for(y=0;yformxy=The_graph-formxy;/復(fù)制數(shù)碼組elseNew_graph=The_graph;/移動后New_graph-formij=New_graph-fo

9、rmt_it_j;New_graph-formt_it_j=0;/printf(移動產(chǎn)生的新圖:n);/Print(New_graph);returnNew_graph;/搜索函數(shù)Graph*Search(Graph*Begin,Graph*End)Graph*g1,*g2,*g;intStep=0;/深度intDirect=0;/方向inti;intfront,rear;front=rear=-1;/隊列初始化g=NULL;rear+;/入隊Qurear=Begin;while(rear!=front)/隊列不空front+;/出隊g1=Qufront;/printf(開始第d個圖：n,fr

10、ont);/Print(g1);for(i=1;iudirect)/跳過屏蔽方向continue;g2=Move(g1,Direct,1);/移動數(shù)碼組if(g2!=g1)/數(shù)碼組是否可以移動/可以移動Evaluate(g2,End);/評價新的節(jié)點(diǎn)/printf(開始產(chǎn)生的第d個圖：n,i);/Print(g2);if(g2-evalueevalue+1)/是優(yōu)越節(jié)點(diǎn)g2-parent=g1;/移動空格switch(Direct)/設(shè)置屏蔽方向，防止往回推case1：/上g2-udirect=2;break;case2：/下g2-udirect=1;break;case3：/左g2-udir

11、ect=4;break;case4：/右g2-udirect=3;break;rear+;Qurear=g2;/存儲節(jié)點(diǎn)到待處理隊列if(g2-evalue=0)/為0則搜索完成g=g2;/i=5;break;elsefree(g2);/拋棄劣質(zhì)節(jié)點(diǎn)g2=NULL;if(g!=NULL)/為0則搜索完成if(g-evalue=0)break;Step+;/統(tǒng)計深度if(StepMax_Step)break;returng;/初始化一個八數(shù)碼結(jié)構(gòu)體Graph*CR_BeginGraph(Graph*The_graph)srand(unsigned)time(0);intM=10;/隨機(jī)移動步數(shù)i

12、ntDirect;inti,x,y;Graph*New_graph;New_graph=(Graph*)malloc(sizeof(Graph);for(x=0;xN;x+)for(y=0;yformxy=The_graph-formxy;for(i=0;ievalue=0;New_graph-udirect=0;New_graph-parent=NULL;returnNew_graph;intmain(intargc,constchar*argv)/insertcodehere./*GraphBegin_graph=2,8,3,1,6,4,0,7,5,0,0,NULL;GraphBegin_

13、graph=2,8,3,1,0,4,7,6,5,0,0,NULL;GraphBegin_graph=2,0,1,4,6,5,3,7,8,0,0,NULL;*/目標(biāo)數(shù)碼組GraphEnd_graph=1,2,3,8,0,4,7,6,5,0,0,NULL;/初始數(shù)碼組Graph*Begin_graph;Begin_graph=CR_BeginGraph(&End_graph);/隨機(jī)產(chǎn)生初始數(shù)碼組Evaluate(Begin_graph,&End_graph);/對初始的數(shù)碼組評價printf(”初始數(shù)碼組：n”)；Print(Begin_graph);printf(目標(biāo)數(shù)碼組：n);Print(

14、&End_graph);Graph*G,*P;inttop=-1;/圖搜索G=Search(Begin_graph,&End_graph);/打印if(G)/把路徑倒序P=G;/壓棧while(P!=NULL)top+;Sttop=P;P=P-parent;printf(n);/彈棧打印while(top-1)P=Sttop;top-;Print(P);printf(n);elseprintf(”搜索不到結(jié)果，深度為dn,Max_Step);/設(shè)計搜索深度范圍主要是防止隊列內(nèi)存越界return0;讀書的好處1、行萬里路，讀萬卷書。2、書山有路勤為徑，學(xué)海無涯苦作舟。3、讀書破萬卷，下筆如有神。20、讀書給人以快樂、給人以光彩、給人以才干。培根達(dá)爾文4、我所學(xué)到的任何有價值的知識都是由自學(xué)中得來的。5、少壯不努力，老大徒悲傷。6、黑發(fā)不知勤學(xué)早，白首方悔讀書遲。顏真卿7、寶劍鋒從磨礪岀，梅花香自苦寒來。8、讀書要三到：心到、眼到、口到9