八数码问题求解实验报告讲解

实验报告一、实验问题 八数码问题求解二、实验软件VC6.0 编程语言或其它编程语言三、实验目的1. 熟悉人工智能系统中的问题求解过程；2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用；3. 熟悉对八数码问题的建模、求解及编程语言的应用。四、实验数据及步骤 （一、） 实验内容八数码问题：在3X 3的方格棋盘上，摆放着1到8这八个数码，有1个方 格是空的，其初始状态如图 1 所示，要求对空格执行空格左移、空格右移、空格 上移和空格下移这四个操作使得棋盘从初始状态到目标状态。28312314847657 65(a)初始状态图1（b） 目标状态八数码问题示意图（二、）基本数据结构分析和实现1. 结点状态我采用了 struct Node 数据类型 typedef struct _Nodeint digitROWCOL;int dist; / distance between one state and the destination一个表和目的表的距离int dep; / the depth of node深度/ So the comment function = dist + dep.估价函数值int index; / point to the location of parent父节点的位置 Node; 2. 发生器函数 定义的发生器函数由以下的四种操作组成：(1) 将当前状态的空格上移Node node_up;Assign(node_up, index);/ 向上扩展的节点int dist_up = MAXDISTANCE;(2) 将当前状态的空格下移Node node_down;Assign(node_down, index);/ 向下扩展的节点int dist_down = MAXDISTANCE;(3) 将当前状态的空格左移Node node_left;Assign(node_left, index);/ 向左扩展的节点int dist_left = MAXDISTANCE;(4) 将当前状态的空格右移Node node_right;Assign(node_right, index);/ 向右扩展的节点int dist_right = MAXDISTANCE;通过定义结点状态和发生器函数， 就解决了 8 数码问题的隐式图的生成问题。 接 下来就是搜索了。3. 图的搜索策略经过分析， 8数码问题中可采用的搜速策略共有： 1. 广度优先搜索、 2. 深度优先 搜索、2.有界深度优先搜索、 4.最好优先搜索、 5.局部择优搜索，一共五种。其 中，广度优先搜索法是可采纳的， 有界深度优先搜索法是不完备的， 最好优先和 局部择优搜索法是启发式搜索法。实验时,采用了广度 (宽度)优先搜索来实现。(三、)广度 (宽度)优先搜索原理1. 状态空间盲目搜索宽度优先搜索 其基本思想是，从初始节点开始，向下逐层对节点进形依次扩展，并考察 它是否为目标节点，再对下层节点进行扩展(或搜索)之前，必须完成对当层的 所有节点的扩展。再搜索过程中，未扩展节点表 OPEN 中的节点排序准则是： ) 所示。1 先进入的节点排在前面，后进入的节点排在后面。其搜索过程如图(ABCFD EGIHJ2、宽度优先搜索示意图图2.宽度优先算法如下：OPEN表中S0放入OPEN步1把初始结点 表为空，则搜索失败，问题无解若 步2表中，并冠以顺序编CLOSE放在 3取OPENS中最前面的结点步n号Sg=N，贝U搜索成功，问题有解步4若目标结点2N无子结点，则转步步5若的放回指针，依次放N扩展结点N,将其所有子结点配上指向步62表的尾部，转步入OPEN 3.宽度优先算法流程图.起始把S放入OPEN表否是是否OPEN失败？ 为空表表OPE把第一个节 n从并把它放 CLOSE岀OPEN把它的后继节点放扩 n,的指提供回表的末端否成？节点为目标节点、宽度优先算法流程图图3 搜索树上的所有。数码难题用宽度优先搜索所生成的搜索树如图 4 4. 8 节点都标记它们所对应的状态描述，每个节点旁边的数字表示节点扩展的顺序 个节点，也就是源程序运行结果。图中有26 （按顺时针方向移动空格）1SO 104231 47 6 5 7 6 5 7 6 5 7 0 51011121367890 8 3 2 8 3 0 2 3 2 3 0 2 8 0 2 8 3 2 8 3 2 8 32 1 4 7 1 4 1 8 4 1 8 4 1 4 3 1 4 5 1 6 4 1 6 47 6 5 0 6 5 7 6 5 7 6 5 7 6 5 7 6 0 0 6 5 7 5 014151617181920 212 0 3 2 8 3 1 2 3 2 3 4 2 0 8 2 8 3 2 8 3 2 8 32 1 4 7 1 4 0 8 4 1 8 0 1 4 3 1 4 5 0 6 4 1 6 07 5 41 7 57 0 623242522 268 3 08 8 32 8 32 8 31 2 32 1 4 2 0 4 7 0 4 7 1 4 8 0 47 6 5 7 6 5 6 1 5 6 5 0 7 6 5图4.八数码题宽度优先搜索树五、实验结果及分析上机试验时，经多次程序调试，最后得一下结果。此结果所得节点（状态 图）很多，可知宽度优先搜索的盲目性很大，当目标节点距离初始节点较远时, 就会产生大量的无用节点，搜索效率低。但是，只要问题有解，用宽度优先搜索 总可以找到它的解。图 5. 程序运行结果六、结论 人工智能搜索可分为盲目搜索和启发式搜索。 盲目搜索算法有宽度优先算法、 深 度优先算法(有界深度优先算法)，启发式搜索算法有A算法、A*算法。本实验 采用的是宽度优先(广度优先)算法，这种算法是按预定的控制策略进行，在搜 素的过程中所获得的信息不用来改进控制策略。 由于搜索总是按预定的路线进行， 没有考虑问题本身的特性， 这种缺乏问题求解的针对性， 需要进行全方位的搜索， 而没有选择最优的搜索路径。 所以图 4 宽度优先搜索树及程序运行结果图 5 得到 的节点(状态图)很多 ,而解路径为 1-3-8-16-26，其它节点是没有用的节点，搜 索效率很低。 通过这次实验更加熟悉状态空间的宽度优先搜索、 深度优先搜索和 启发式搜索算法及计算机语言对常用数据结构如链表、 队列等的描述应用。 学到 了不少知识。七、源程序及注释#include #include #include using namespace std;const int ROW = 3;/ 行数const int COL = 3;/ 列数const int MAXDISTANCE = 10000;/ 最多可以有的表的数目const int MAXNUM = 10000;typedef struct _Nodeint digitROWCOL;int dist; / distance between one state and the destination 一个表和目的表的距离int dep; / the depth of node 深度/ So the comment function = dist + dep. 估价函数值int index; / point to the location of parent 父节点的位置 Node;Node src, dest;/ 父节表 目的表vector node_v; / store the nodes 存储节点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)- 1y);Swap(node_up.digitxy, node_up.digitx 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 Input source: endl;for (int i = 0; i ROW; i+)/ 输入初始的表 for (int j = 0; j number; src.digitij = number;src.index = 0; src.dep = 1;cout Input destination: endl;/ 输入目的表 for (int m = 0; m ROW; m+)for (int n = 0; n number; dest.digitmn = number;node_v.push_back(src);/ 在容器的尾部加一个数据cout Search. endl; clock_t start = clock(); while (1)if (isEmptyOfOPEN()cout Cannt solve this statement! endl;return -1;elseint loc; / the location of the minimize node 最优节点的位置 loc = GetMinNode();if(isEqual(loc, dest.digit) vector rstep_v; cout Source: endl; cout src endl; PrintSteps(loc, rstep_v); cout Successful! endl; cout Using (clock() - start) / CLOCKS_PER_SEC seconds. endl;break;elseProcessNode(loc);return 0;： )对行和列数进行修改 (十五数码问题的截图.exeInput source: 012345678 Input destination : 123456780 Search.Source:0 123 4 56 ? 8Step 214 23 0 56 ? 8Step 31 4 2 3 57 8 *D:VC6.0S(www.greenxfcom)MyProjertszb20110430DebugV码ce，)卜Step 4 14 26 3 5 0 7 8Step 5 14 26 3 5 ? 0 8SLcp G 426 3 57 8 UStep 714 26 3 07 8 5Step 814 2 6 0 3 ? 8 5 ,D：VC6.03feS(ww.greenxfxom)MyProjectszb20110430Debug1JJ exeStep 2012 34 0 57 8 6Step 211 2 34 5 07 8 6Gtcp 2212 34 5 67 8 0Successful!Using 0 seconds.Press any key to continue