八數(shù)碼問(wèn)題求解--實(shí)驗(yàn)報(bào)告

1、 實(shí) 驗(yàn) 報(bào) 告一、實(shí)驗(yàn)問(wèn)題八數(shù)碼問(wèn)題求解二、實(shí)驗(yàn)軟件 VC6.0 編程語(yǔ)言或其它編程語(yǔ)言 三、實(shí)驗(yàn)?zāi)康?1. 熟悉人工智能系統(tǒng)中的問(wèn)題求解過(guò)程； 2. 熟悉狀態(tài)空間的盲目搜索和啟發(fā)式搜索算法的應(yīng)用； 3. 熟悉對(duì)八數(shù)碼問(wèn)題的建模、求解及編程語(yǔ)言的應(yīng)用。 四、實(shí)驗(yàn)數(shù)據(jù)及步驟 （一、） 實(shí)驗(yàn)內(nèi)容 八數(shù)碼問(wèn)題：在3×3的方格棋盤上，擺放著1到8這八個(gè)數(shù)碼，有1個(gè)方格是空的，其初始狀態(tài)如圖1所示，要求對(duì)空格執(zhí)行空格左移、空格右移、空格上移和空格下移這四個(gè)操作使得棋盤從初始狀態(tài)到目標(biāo)狀態(tài)。 2 8 3 1 2 3 1 4 8 4 7 6 5 7 6 5 (a) 初始狀態(tài) (b) 目標(biāo)狀態(tài) 圖

2、 1 八數(shù)碼問(wèn)題示意圖 （二、）基本數(shù)據(jù)結(jié)構(gòu)分析和實(shí)現(xiàn)1.結(jié)點(diǎn)狀態(tài) 我采用了struct Node數(shù)據(jù)類型typedef struct _Node int digitROWCOL; int dist; / distance between one state and the destination一個(gè)表和目的表的距離 int dep; / the depth of node深度 / So the comment function = dist + dep.估價(jià)函數(shù)值 int index; / point to the location of parent父節(jié)點(diǎn)的位置 Node; 2.發(fā)生器函數(shù)

3、 定義的發(fā)生器函數(shù)由以下的四種操作組成： (1)將當(dāng)前狀態(tài)的空格上移 Node node_up; Assign(node_up, index);/向上擴(kuò)展的節(jié)點(diǎn)int dist_up = MAXDISTANCE; (2)將當(dāng)前狀態(tài)的空格下移 Node node_down; Assign(node_down, index);/向下擴(kuò)展的節(jié)點(diǎn) int dist_down = MAXDISTANCE; (3)將當(dāng)前狀態(tài)的空格左移 Node node_left; Assign(node_left, index);/向左擴(kuò)展的節(jié)點(diǎn) int dist_left = MAXDISTANCE; (4)將當(dāng)前狀

4、態(tài)的空格右移Node node_right; Assign(node_right, index);/向右擴(kuò)展的節(jié)點(diǎn) int dist_right = MAXDISTANCE;通過(guò)定義結(jié)點(diǎn)狀態(tài)和發(fā)生器函數(shù)，就解決了8數(shù)碼問(wèn)題的隱式圖的生成問(wèn)題。接下來(lái)就是搜索了。3.圖的搜索策略經(jīng)過(guò)分析，8數(shù)碼問(wèn)題中可采用的搜速策略共有：1.廣度優(yōu)先搜索、2.深度優(yōu)先搜索、2.有界深度優(yōu)先搜索、4.最好優(yōu)先搜索、5.局部擇優(yōu)搜索，一共五種。其中，廣度優(yōu)先搜索法是可采納的，有界深度優(yōu)先搜索法是不完備的，最好優(yōu)先和局部擇優(yōu)搜索法是啟發(fā)式搜索法。 實(shí)驗(yàn)時(shí),采用了廣度(寬度)優(yōu)先搜索來(lái)實(shí)現(xiàn)。（三、）廣度(寬度)優(yōu)先搜索原

5、理 1. 狀態(tài)空間盲目搜索寬度優(yōu)先搜索 其基本思想是，從初始節(jié)點(diǎn)開始，向下逐層對(duì)節(jié)點(diǎn)進(jìn)形依次擴(kuò)展，并考察它是否為目標(biāo)節(jié)點(diǎn)，再對(duì)下層節(jié)點(diǎn)進(jìn)行擴(kuò)展（或搜索）之前，必須完成對(duì)當(dāng)層的所有節(jié)點(diǎn)的擴(kuò)展。再搜索過(guò)程中，未擴(kuò)展節(jié)點(diǎn)表OPEN中的節(jié)點(diǎn)排序準(zhǔn)則是：先進(jìn)入的節(jié)點(diǎn)排在前面，后進(jìn)入的節(jié)點(diǎn)排在后面。其搜索過(guò)程如圖（1）所示。 SABCFDEGHIJ 圖2、寬度優(yōu)先搜索示意圖 2. 寬度優(yōu)先算法如下： 步1 把初始結(jié)點(diǎn)S0放入OPEN表中 步2 若OPEN表為空，則搜索失敗，問(wèn)題無(wú)解 步3 取OPEN表中最前面的結(jié)點(diǎn)N放在CLOSE表中，并冠以順序編號(hào)n 步4 若目標(biāo)結(jié)點(diǎn)Sg=N，則搜索成功，問(wèn)題有解 步5

6、 若N無(wú)子結(jié)點(diǎn)，則轉(zhuǎn)步2 步6 擴(kuò)展結(jié)點(diǎn)N，將其所有子結(jié)點(diǎn)配上指向N的放回指針，依次放入OPEN表的尾部，轉(zhuǎn)步2 3.寬度優(yōu)先算法流程圖 起始 把S放入OPEN表Fangru 否是OPEN是否為空表?失敗把第一個(gè)節(jié)點(diǎn)n,從OPEN表移出,并把它放入CLOSED表擴(kuò)展n,把它的后繼節(jié)點(diǎn)放入OPEN表的末端,提供回到n的指針是否有任何后繼節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)?否是成功 圖3、寬度優(yōu)先算法流程圖 48數(shù)碼難題用寬度優(yōu)先搜索所生成的搜索樹如圖4。搜索樹上的所有節(jié)點(diǎn)都標(biāo)記它們所對(duì)應(yīng)的狀態(tài)描述，每個(gè)節(jié)點(diǎn)旁邊的數(shù)字表示節(jié)點(diǎn)擴(kuò)展的順序（按順時(shí)針?lè)较蛞苿?dòng)空格）。圖中有26個(gè)節(jié)點(diǎn)，也就是源程序運(yùn)行結(jié)果。2 8

7、 31 0 47 6 5 1 So2 8 31 4 07 6 52 0 31 8 47 6 52 8 30 1 47 6 52 8 31 6 47 0 5 2 3 4 5 6 7 8 9 10 11 12 130 8 32 1 47 6 50 2 31 8 47 6 52 3 01 8 47 6 52 8 31 4 57 6 02 8 01 4 37 6 52 8 31 6 47 5 02 8 31 6 40 6 52 8 37 1 40 6 5 14 15 16 17 18 19 20 21 1 2 30 8 47 6 52 0 32 1 47 6 52 8 37 1 46 0 52 3 4

8、1 8 07 6 52 8 31 6 07 5 42 8 30 6 41 7 52 8 31 4 57 0 62 0 81 4 37 5 6 22 23 24 25 261 2 38 0 47 6 52 8 37 1 46 5 02 8 37 0 46 1 58 3 02 1 47 6 58 8 32 0 47 6 5圖4.八數(shù)碼題寬度優(yōu)先搜索樹五、實(shí)驗(yàn)結(jié)果及分析 上機(jī)試驗(yàn)時(shí),，經(jīng)多次程序調(diào)試，最后得一下結(jié)果。此結(jié)果所得節(jié)點(diǎn)（狀態(tài)圖）很多 ，可知寬度優(yōu)先搜索的盲目性很大，當(dāng)目標(biāo)節(jié)點(diǎn)距離初始節(jié)點(diǎn)較遠(yuǎn)時(shí)，就會(huì)產(chǎn)生大量的無(wú)用節(jié)點(diǎn)，搜索效率低。但是，只要問(wèn)題有解，用寬度優(yōu)先搜索總可以找到它的解。 圖5

9、.程序運(yùn)行結(jié)果六、結(jié)論 人工智能搜索可分為盲目搜索和啟發(fā)式搜索。盲目搜索算法有寬度優(yōu)先算法、深度優(yōu)先算法（有界深度優(yōu)先算法），啟發(fā)式搜索算法有A算法、A*算法。本實(shí)驗(yàn)采用的是寬度優(yōu)先（廣度優(yōu)先）算法，這種算法是按預(yù)定的控制策略進(jìn)行，在搜素的過(guò)程中所獲得的信息不用來(lái)改進(jìn)控制策略。由于搜索總是按預(yù)定的路線進(jìn)行，沒(méi)有考慮問(wèn)題本身的特性，這種缺乏問(wèn)題求解的針對(duì)性，需要進(jìn)行全方位的搜索，而沒(méi)有選擇最優(yōu)的搜索路徑。所以圖4寬度優(yōu)先搜索樹及程序運(yùn)行結(jié)果圖5得到的節(jié)點(diǎn)（狀態(tài)圖）很多,而解路徑為1-3-8-16-26，其它節(jié)點(diǎn)是沒(méi)有用的節(jié)點(diǎn)，搜索效率很低。通過(guò)這次實(shí)驗(yàn)更加熟悉狀態(tài)空間的寬度優(yōu)先搜索、深度優(yōu)先搜索

10、和啟發(fā)式搜索算法及計(jì)算機(jī)語(yǔ)言對(duì)常用數(shù)據(jù)結(jié)構(gòu)如鏈表、隊(duì)列等的描述應(yīng)用。學(xué)到了不少知識(shí)。七、源程序及注釋 #include <iostream>#include <ctime>#include <vector>using namespace std;const int ROW = 3;/行數(shù)const int COL = 3;/列數(shù)const int MAXDISTANCE = 10000;/最多可以有的表的數(shù)目const int MAXNUM = 10000;typedef struct _Node int digitROWCOL; int dist; / d

11、istance between one state and the destination一個(gè)表和目的表的距離 int dep; / the depth of node深度 / So the comment function = dist + dep.估價(jià)函數(shù)值 int index; / point to the location of parent父節(jié)點(diǎn)的位置 Node;Node src, dest;/ 父節(jié)表 目的表vector<Node> node_v; / store the nodes存儲(chǔ)節(jié)點(diǎn)bool isEmptyOfOPEN() /open表是否為空 for (int

12、 i = 0; i < node_v.size(); i+) if (node_vi.dist != MAXNUM) return false; return true;bool isEqual(int index, int digitCOL) /判斷這個(gè)最優(yōu)的節(jié)點(diǎn)是否和目的節(jié)點(diǎn)一樣 for (int i = 0; i < ROW; i+) for (int j = 0; j < COL; j+) if (node_vindex.digitij != digitij) return false; return true;ostream& operator<<

13、;(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<Node>& rstep_v)/輸出每一個(gè)遍歷的節(jié)點(diǎn) 深度遍歷 rstep_v.push_back(node_vindex); index = node_vindex

14、.index; while (index != 0) rstep_v.push_back(node_vindex); index = node_vindex.index; for (int i = rstep_v.size() - 1; i >= 0; i-)/輸出每一步的探索過(guò)程 cout << "Step " << rstep_v.size() - i << endl << rstep_vi << endl;void Swap(int& a, int& b) int t; t = a; a

15、 = 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é)點(diǎn)的位置 即最優(yōu)節(jié)點(diǎn) int dist = MAXNUM; int loc; / the location of minimize node for (int i = 0; i < node_v.size(); i+) if (node_vi.d

16、ist = 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_v.size(); i+) if (isEqual(i, node.digit) return false; return true;int Distance(Node& node, int digitCOL) i

17、nt 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 - k) + abs(j - l); flag = true; break; else flag = false; if (flag) break; return distance;

18、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 (node_vindex.digitij = 0) x =i; y = j; flag = true; break; else flag = false; if(flag) break; Node node_up; Assign(node_up, inde

19、x);/向上擴(kuò)展的節(jié)點(diǎn) 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.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

20、_down, index);/向下擴(kuò)展的節(jié)點(diǎn) int dist_down = MAXDISTANCE; if (x < 2) Swap(node_down.digitxy, node_down.digitx + 1y); if (isExpandable(node_down) dist_down = Distance(node_down, dest.digit); node_down.index = index; node_down.dist = dist_down; node_down.dep = node_vindex.dep + 1; node_v.push_back(node_d

21、own); Node node_left; Assign(node_left, index);/向左擴(kuò)展的節(jié)點(diǎn) int dist_left = MAXDISTANCE; if (y > 0) Swap(node_left.digitxy, node_left.digitxy - 1); if (isExpandable(node_left) dist_left = Distance(node_left, dest.digit); node_left.index = index; node_left.dist = dist_left; node_left.dep = node_vindex

22、.dep + 1; node_v.push_back(node_left); Node node_right; Assign(node_right, index);/向右擴(kuò)展的節(jié)點(diǎn) 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.di

23、st = 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;/輸入目的表 for (int m = 0; m < ROW;