重慶交通大學計算機與信息學院驗證性實驗報告班 級： 軟件開發 專業 2013 級 1 班 學 號： 631306050105 姓 名： 何昭霞 實驗項目名稱： 狀態空間搜索 實驗項目性質： 驗證性實驗 實驗所屬課程： 人工智能 實驗室(中心)：軟件中心實驗室（語音樓8樓） 指 導 教 師 ： 朱振國 實驗完成時間： 2016 年 6 月 10 日評閱意見：實驗成績： 簽名： 年 月 日一、實驗目的 1. 理解和掌握狀態空間搜索的策略。 2.熟悉人工智能系統中的問題求解過程； 3.熟悉狀態空間的盲目搜索和啟發式搜索算法的應用； 4.熟悉對八數碼問題的建模、求解及編程語言的應用。二、實驗內容及要求（一）實驗內容在一個3*3的九宮中有1-8個數碼及一個空格隨即的擺放在其中的格子里，現在要求實驗這個問題：將該九宮格調整為某種有序的形式。調整的規則是，每次只能將與空格（上、下、左、右）相鄰的一個數字平移到空格中。 （二）實驗要求 用選定的編程語言編寫程序，利用不同的搜索策略進行狀態空間搜索（如寬度優先搜索、深度優先搜索、有界深度優先搜索等）。三、實驗設備及軟件 PC機一臺、Visual Studio 2012編程軟件四、設計方案 題目 狀態空間搜索 8數碼問題 設計的主要思路考慮廣度優先算法：(1) 狀態空間盲目搜索寬度優先搜索其基本思想是，從初始節點開始，向下逐層對節點進形依次擴展，并考察它是否為目標節點，再對下層節點進行擴展（或搜索）之前，必須完成對當層的所有節點的擴展。再搜索過程中，未擴展節點表OPEN中的節點排序準則是：先進入的節點排在前面，后進入的節點排在后面。(2) 寬度優先算法如下首先把初始結點S0放入OPEN表中，然后若OPEN表為空，則搜索失敗，問題無解，接著取OPEN表中最前面的結點N放在CLOSE表中，并冠以順序編號n，若目標結點Sg=N，則搜索成功，問題有解。若N無子結點，則重復取OPEN表中最前面的結點N放在CLOSE表中。擴展結點N，將其所有子結點配上指向N的放回指針，依次放入OPEN表的尾部，然后重復取OPEN表中最前面的結點N放在CLOSE表中。 根據算法的中心思想進行程序設計，其流程圖如下圖所示。 主要功能使用C語言相關知識，將3*3的九宮格調整為某種有序的形式。五、主要代碼#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數目最小的擴展 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; 六、測試結果及說明 七、實驗體會 人工智能搜索可分為盲目搜索和啟發式搜索。盲目搜索算法有寬度優先算法、深度優先算法（有界深度優先算法），啟發式搜索算法有A算法、A*算法。我在本實驗中，采用的是寬度優先（廣度優先）算法，這種算法是按預定的控制策略進行，在搜素的過程中所獲得的信息不用來改進控制策略。由于搜索總是按預定的路線進行，沒有考慮問題本身的特性，這種缺乏問題求解的針對性，需要進行全方位的搜索，而沒有選擇最優的搜索路徑。通過這次實驗更加熟悉狀態空間的寬度優先搜索、深度優先搜索和啟發式搜索算法及計算機語言對常用數據結構如鏈表、隊列等的描述應用。因此，我對人工智能搜索有了更深的認識。 重慶交通大學計算機與信息學院驗證性實驗報告班 級： 軟件開發 專業 2013 級 1 班 學 號： 631306050105 姓 名： 何昭霞 實驗項目名稱： 啟發式搜索 實驗項目性質： 驗證性實驗 實驗所屬課程： 人工智能 實驗室(中心)：軟件中心實驗室（語音樓8樓） 指 導 教 師 ： 朱振國 實驗完成時間： 2016 年 6 月 10 日評閱意見：實驗成績： 簽名： 年 月 日一、實驗目的 理解和掌握A*算法。二、實驗內容及要求（一）實驗內容在8數碼問題中，利用策略函數判斷搜索，并使用A*算法減少搜索目標。 （二）實驗要求 用選定的編程語言編寫程序，利用不同的搜索策略進行狀態空間搜索（如寬度優先搜索、深度優先搜索、有界深度優先搜索等）。三、實驗設備及軟件 PC機一臺、Visual Studio 2012編程軟件四、設計方案 題目 啟發式搜索A*算法 設計的主要思路根據任務要求，該實驗我采用A*搜索算法。對于八數碼問題的解決,首先要考慮是否有答案。每一個狀態可認為是一個19的矩陣,問題即通過矩陣的變換,是否可以變換為目標狀態對應的矩陣.由數學知識可知,可計算這兩個有序數列的逆序值,如果兩者都是偶數或奇數,則可通過變換到達,否則,這兩個狀態不可達。這樣,就可以在具體解決問題之前判斷出問題是否可解,從而可以避免不必要的搜索。如果初始狀態可以到達目標狀態,常用的狀態空間搜索有深度優先和廣度優先。廣度優先是從初始狀態一層一層向下找,直到找到目標為止。深度優先是按照一定的順序前查找完一個分支,再查找另一個分支,以至找到目標為止。在這里就要用到啟發式搜索啟發中的估價是用估價函數表示的,如:f(n)=g(n)+h(n)其中f(n)是節點n的估價函數,g(n)是在狀態空間中從初始節點到n節點的實際代價,h(n)是從n到目標節點最佳路徑的估計代價。在此八數碼問題中,顯然g(n)就是從初始狀態變換到當前狀態所移動的步數,估計函數f(n)我們就可采用當前狀態各個數字牌不在目標狀態未知的個數,即錯位數。 1.狀態的表示 在A*算法中，需要用到open表和closed表，特別是在open表中，待擴展節點間有很嚴格的擴展順序。因此在表示當前狀態的變量中，與數據結構中的鏈表相似，必須要有能指向下一個擴展節點的指針，以完成對open表中元素的索引。這里表示問題的結構體包括表示當前節點狀態的DATA和指向open表中下一個待擴展節點的指針NEXT。其中DATA中包括的內容采用一個的二維數組s33表示當前狀態的具體信息。而為了保證在搜索到目標狀態后能夠順利復現尋優路徑，當前狀態的DATA中還應該包括一個指向其父節點的指針father，這樣，才能在達到目標狀態后，通過指針father逐層回溯到初始狀態，即復現尋優路徑。2.啟發函數的設計 根據A*算法的定義，啟發函數應滿足：h(n)next = NULL; /判斷鏈表是否為空 bool isEmpty(PNode Head) if(Head-next = NULL) return true; else return false; /從鏈表中拿出一個數據 void popNode(PNode &Head , PNode &FNode)if(isEmpty(Head) FNode = NULL; return; FNode = Head-next; Head-next = Head-next-next; FNode-next = NULL; /向結點的最終后繼結點鏈表中添加新的子結點void addSpringNode(PNode &Head , PNode newData) PSPLink newNode = (PSPLink)malloc(sizeof(SPLink); newNode-pointData = newData; newNode-next = Head-child; Head-child = newNode; /釋放狀態圖中存放結點后繼結點地址的空間 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) /首先釋放存放結點后繼結點地址的空間freeSpringLink(Head-child); tmn = Head; computeAllValue(udNewNode , theNode); /將本結點加入后繼結點鏈表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);/與父輩相同，丟棄本結點 else duNewNode-parent = theNode; duNewNode-child = NULL; duNewNode-next = NULL; computeAllValue(duNewNode , theNode); /將本結點加入后繼結點鏈表addNode(spring , duNewNode); /輸出給定結點的狀態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- 層的狀態： endl; outputStatus(goal); void AStar() PNode tmpNode;/指向從open表中拿出并放到closed表中的結點的指針PNode spring;/tmpNode的后繼結點鏈PNode tmpLNode;/tmpNode的某一個后繼結點PNode tmpChartNode; PNode thePreNode;/指向將要從closed表中移到open表中的結點的前一個結點指針bool getGoal = false;/標識是否達到目標狀態long numcount = 1;/記錄從open表中拿出結點的序號initial();/對函數進行初始化initLink(spring);/對后繼鏈表的初始化tmpChartNode = NULL; cout 從open表中拿出的結點的狀態及相應的值 endl; while(!isEmpty(open) /從open表中拿出f值最小的元素,并將拿出的元素放入closed表中popNode(open , tmpNode); addNode(closed , tmpNode); cout 第 numcount+ 個狀態是： 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); /狀態在closed表中已經存在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