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

.西安郵電大学人工智能实验 报 告 书（三） 学院：自动化学院专业：智能科学与技术 班级：智能1403 姓名：刘忠强 时间：2016-3-29一、实验目的1. 熟悉人工智能系统中的问题求解过程；2. 熟悉状态空间的盲目搜索策略；3.掌握盲目收索算法，重点是宽度优先收索和深度优先收索。二、实验算法 广度优先收索是一种先生成的节点先扩展的策略。它的过程是：从初始节点开始逐层向下扩展，再第n层节点还没有完全搜索之前，不进如第n+1层节点。Open表中的节点总是按进入的先后排序，先进入的节点排在前面，够进入的排在后面。三、程序框图四、实验结果及分析初始状态： 目标状态： 2 8 3 2 1 6 1 6 4 4 0 8 7 0 5 7 5 3五、源程序及注释#include #include #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 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) /判断节点是否与索引值指向的节点相同 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(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.index;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() /获取启发值最小的节点 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_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 - 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 (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_down, index);int dist_down = MAXDISTANCE;if (x 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.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_vindex.dep + 1; node_v.push_back(node_right); node_vindex.dist = MAXNUM;int main() int number;cout 输入初始状态: endl;for (int i = 0; i ROW; i+) for (int j = 0; j number; src.digitij = number; src.index = 0;src.dep = 1;cout 输入目标状态 endl;for (int m = 0; m ROW; m+) for (int n = 0; n number; dest.digitmn = number; node_v.push_back(src);while (1) if (isEmptyOfOPEN() cout 找不到解! endl; return -1; else int loc; / the location of the minimize node loc = GetMinNode(); if(isEqual(loc, dest.digit) vector rstep_v; cout 初始状态： endl; cout src endl; PrintSteps(loc, rstep_v); cout 成功! endl; break; else ProcessNode(loc); return 0;