人工智能_八數碼實驗報告重點講義

1、西安郵電大學人工智能實驗 報 告 書（三） 學院：自動化學院專業(yè)：智能科學與技術 班級：智能1403 姓名：劉忠強 時間：2016-3-29一、實驗目的1. 熟悉人工智能系統(tǒng)中的問題求解過程；2. 熟悉狀態(tài)空間的盲目搜索策略；3.掌握盲目收索算法，重點是寬度優(yōu)先收索和深度優(yōu)先收索。二、實驗算法 廣度優(yōu)先收索是一種先生成的節(jié)點先擴展的策略。它的過程是：從初始節(jié)點開始逐層向下擴展，再第n層節(jié)點還沒有完全搜索之前，不進如第n+1層節(jié)點。Open表中的節(jié)點總是按進入的先后排序，先進入的節(jié)點排在前面，夠進入的排在后面。三、程序框圖四、實驗結果及分析初始狀態(tài)： 目標狀態(tài)： 2 8 3 2 1 6 1 6

2、4 4 0 8 7 0 5 7 5 3五、源程序及注釋#include <iostream>#include <ctime>#include <vector>using namespace std;const int ROW = 3;const int COL = 3;const int MAXDISTANCE = 10000;const int MAXNUM = 10000;int abs(int a)if (a>0) return a;else return -a;typedef struct _Nodeint digitROWCOL;int di

3、st; / 距離 int dep; / 深度 int index; / 索引值 Node;Node src, dest;vector<Node> node_v; / 儲存節(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) /判斷節(jié)點是否與索引值指向的節(jié)點相同 for (int i = 0; i <

4、; ROW; i+) 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;retur

5、n os;void PrintSteps(int index, vector<Node>& rstep_v) /輸出步驟 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 " << rstep_

6、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) /獲取節(jié)點 for (int i = 0; i < ROW; i+) for (int j = 0; j < COL; j+) node.digitij = node_vindex.digitij;int GetMinNode() /獲取啟發(fā)值最小的節(jié)點 int di

7、st = 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 <

8、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.digitij =

9、 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) /展開節(jié)點 int x, y;bool flag;for (int i = 0; i < ROW; i+) for (int j = 0; j < COL; j+) if

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

11、x = 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 < 2) Swap(node_down.digitxy, node_down.digitx + 1y); if (isExpandable(node_down) dist_down = Distance(node_down, dest.di

12、git); 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);int dist_left = MAXDISTANCE;if (y > 0) Swap(node_left.digitxy, node_left.digitxy - 1); if (isExpandable(node_left) dist_left =

13、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 (isE

14、xpandable(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() int number;cout << "輸入初始狀態(tài):" << endl;for (int i

15、= 0; i < ROW; i+) for (int j = 0; j < COL; j+) cin >> number; src.digitij = number; src.index = 0;src.dep = 1;cout << "輸入目標狀態(tài)" << endl;for (int m = 0; m < ROW; m+) for (int n = 0; n < COL; n+) cin >> number; dest.digitmn = number; node_v.push_back(src);w

16、hile (1) if (isEmptyOfOPEN() cout << "找不到解!" << endl; return -1; else int loc; / the location of the minimize node loc = GetMinNode(); if(isEqual(loc, dest.digit) vector<Node> rstep_v; cout << "初始狀態(tài)：" << endl; cout << src << endl; PrintSteps(loc, rstep_v); cout << "成功!&qu