人工智能_八数码实验报告

第一章：P23 页脚内容1 西安郵電大学 人工智能实验 报 告 书（三）

学院：自动化学院 专业：智能科学与技术 班级：智能1403 姓名：刘忠强 时间：2016-3-29 第一章：P23

页脚内容2 一、实验目的 1. 熟悉人工智能系统中的问题求解过程； 2. 熟悉状态空间的盲目搜索策略； 3.掌握盲目收索算法，重点是宽度优先收索和深度优先收索。 二、实验算法 广度优先收索是一种先生成的节点先扩展的策略。它的过程是：从初始节点开始逐层向下扩展，再第n层节点还没有完全搜索之前，不进如第n+1层节点。Open表中的节点总是按进入的先后排序，先进入的节点排在前面，够进入的排在后面。

三、程序框图 第一章：P23

页脚内容3 四、实验结果及分析 初始状态： 目标状态： 2 8 3 2 1 6 1 6 4 4 0 8 7 0 5 7 5 3 第一章：P23 页脚内容4 五、源程序及注释 #include #include #include 第一章：P23 页脚内容5 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 _Node{ int digit[ROW][COL]; int dist; // 距离 int dep; // 深度 第一章：P23 页脚内容6

int index; // 索引值

} Node;

Node src, dest; vector node_v; // 储存节点 bool isEmptyOfOPEN() { //判断Open表是否空 for (int i = 0; i < node_v.size(); i++) { if (node_v[i].dist != MAXNUM) return false; } return true; }

bool isEqual(int index, int digit[][COL]) { //判断节点是否与索引值指向的节点相同 for (int i = 0; i < ROW; i++) 第一章：P23 页脚内容7 for (int j = 0; j < COL; j++) { if (node_v[index].digit[i][j] != digit[i][j]) 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.digit[i][j] << ' '; os << endl; } return os; }

void PrintSteps(int index, vector& rstep_v) { //输出步骤 rstep_v.push_back(node_v[index]); 第一章：P23 页脚内容8 index = node_v[index].index; while (index != 0) { rstep_v.push_back(node_v[index]); index = node_v[index].index; }

for (int i = rstep_v.size() - 1; i >= 0; i--) cout << "Step " << rstep_v.size() - i << endl << rstep_v[i] << endl; }

void Swap(int& a, int& b) { //交换 int t; t = a; a = b; b = t; } 第一章：P23 页脚内容9 void Assign(Node& node, int index) { //获取节点 for (int i = 0; i < ROW; i++) for (int j = 0; j < COL; j++) node.digit[i][j] = node_v[index].digit[i][j]; }

int GetMinNode() { //获取启发值最小的节点 int dist = MAXNUM; int loc; // the location of minimize node for (int i = 0; i < node_v.size(); i++) { if (node_v[i].dist == MAXNUM) continue; else if ((node_v[i].dist + node_v[i].dep) < dist) { loc = i; dist = node_v[i].dist + node_v[i].dep; } } 第一章：P23 页脚内容10 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 digit[][COL]) { //计算距离 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++) { 第一章：P23 页脚内容11 for (int l = 0; l < COL; l++) { if (node.digit[i][j] == digit[k][l]) { 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); 第一章：P23 页脚内容12 }

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_v[index].digit[i][j] == 0) { x =i; y = j; flag = true; break; } else flag = false; } if(flag) break; } 第一章：P23 页脚内容13 Node node_up; //上移操作 Assign(node_up, index); int dist_up = MAXDISTANCE; if (x > 0) { Swap(node_up.digit[x][y], node_up.digit[x - 1][y]); if (isExpandable(node_up)) { dist_up = Distance(node_up, dest.digit); node_up.index = index; node_up.dist = dist_up; node_up.dep = node_v[index].dep + 1; node_v.push_back(node_up); } }

Node node_down; //下移操作 Assign(node_down, index); int dist_down = MAXDISTANCE; 第一章：P23 页脚内容14 if (x < 2) { Swap(node_down.digit[x][y], node_down.digit[x + 1][y]); if (isExpandable(node_down)) { dist_down = Distance(node_down, dest.digit); node_down.index = index; node_down.dist = dist_down; node_down.dep = node_v[index].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.digit[x][y], node_left.digit[x][y - 1]); if (isExpandable(node_left)) {