昆明理工大學(xué)人工智能導(dǎo)論實驗報告模板

1、昆明理工大學(xué)信息工程與自動化學(xué)院學(xué)生實驗報告（ 2013 2014 學(xué)年 第 一 學(xué)期 ）課程名稱：人工智能導(dǎo)論 開課實驗室：信自樓234室 2013年10月29日年級、專業(yè)、班2011級測控專業(yè)學(xué)號201110402137姓名陳文武成績實驗項目名稱狀態(tài)空間搜索實驗八數(shù)碼問題求解指導(dǎo)教師教師評語該同學(xué)是否了解實驗原理： A.了解 B.基本了解 C.不了解 該同學(xué)的實驗?zāi)芰Γ?A.強 B.中等 C.差 該同學(xué)的實驗是否達到要求 ： A.達到 B.基本達到 C.未達到實驗報告是否規(guī)范： A.規(guī)范 B.基本規(guī)范 C.不規(guī)范實驗過程是否詳細(xì)記錄： A.詳細(xì) B.一般 C.沒有 教師簽名： 年 月 日目

2、 錄一、實驗問題2二、實驗?zāi)康?三、實驗原理2A搜索的原理：2估價函數(shù)：2重要程序分析：3四、程序框圖4五、實驗結(jié)果及分析5隨機檢驗15隨機檢驗26隨機檢驗37隨機檢驗47六、結(jié)論9七、源程序及注釋1013 人工智能導(dǎo)論 測控 陳文武 一、實驗問題八數(shù)碼問題的求解，及程序設(shè)計。具體要求如下在3*3的方格中的棋盤中任意擺放1到8個自然數(shù)和一個空格，其初始狀態(tài)如下：254307186a初始狀態(tài) 123804765b目標(biāo)狀態(tài) 請選擇一種盲目搜索的算法或選擇一種啟發(fā)式搜索的算法編程求解八數(shù)碼問題，初始狀態(tài)任選，并對使用進行合理分析做出合理結(jié)果。二、實驗?zāi)康?、熟悉人工智能系統(tǒng)中的問題求解過程；2、熟悉

3、狀態(tài)空間的滿目搜索和啟發(fā)式搜索算法的運用；3、熟悉對八碼數(shù)問題的建模、求解及編程語言的運用；三、實驗原理經(jīng)過分析，8數(shù)碼問題中可采用的搜速策略共有：1.廣度優(yōu)先搜索2.深度優(yōu)先搜索2.有界深度優(yōu)先搜索4.最好優(yōu)先搜索5.局部擇優(yōu)搜索一共五種。其中，廣度優(yōu)先搜索法是可采納的，有界深度優(yōu)先搜索法是不完備的，最好優(yōu)先和局部擇優(yōu)搜索法是啟發(fā)式搜索法。在實驗時，我采用了啟發(fā)式搜索中的最好優(yōu)先來實現(xiàn)。啟發(fā)式搜索算法有A算法、A*算法。本次實驗采用了A算法得到結(jié)果。A搜索的原理：A算法搜索就是在狀態(tài)空間中的搜索對每一個搜索的位置進行評估，得到最好的位置，再從這個位置進行搜索直到目標(biāo)。這樣可以省略大量無謂的搜

4、索路徑，提高了效率。在啟發(fā)式搜索中，對位置的估價是十分重要的。采用了不同的估價可以有不同的效果。估價函數(shù)：計算一個節(jié)點的估價函數(shù)，可以分成兩個部分：1、 已經(jīng)付出的代價（起始節(jié)點到當(dāng)前節(jié)點）；2、 將要付出的代價（當(dāng)前節(jié)點到目標(biāo)節(jié)點）。節(jié)點n的估價函數(shù)定義為從初始節(jié)點、經(jīng)過n、到達目標(biāo)節(jié)點的路徑的最小代價的估計值，即 = + 。是從初始節(jié)點到達當(dāng)前節(jié)點n的實際代價； 是從節(jié)點n到目標(biāo)節(jié)點的最佳路徑的估計代價，體現(xiàn)出搜索過程中采用的啟發(fā)式信息（背景知識），稱之為啟發(fā)函數(shù)。所占的比重越大，越趨向于寬度優(yōu)先或等代價搜索；反之，的比重越大，表示啟發(fā)性能就越強。本實驗中我們使用函數(shù)，其值是節(jié)點n與目標(biāo)狀

5、態(tài)節(jié)點相比較，每個錯位棋牌在假設(shè)不受阻攔的情況下，移動到目標(biāo)狀態(tài)相應(yīng)位置所需走步（移動次數(shù)）的總和。顯然比更接近于，因為不僅考慮了錯位因素，還考慮了錯位的距離。重要程序分析：1.結(jié)點狀態(tài) 我采用了struct Node數(shù)據(jù)類型typedef struct _Nodeint digitROWCOL;int dist; / distance between one state and the destination一個表和目的表的距離int dep; / the depth of node深度/ So the comment function = dist + dep.估價函數(shù)值int index

6、; / point to the location of parent父節(jié)點的位置 Node; 2.發(fā)生器函數(shù) 定義的發(fā)生器函數(shù)由以下的四種操作組成： (1)將當(dāng)前狀態(tài)的空格上移 Node node_up;Assign(node_up, index);/向上擴展的節(jié)點int dist_up = MAXDISTANCE;(2)將當(dāng)前狀態(tài)的空格下移 Node node_down;Assign(node_down, index);/向下擴展的節(jié)點int dist_down = MAXDISTANCE; (3)將當(dāng)前狀態(tài)的空格左移 Node node_left;Assign(node_left, in

7、dex);/向左擴展的節(jié)點int dist_left = MAXDISTANCE; (4)將當(dāng)前狀態(tài)的空格右移Node node_right;Assign(node_right, index);/向右擴展的節(jié)點int dist_right = MAXDISTANCE;通過定義結(jié)點狀態(tài)和發(fā)生器函數(shù)，就解決了8數(shù)碼問題的隱式圖的生成問題。接下來就是搜索了。四、程序框圖流程圖文字解釋：1、 把附有f（S0）的初始節(jié)點S0放入OPEN。2、 若OPEN為空（NIL），則搜索失敗，退出。3、 移除OPEN表中第一個節(jié)點放入表中，并加標(biāo)號。4、 若目標(biāo)節(jié)點，則搜索成功，結(jié)束。5、 若不可擴散，則轉(zhuǎn)。6、

8、若擴展，計算每個子節(jié)點函數(shù)f（x），對著組數(shù)據(jù)做以下處理：（1）、考察是否有已經(jīng)存在的OPEN表或CLOSED表中存在的節(jié)點；若存在則考察有無N的先輩節(jié)點，若有則刪除它；對于其余的子節(jié)點，也刪除它，但他們又被第二次生成，因而需要考慮修改已經(jīng)存在的OPEN表或CLOSED表中的這些節(jié)點及其后裔的返回指針和f（x）值，修改原則是“抄f（x）值小的路走”。（2）對其余的子節(jié)點配上指向N的返回指針后放入OPEN表中，并對OPEN表按照f（x）值升序排序，轉(zhuǎn)2。7、 以下是流程框圖：五、實驗結(jié)果及分析隨機檢驗1初始狀態(tài)為：254307186的運行結(jié)果為：經(jīng)過運行，該八數(shù)碼搜索不到原結(jié)果。隨機檢驗2初始狀

9、態(tài)為：283104765的運行結(jié)果為：經(jīng)過運行，搜索結(jié)果如圖，本次搜索經(jīng)過了4個步驟。隨機檢驗3初始狀態(tài)為：123084765運行結(jié)果為：經(jīng)過運行搜索結(jié)果如圖，經(jīng)過了1步搜索成功。隨機檢驗4初始狀態(tài)為：124703865運行結(jié)果為：運行結(jié)果如圖，經(jīng)過了16個步驟搜索成功。經(jīng)過隨機驗證了4組數(shù)據(jù)，有一組沒出結(jié)果，并且有些隨機數(shù)組搜索不出結(jié)果，現(xiàn)在我還找不到是程序錯誤還是數(shù)組本身性質(zhì)。六、結(jié)論通過本次試驗，對典型的啟發(fā)式搜索的A算法又了更清晰的認(rèn)識和運用。從所擴展的節(jié)點數(shù)來看，看來比更加有效，能在復(fù)雜情況下求得更加優(yōu)質(zhì)的解，避免不必要的節(jié)點的擴展。但是對于估價函數(shù)來說，它的定義趨向多元化，只是它的

10、一個比較好的特例，對一復(fù)雜的搜索問題，如國際象棋問題，他就顯得較簡單。所以，要更好地定義一個估價函數(shù)還有待深入討論。在尋找最佳擴展路徑的過程中我發(fā)現(xiàn)，最佳擴展路基上的節(jié)點均在CLOSED表中，利用標(biāo)志flag，以及它們之間的父子關(guān)系，我很容易的就找到了擴展路徑，避免了再用一個路徑指針path來找到路徑，這樣節(jié)省了存儲空間，更利于搜索。七、源程序及注釋#include <iostream>#include <ctime>#include <vector>using namespace std;const int ROW = 3;/行數(shù)const int COL

11、 = 3;/列數(shù)const int MAXDISTANCE = 10000;/最多可以有的表的數(shù)目const int MAXNUM = 10000;typedef struct _Node int digitROWCOL; int dist; / distance between one state and the destination一個表和目的表的距離 int dep; / the depth of node深度 / So the comment function = dist + dep.估價函數(shù)值 int index; / point to the location of paren

12、t父節(jié)點的位置 Node;Node src, dest;/ 父節(jié)表 目的表vector<Node> node_v; / store the nodes存儲節(jié)點bool isEmptyOfOPEN() /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) /判斷這個最優(yōu)的節(jié)點是否和目的節(jié)點一樣 for (int i = 0; i < ROW; i

13、+) for (int j = 0; j < COL; j+) if (node_vindex.digitij != digitij) return false; return true;ostream& operator<<(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;vo

14、id PrintSteps(int index, vector<Node>& rstep_v)/輸出每一個遍歷的節(jié)點 深度遍歷 rstep_v.push_back(node_vindex); index = node_vindex.index; while (index != 0) rstep_v.push_back(node_vindex); index = node_vindex.index; for (int i = rstep_v.size() - 1; i >= 0; i-)/輸出每一步的探索過程 cout << "Step "

15、; << 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() /找到最小的節(jié)點

16、的位置 即最優(yōu)節(jié)點 int dist = MAXNUM; int loc; / the location of minimize node for (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

17、; i < node_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.dig

18、itij = digitkl) distance += abs(i - 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 < COL; j+) if (no

19、de_vindex.digitij = 0) x =i; y = j; flag = true; break; else flag = false; if(flag) break; Node node_up; Assign(node_up, index);/向上擴展的節(jié)點 int dist_up = MAXDISTANCE; if (x > 0) Swap(node_up.digitxy, node_up.digitx - 1y); if (isExpandable(node_up) dist_up = Distance(node_up, dest.digit); node_up.ind

20、ex = 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);/向下擴展的節(jié)點 int dist_down = MAXDISTANCE; if (x < 2) Swap(node_down.digitxy, node_down.digitx + 1y); if (isExpandable(node_down) dist_down = Distance(node_down, d

21、est.digit); node_down.index = index; node_down.dist = dist_down; node_down.dep = node_vindex.dep + 1; node_v.push_back(node_down); Node node_left; Assign(node_left, index);/向左擴展的節(jié)點 int dist_left = MAXDISTANCE; if (y > 0) Swap(node_left.digitxy, node_left.digitxy - 1); if (isExpandable(node_left)

22、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);/向右擴展的節(jié)點 int dist_right = MAXDISTANCE; if (y < 2) Swap(node_right.digitxy, node_right.digi

23、txy + 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_vindex.dep + 1; node_v.push_back(node_right); node_vindex.dist = MAXNUM;int main() / 主函數(shù) int number; cout << "Input source:" << endl; for (int i = 0; i < ROW; i+)/輸入初始的表 for (int j = 0; j < COL; j+) cin >> number; src.digitij = number; src.index = 0; src.dep = 1; cout << "Input destination:" << endl;/輸入目