




版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
1、精選優質文檔-傾情為你奉上一、實驗內容和要求八數碼問題:在33的方格棋盤上,擺放著1到8這八個數碼,有1個方格是空的,其初始狀態如圖1所示,要求對空格執行空格左移、空格右移、空格上移和空格下移這四個操作使得棋盤從初始狀態到目標狀態。例如:28312316484705765(a) 初始狀態 (b) 目標狀態圖1 八數碼問題示意圖請任選一種盲目搜索算法(廣度優先搜索或深度優先搜索)或任選一種啟發式搜索方法(全局擇優搜索,加權狀態圖搜索,A 算法或 A* 算法)編程求解八數碼問題(初始狀態任選)。選擇一個初始狀態,畫出搜索樹,填寫相應的OPEN表和CLOSED表,給出解路徑,對實驗結果進行分析總結,
2、得出結論。二、實驗目的1. 熟悉人工智能系統中的問題求解過程;2. 熟悉狀態空間的盲目搜索和啟發式搜索算法的應用;3. 熟悉對八數碼問題的建模、求解及編程語言的應用。三、實驗算法A*算法是一種常用的啟發式搜索算法。在A*算法中,一個結點位置的好壞用估價函數來對它進行評估。A*算法的估價函數可表示為: f(n) = g(n) + h(n) 這里,f(n)是估價函數,g(n)是起點到終點的最短路徑值(也稱為最小耗費或最小代價),h(n)是n到目標的最短路經的啟發值。由于這個f(n)其實是無法預先知道的,所以實際上使用的是下面的估價函數:f(n) = g(n) + h(n) 其中g(n)是從初始結點
3、到節點n的實際代價,h(n)是從結點n到目標結點的最佳路徑的估計代價。在這里主要是h(n)體現了搜索的啟發信息,因為g(n)是已知的。用f(n)作為f(n)的近似,也就是用g(n)代替g(n),h(n)代替h(n)。這樣必須滿足兩個條件:(1)g(n)=g(n)(大多數情況下都是滿足的,可以不用考慮),且f必須保持單調遞增。(2)h必須小于等于實際的從當前節點到達目標節點的最小耗費h(n)=h(n)。第二點特別的重要。可以證明應用這樣的估價函數是可以找到最短路徑的。3.A*算法的步驟A*算法基本上與廣度優先算法相同,但是在擴展出一個結點后,要計算它的估價函數,并根據估價函數對待擴展的結點排序,
4、從而保證每次擴展的結點都是估價函數最小的結點。A*算法的步驟如下:1)建立一個隊列,計算初始結點的估價函數f,并將初始結點入隊,設置隊列頭和尾指針。2)取出隊列頭(隊列頭指針所指)的結點,如果該結點是目標結點,則輸出路徑,程序結束。否則對結點進行擴展。 3)檢查擴展出的新結點是否與隊列中的結點重復,若與不能再擴展的結點重復(位于隊列頭指針之前),則將它拋棄;若新結點與待擴展的結點重復(位于隊列頭指針之后),則比較兩個結點的估價函數中g的大小,保留較小g值的結點。跳至第五步。4)如果擴展出的新結點與隊列中的結點不重復,則按照它的估價函數f大小將它插入隊列中的頭結點后待擴展結點的適當位置,使它們按
5、從小到大的順序排列,最后更新隊列尾指針。5)如果隊列頭的結點還可以擴展,直接返回第二步。否則將隊列頭指針指向下一結點,再返回第二步。四、程序框圖五、實驗結果及分析輸入初始狀態:2 8 3目標狀態:1 2 31 6 48 0 47 0 57 6 5運行結果屏幕打印OPEN表與CLOSE表:OPENCLOSE1 2 3 4 02 3 4 5 60 12 3 4 6 70 1 52 3 4 6 8 90 1 5 72 3 4 8 9 100 1 5 7 62 3 4 8 11 12 13 0 1 5 7 6 92 3 4 8 12 13 14 150 1 5 7 6 9 113 4 8 12 13
6、14 15 16 170 1 5 7 6 9 11 24 8 12 13 14 15 16 17 18 190 1 5 7 6 9 11 2 34 8 12 13 14 15 16 17 19 200 1 5 7 6 9 11 2 3 188 12 13 14 15 16 17 19 21 220 1 5 7 6 9 11 2 3 18 412 13 14 15 16 17 19 21 22 230 1 5 7 6 9 11 2 3 18 4 812 13 14 15 16 17 19 21 22 24 250 1 5 7 6 9 11 2 3 18 4 8 2312 13 14 15 16
7、17 19 21 22 24 260 1 5 7 6 9 11 2 3 18 4 8 23 24發現26為目標節點072 8 31 0 47 6 5搜索樹:2.112 8 31 6 47 0 5172 0 31 8 47 6 54.112 8 31 4 07 6 53.112 8 30 1 47 6 522.142 8 31 4 57 6 019.122 8 37 1 40 6 521.122 8 31 4 37 6 518.100 8 32 1 47 6 511.142 8 31 6 47 5 010.142 8 31 6 47 0 5692 3 01 8 47 6 5580 2 31 8
8、47 6 5791 2 30 8 47 6 510.112 3 41 8 07 6 520.118 0 32 1 47 6 5注釋:每個方格中最上面兩個數字分別為編號與啟發值,下面九個數字為八數碼。較粗的箭頭為解路徑8.121 2 37 8 40 6 59.101 2 38 0 47 6 511.91 0 38 2 47 6 523.91 2 37 8 46 0 513.131 2 38 4 07 6 512.131 2 38 6 47 0 524.81 2 37 0 46 8 525.121 2 37 8 46 5 014.120 1 38 2 47 6 515.143 1 08 2 47
9、6 5目標節點六、結論對于八數碼問題,BFS算法最慢,A*算法較快。八數碼問題的一個狀態實際上是09的一個排列,對于任意給定的初始狀態和目標,不一定有解,也就是說從初始狀態不一定能到達目標狀態。因為排列有奇排列和偶排列兩類,從奇排列不能轉化成偶排列。如果一個數字08的隨機排列,用F(X)表示數字X前面比它小的數的個數,全部數字的F(X)之和為Y=(F(X),如果Y為奇數則稱原數字的排列是奇排列,如果Y為偶數則稱原數字的排列是偶排列。因此,可以在運行程序前檢查初始狀態和目標狀態的排序的奇偶行是否相同,相同則問題可解,應當能搜索到路徑。否則無解。七、源程序及注釋#include #include
10、#include using namespace std;const int ROW = 3;const int COL = 3;const int MAXDISTANCE = 10000;const int MAXNUM = 10000;int abs(int a)if (a0) return a;else return -a;typedef struct _Nodeint digitROWCOL;int dist; / 距離 int dep; / 深度 int index; / 索引值 Node;Node src, dest;vector node_v; / 儲存節點 bool isEmp
11、tyOfOPEN() /判斷Open表是否空 for (int i = 0; i node_v.size(); i+) if (node_vi.dist != MAXNUM) return false;return true;bool isEqual(int index, int digitCOL) /判斷節點是否與索引值指向的節點相同 for (int i = 0; i ROW; i+) for (int j = 0; j COL; j+) if (node_vindex.digitij != digitij) return false; return true;ostream& opera
12、tor(ostream& os, Node& node) for (int i = 0; i ROW; i+) for (int j = 0; j COL; j+) os node.digitij ; os endl;return os;void PrintSteps(int index, vector& rstep_v) /輸出步驟 rstep_v.push_back(node_vindex);index = node_vindex.index;while (index != 0) rstep_v.push_back(node_vindex); index = node_vindex.ind
13、ex;for (int i = rstep_v.size() - 1; i = 0; i-) cout Step rstep_v.size() - i endl rstep_vi endl;void Swap(int& a, int& b) /交換 int t;t = a;a = b;b = t;void Assign(Node& node, int index) /獲取節點 for (int i = 0; i ROW; i+) for (int j = 0; j COL; j+) node.digitij = node_vindex.digitij;int GetMinNode() /獲取啟
14、發值最小的節點 int dist = MAXNUM;int loc; / the location of minimize nodefor (int i = 0; i node_v.size(); i+) if (node_vi.dist = MAXNUM) continue; else if (node_vi.dist + node_vi.dep) dist) loc = i; dist = node_vi.dist + node_vi.dep; return loc;bool isExpandable(Node& node) /判斷是否可擴展 for (int i = 0; i node_
15、v.size(); i+) if (isEqual(i, node.digit) return false;return true;int Distance(Node& node, int digitCOL) /計算距離 int distance = 0;bool flag = false;for(int i = 0; i ROW; i+) for (int j = 0; j COL; j+) for (int k = 0; k ROW; k+) for (int l = 0; l COL; l+) if (node.digitij = digitkl) distance += abs(i -
16、 k) + abs(j - l); flag = true; break; else flag = false; if (flag) break; return distance;int MinDistance(int a, int b) /二者取小 return (a b ? a : b);void ProcessNode(int index) /展開節點 int x, y;bool flag;for (int i = 0; i ROW; i+) for (int j = 0; j 0) Swap(node_up.digitxy, node_up.digitx - 1y); if (isEx
17、pandable(node_up) dist_up = Distance(node_up, dest.digit); node_up.index = index; node_up.dist = dist_up; node_up.dep = node_vindex.dep + 1; node_v.push_back(node_up); Node node_down; /下移操作Assign(node_down, index);int dist_down = MAXDISTANCE;if (x 0) Swap(node_left.digitxy, node_left.digitxy - 1); i
18、f (isExpandable(node_left) dist_left = Distance(node_left, dest.digit); node_left.index = index; node_left.dist = dist_left; node_left.dep = node_vindex.dep + 1; node_v.push_back(node_left); Node node_right; /右移操作Assign(node_right, index);int dist_right = MAXDISTANCE;if (y 2) Swap(node_right.digitxy, node_right.digitxy + 1); if (isExpandable(node_right) dist_right = Distance(node_right, dest.digit); node_right.index = index; node_right.dist = dist_right; node_right.dep = node_
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025股份制合同協議范本編寫
- 職稱評聘協議書
- 資金規范協議書
- 遂寧搬遷協議書
- 電費代扣協議書
- 穩定價格協議書
- 豬頭收購協議書
- 小米無線充電寶協議書
- 加油站建設合作協議書
- 英文縮寫協議書
- 小型設備購買協議書
- 難點02:總集篇·十六種陰影部分面積法【十六大考點】-2024年小升初數學典型例題系列(解析版)
- 廠房設備拆除協議書
- 2025屆高三高考押題預測卷 數學(新高考Ⅱ卷02) 含解析
- 智能家居安裝與調試協議
- 擔保貸款免責協議書
- 第五版-FMEA培訓教材-新版
- NB-T32036-2017光伏發電工程達標投產驗收規程
- 食品安全與日常飲食智慧樹知到期末考試答案章節答案2024年中國農業大學
- PE袋化學品安全技術說明書MSDS(聚乙烯塑膠袋)
- 醫院檢驗科實驗室生物安全管理手冊
評論
0/150
提交評論