631306050105何昭霞+狀態(tài)空間搜索+啟發(fā)式搜索.doc

重慶交通大學計算機與信息學院驗證性實驗報告班 級： 軟件開發(fā) 專業(yè) 2013 級 1 班 學 號： 631306050105 姓 名： 何昭霞 實驗項目名稱： 狀態(tài)空間搜索 實驗項目性質(zhì)： 驗證性實驗 實驗所屬課程： 人工智能 實驗室(中心)：軟件中心實驗室（語音樓8樓） 指 導 教 師 ： 朱振國 實驗完成時間： 2016 年 6 月 10 日評閱意見：實驗成績： 簽名： 年 月 日一、實驗?zāi)康?1. 理解和掌握狀態(tài)空間搜索的策略。 2.熟悉人工智能系統(tǒng)中的問題求解過程； 3.熟悉狀態(tài)空間的盲目搜索和啟發(fā)式搜索算法的應(yīng)用； 4.熟悉對八數(shù)碼問題的建模、求解及編程語言的應(yīng)用。二、實驗內(nèi)容及要求（一）實驗內(nèi)容在一個3*3的九宮中有1-8個數(shù)碼及一個空格隨即的擺放在其中的格子里，現(xiàn)在要求實驗這個問題：將該九宮格調(diào)整為某種有序的形式。調(diào)整的規(guī)則是，每次只能將與空格（上、下、左、右）相鄰的一個數(shù)字平移到空格中。 （二）實驗要求 用選定的編程語言編寫程序，利用不同的搜索策略進行狀態(tài)空間搜索（如寬度優(yōu)先搜索、深度優(yōu)先搜索、有界深度優(yōu)先搜索等）。三、實驗設(shè)備及軟件 PC機一臺、Visual Studio 2012編程軟件四、設(shè)計方案 題目 狀態(tài)空間搜索 8數(shù)碼問題 設(shè)計的主要思路考慮廣度優(yōu)先算法：(1) 狀態(tài)空間盲目搜索寬度優(yōu)先搜索其基本思想是，從初始節(jié)點開始，向下逐層對節(jié)點進形依次擴展，并考察它是否為目標節(jié)點，再對下層節(jié)點進行擴展（或搜索）之前，必須完成對當層的所有節(jié)點的擴展。再搜索過程中，未擴展節(jié)點表OPEN中的節(jié)點排序準則是：先進入的節(jié)點排在前面，后進入的節(jié)點排在后面。(2) 寬度優(yōu)先算法如下首先把初始結(jié)點S0放入OPEN表中，然后若OPEN表為空，則搜索失敗，問題無解，接著取OPEN表中最前面的結(jié)點N放在CLOSE表中，并冠以順序編號n，若目標結(jié)點Sg=N，則搜索成功，問題有解。若N無子結(jié)點，則重復取OPEN表中最前面的結(jié)點N放在CLOSE表中。擴展結(jié)點N，將其所有子結(jié)點配上指向N的放回指針，依次放入OPEN表的尾部，然后重復取OPEN表中最前面的結(jié)點N放在CLOSE表中。 根據(jù)算法的中心思想進行程序設(shè)計，其流程圖如下圖所示。 主要功能使用C語言相關(guān)知識，將3*3的九宮格調(diào)整為某種有序的形式。五、主要代碼#include #include struct node int x,y; int cntdif;int step; int f9; int xy33; queue10000; int map33; int dir42=-1,0,1,0,0,1,0,-1; int open10000; int zz9; int f1,f2; struct node sour,dest; queuetail.fi*3+j=queuetail.xyij=ffi*3+j; queuetail.step=HH.step+1; queuetail.x=sx; queuetail.y=sy; tdif=count(queuetail.f,zz); opentail=visit(queuetail.f); print(queuetail.xy); if(match(queuetail) printf(step(s):%d！n,queuetail.step); return; qsort(queue+head,tail-head+1,sizeof(queue0),comp);/排序，每次選擇cntdif數(shù)目最小的擴展 int main() int i,j,a9,b9; printf(Please input the nitial status,input 0 to the vacant position :n); for(i=0;i3;i+) for(j=0;j3;j+) scanf(%d,&mapij); sour.xyij=mapij; sour.fi*3+j=mapij; ai*3+j=mapij; if(mapij=0) sour.x=i; sour.y=j; sour.step=0; tdif=0; printf(Please input the final status:n); for(i=0;i3;i+) for(j=0;j3;j+) scanf(%d,&mapij); dest.xyij=mapij; dest.fi*3+j=mapij; bi*3+j=mapij; zzi*3+j=mapij; printf(n); if(judge(a)+judge(b)&1) printf(The final status cannot be reached .); return 0; printf(The searching process is:n); bfs(); return 0; 六、測試結(jié)果及說明 七、實驗體會 人工智能搜索可分為盲目搜索和啟發(fā)式搜索。盲目搜索算法有寬度優(yōu)先算法、深度優(yōu)先算法（有界深度優(yōu)先算法），啟發(fā)式搜索算法有A算法、A*算法。我在本實驗中，采用的是寬度優(yōu)先（廣度優(yōu)先）算法，這種算法是按預(yù)定的控制策略進行，在搜素的過程中所獲得的信息不用來改進控制策略。由于搜索總是按預(yù)定的路線進行，沒有考慮問題本身的特性，這種缺乏問題求解的針對性，需要進行全方位的搜索，而沒有選擇最優(yōu)的搜索路徑。通過這次實驗更加熟悉狀態(tài)空間的寬度優(yōu)先搜索、深度優(yōu)先搜索和啟發(fā)式搜索算法及計算機語言對常用數(shù)據(jù)結(jié)構(gòu)如鏈表、隊列等的描述應(yīng)用。因此，我對人工智能搜索有了更深的認識。 重慶交通大學計算機與信息學院驗證性實驗報告班 級： 軟件開發(fā) 專業(yè) 2013 級 1 班 學 號： 631306050105 姓 名： 何昭霞 實驗項目名稱： 啟發(fā)式搜索 實驗項目性質(zhì)： 驗證性實驗 實驗所屬課程： 人工智能 實驗室(中心)：軟件中心實驗室（語音樓8樓） 指 導 教 師 ： 朱振國 實驗完成時間： 2016 年 6 月 10 日評閱意見：實驗成績： 簽名： 年 月 日一、實驗?zāi)康?理解和掌握A*算法。二、實驗內(nèi)容及要求（一）實驗內(nèi)容在8數(shù)碼問題中，利用策略函數(shù)判斷搜索，并使用A*算法減少搜索目標。 （二）實驗要求 用選定的編程語言編寫程序，利用不同的搜索策略進行狀態(tài)空間搜索（如寬度優(yōu)先搜索、深度優(yōu)先搜索、有界深度優(yōu)先搜索等）。三、實驗設(shè)備及軟件 PC機一臺、Visual Studio 2012編程軟件四、設(shè)計方案 題目 啟發(fā)式搜索A*算法 設(shè)計的主要思路根據(jù)任務(wù)要求，該實驗我采用A*搜索算法。對于八數(shù)碼問題的解決,首先要考慮是否有答案。每一個狀態(tài)可認為是一個19的矩陣,問題即通過矩陣的變換,是否可以變換為目標狀態(tài)對應(yīng)的矩陣.由數(shù)學知識可知,可計算這兩個有序數(shù)列的逆序值,如果兩者都是偶數(shù)或奇數(shù),則可通過變換到達,否則,這兩個狀態(tài)不可達。這樣,就可以在具體解決問題之前判斷出問題是否可解,從而可以避免不必要的搜索。如果初始狀態(tài)可以到達目標狀態(tài),常用的狀態(tài)空間搜索有深度優(yōu)先和廣度優(yōu)先。廣度優(yōu)先是從初始狀態(tài)一層一層向下找,直到找到目標為止。深度優(yōu)先是按照一定的順序前查找完一個分支,再查找另一個分支,以至找到目標為止。在這里就要用到啟發(fā)式搜索啟發(fā)中的估價是用估價函數(shù)表示的,如:f(n)=g(n)+h(n)其中f(n)是節(jié)點n的估價函數(shù),g(n)是在狀態(tài)空間中從初始節(jié)點到n節(jié)點的實際代價,h(n)是從n到目標節(jié)點最佳路徑的估計代價。在此八數(shù)碼問題中,顯然g(n)就是從初始狀態(tài)變換到當前狀態(tài)所移動的步數(shù),估計函數(shù)f(n)我們就可采用當前狀態(tài)各個數(shù)字牌不在目標狀態(tài)未知的個數(shù),即錯位數(shù)。 1.狀態(tài)的表示 在A*算法中，需要用到open表和closed表，特別是在open表中，待擴展節(jié)點間有很嚴格的擴展順序。因此在表示當前狀態(tài)的變量中，與數(shù)據(jù)結(jié)構(gòu)中的鏈表相似，必須要有能指向下一個擴展節(jié)點的指針，以完成對open表中元素的索引。這里表示問題的結(jié)構(gòu)體包括表示當前節(jié)點狀態(tài)的DATA和指向open表中下一個待擴展節(jié)點的指針NEXT。其中DATA中包括的內(nèi)容采用一個的二維數(shù)組s33表示當前狀態(tài)的具體信息。而為了保證在搜索到目標狀態(tài)后能夠順利復現(xiàn)尋優(yōu)路徑，當前狀態(tài)的DATA中還應(yīng)該包括一個指向其父節(jié)點的指針father，這樣，才能在達到目標狀態(tài)后，通過指針father逐層回溯到初始狀態(tài)，即復現(xiàn)尋優(yōu)路徑。2.啟發(fā)函數(shù)的設(shè)計 根據(jù)A*算法的定義，啟發(fā)函數(shù)應(yīng)滿足：h(n)next = NULL; /判斷鏈表是否為空 bool isEmpty(PNode Head) if(Head-next = NULL) return true; else return false; /從鏈表中拿出一個數(shù)據(jù) void popNode(PNode &Head , PNode &FNode)if(isEmpty(Head) FNode = NULL; return; FNode = Head-next; Head-next = Head-next-next; FNode-next = NULL; /向結(jié)點的最終后繼結(jié)點鏈表中添加新的子結(jié)點void addSpringNode(PNode &Head , PNode newData) PSPLink newNode = (PSPLink)malloc(sizeof(SPLink); newNode-pointData = newData; newNode-next = Head-child; Head-child = newNode; /釋放狀態(tài)圖中存放結(jié)點后繼結(jié)點地址的空間 void freeSpringLink(PSPLink &Head) PSPLink tmm; while(Head != NULL) tmm = Head; Head = Head-next; free(tmm); /釋放open表與closed中的資源 void freeLink(PNode &Head) PNode tmn; tmn = Head; Head = Head-next; free(tmn); while(Head != NULL) /首先釋放存放結(jié)點后繼結(jié)點地址的空間freeSpringLink(Head-child); tmn = Head; computeAllValue(udNewNode , theNode); /將本結(jié)點加入后繼結(jié)點鏈表addNode(spring , udNewNode); /空的格子下邊的格子向上移動if(row != 2) PNode duNewNode = (PNode)malloc(sizeof(NNode); statusAEB(duNewNode , theNode); changeAB(duNewNode-datarowcol , duNewNode-datarow + 1col); if(hasAnceSameStatus(duNewNode , theNode-parent) free(duNewNode);/與父輩相同，丟棄本結(jié)點 else duNewNode-parent = theNode; duNewNode-child = NULL; duNewNode-next = NULL; computeAllValue(duNewNode , theNode); /將本結(jié)點加入后繼結(jié)點鏈表addNode(spring , duNewNode); /輸出給定結(jié)點的狀態(tài)void outputStatus(PNode stat) for(int i = 0 i 3 i+) for(int j = 0 j 3 j+) cout dataij ; cout gvalue; if(goal-parent != NULL) outputBestRoad(goal-parent); cout 第 deepnum- 層的狀態(tài)： endl; outputStatus(goal); void AStar() PNode tmpNode;/指向從open表中拿出并放到closed表中的結(jié)點的指針PNode spring;/tmpNode的后繼結(jié)點鏈PNode tmpLNode;/tmpNode的某一個后繼結(jié)點PNode tmpChartNode; PNode thePreNode;/指向?qū)⒁獜腸losed表中移到open表中的結(jié)點的前一個結(jié)點指針bool getGoal = false;/標識是否達到目標狀態(tài)long numcount = 1;/記錄從open表中拿出結(jié)點的序號initial();/對函數(shù)進行初始化initLink(spring);/對后繼鏈表的初始化tmpChartNode = NULL; cout 從open表中拿出的結(jié)點的狀態(tài)及相應(yīng)的值 endl; while(!isEmpty(open) /從open表中拿出f值最小的元素,并將拿出的元素放入closed表中popNode(open , tmpNode); addNode(closed , tmpNode); cout 第 numcount+ 個狀態(tài)是： endl; outputStatus(tmpNode); cout 其f值為： fvalue endl; cout 其g值為： gvalue endl; cout 其h值為： hvalue gvalue gvalue) tmpChartNode-parent = tmpLNode-parent; tmpChartNode-gvalue = tmpLNode-gvalue; tmpChartNode-fvalue = tmpLNode-fvalue; free(tmpLNode); /狀態(tài)在closed表中已經(jīng)存在else if(inLink(tmpLNode , closed , tmpChartNode , thePreNode) addSpringNode(tmpNode , tmpChartNode); if(tmpLNode-gvalue gvalue) PNode commu; tmpChartNode-parent = tmpLNode-parent; tmpChartNode-gvalue = tmpLNode-gvalue; tmpChartNode-fvalue = tmpLNode-fvalue; freeSpringLink(tmpChartNode-child); tmpChartNode-child = NULL; popNode(the