《人工智能_八数码实验报告》由会员分享，可在线阅读，更多相关《人工智能_八数码实验报告（11页珍藏版）》请在金锄头文库上搜索。
1、郵電大学人工智能实验报告书（三）学院：自动化学院专业：智能科学与技术班级：智能1403:忠强时间：2016-3-29一、实验目的1. 熟悉人工智能系统中的问题求解过程；2. 熟悉状态空间的盲目搜索策略；3. 掌握盲目收索算法，重点是宽度优先收索和深度优先收索。二、实验算法广度优先收索是一种先生成的节点先扩展的策略。它的过程是：从初始节点 开始逐层向下扩展，再第n层节点还没有完全搜索之前，不进如第 n+1层节点。 Open表中的节点总是按进入的先后排序，先进入的节点排在前面，够进入的排 在后面。三、程序框图四、实验结果及分析目标状态:2 1 6初始状态：2 8 31 6 44 0 87 0 57
2、 5 3五、源程序及注释#in elude #in elude #in elude using n amespace std;const int ROW = 3;const int COL = 3;const int MAXDISTANCE = 10000;const int MAXNUM = 10000;int abs(i nt a)if (a0) retur n a; else return -a;typedef struct _Node int digitROWCOL; int dist; /距离int dep; / 深度intin dex; / 索引值 Node;Node src, d
3、est;vector no de_v; / 储存节点bool isEmptyOfOPEN() / 判断 Open表是否空 for (int i = 0; i no de_v.size(); i+) if (n ode_vi.dist != MAXNUM)return false;return true;判断节点是否与索引bool isEqual(int index, int digitCOL) / 值指向的节点相同for (int i = 0; i ROW; i+)for (i nt j = 0; j COL; j+) if (node_vindex.digitij != digitij) r
4、eturn false;return true;ostream& operator(ostream& os, Node& no de) for (int i = 0; i ROW; i+) for (i nt j = 0; j COL; j+)os no de.digitij ;os en dl;return os;void Prin tSteps(i nt in dex, vector& rstep_v) / rstep_v.push_back (no de_vi ndex);in dex = no de_vi ndex.i ndex;while (in dex != 0) rstep_v.
5、push_back (no de_vi ndex);in dex = no de_vi ndex.i ndex; _输出步骤for (int i = rstep_v.size() - 1; i = 0; i-) cout Step rstep_v.size() - i endl rstep_vi en dl; _void Sw ap(i nt& a, i nt& b) / int t;t = a;a = b;b = t;交换void Assig n(N ode& no de, int in dex) / for (int i = 0; i ROW; i+)for (i nt j = 0; j
6、COL; j+)no de.digitij = no de_vi ndex.digitij; _获取节点int GetMi nNode() /获取启发值最小的节点int dist = MAXNUM;in t loc; / the locati on of mini mize nodefor (int i = 0; i no de_v.size(); i+) if (n ode_vi.dist = MAXNUM)con ti nue;else if (no de_vi.dist + no de_vi.dep) dist) loc = i;dist = no de_vi.dist + no de_
7、vi.dep;return loc; bool isExpa ndable(Node& no de) / for (int i = 0; i no de_v.size(); i+) 判断是否可扩展if (isEqual(i, no de.digit) return false;return true;计算距离int Distance(Node& node, int digitCOL) / int dista nee = 0;bool flag = false;for(int i = 0; i ROW; i+)for (i nt j = 0; j COL; j+)for (int k = 0;
8、k ROW; k+) for (int l = 0; l COL; l+) if (no de.digitij = digitkl) dista nee += abs(i - k) + abs(j - l); flag = true;break;elseflag = false;if (flag)break;retur n dista nee;int Mi nDista nce(i nt a, i nt b) /二者取小return (a b ? a : b);展开节点void ProeessNode(i nt in dex) / int x, y;bool flag;for (int i =
9、 0; i ROW; i+) for (i nt j = 0; j 0) Swap(node_up.digitxy, node_up.digitx - 1y);if (isExpa ndable( no de_up) dist_up = Dista nce( no de_up, dest.digit);no de_up.i ndex = in dex;no de_up.dist = dist_up;no de_up.dep = no de_vi ndex.dep + 1;no de_v.push_back (no de_up); 一一 一Node node_down; / 下移操作Assig
10、n(no de_dow n, in dex);int dist_dow n = MAXDISTANCE;if (x 0) Swap(node_left.digitxy, node_left.digitxy - 1);if (isExpa ndable( no de_left) dist_left = Dista nce( no de_left, dest.digit);no de_left.i ndex = in dex;no de_left.dist = dist_left;no de_left.dep = no de_vi ndex.dep + 1;no de_v.push_back (n
11、o de_left); 一一 一Node node_right; /右移操作Assig n(no de_right, i ndex);int dist_right = MAXDISTANCE;if (y 2) Swap(node_right.digitxy, node_right.digitxy + 1); if (isExpa ndable( no de_right) dist_right = Dista nce( no de_right, dest.digit);no de_right.i ndex = in dex;no de_right.dist = dist_right;no de_right.dep = no de_vi ndex.dep + 1;no de_v.push_back (no de_right); 一一 一n ode_vi ndex.dist = MAXNUM;int mai n() int nu mber;cout 输入初始状态: endl;for (int i = 0; i ROW; i+)for (int j
