2022年八数码问题求解--实验报告.pdf

v1.0 可编辑可修改1 实验报告一、实验问题八数码问题求解二、实验软件编程语言或其它编程语言三、实验目的 1. 熟悉人工智能系统中的问题求解过程； 2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用； 3. 熟悉对八数码问题的建模、求解及编程语言的应用。四、实验数据及步骤（一、 ） 实验内容八数码问题： 在 33 的方格棋盘上， 摆放着 1 到 8 这八个数码， 有 1 个方格是空的，其初始状态如图1 所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。 2 8 3 1 2 3 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 1 页，共 15 页 - - - - - - - - - - v1.0 可编辑可修改2 1 4 8 4 7 6 5 7 6 5 (a) 初始状态 (b) 目标状态图 1 八数码问题示意图（二、 ）基本数据结构分析和实现1. 结点状态我采用了 struct Node数据类型typedef struct _Node int digitROWCOL; int dist; 价函数值 int index; 生器函数定义的发生器函数由以下的四种操作组成： (1) 将当前状态的空格上移Node node_up; Assign(node_up, index);的搜索策略经过分析， 8 数码问题中可采用的搜速策略共有：1. 广度优先搜索、 2. 深度优先搜索、2. 有界深度优先搜索、 4. 最好优先搜索、 5. 局部择优搜索， 一共五种。其中，广度优先搜索法是可采纳的，有界深度优先搜索法是不完备的，最好优先和局部择优搜索法是启发式搜索法。实验时 , 采用了广度 (宽度) 优先搜索来实现。（三、 ）广度 (宽度)优先搜索原理 1. 状态空间盲目搜索宽度优先搜索其基本思想是，从初始节点开始，向下逐层对节点进形依次扩展，并考察它是否为目标节点，再对下层节点进行扩展（或搜索）之前，必须完成对当层的所有节点的扩展。再搜索过程中，未扩展节点表OPEN 中的节点排序准则是：先精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 2 页，共 15 页 - - - - - - - - - - v1.0 可编辑可修改3 进入的节点排在前面，后进入的节点排在后面。其搜索过程如图（1）所示。图 2、宽度优先搜索示意图 2. 宽度优先算法如下：步 1 把初始结点 S0放入 OPEN 表中步 2 若 OPEN 表为空，则搜索失败，问题无解步 3 取 OPEN 表中最前面的结点N放在 CLOSE 表中，并冠以顺序编号 n 步 4 若目标结点 Sg=N ，则搜索成功，问题有解步 5 若 N无子结点，则转步2 步 6 扩展结点 N，将其所有子结点配上指向N的放回指针，依次放入 OPEN 表的尾部，转步 2 3. 宽度优先算法流程图CSBEDAIFHGJ起始精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 3 页，共 15 页 - - - - - - - - - - v1.0 可编辑可修改4 图 3、宽度优先算法流程图 48 数码难题用宽度优先搜索所生成的搜索树如图4。搜索树上的所有节点都标记它们所对应的状态描述，每个节点旁边的数字表示节点扩展的顺序（按顺时针方向移动空格） 。图中有 26 个节点，也就是源程序运行结果。把 S放入 OPEN 表OPEN 是否为把第一个节点n, 从 OPEN表移扩展 n, 把它的后继节点放入OPEN失败成功是 否 有 任 何 后 继节点为目标节点是否是否精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 4 页，共 15 页 - - - - - - - - - - v1.0 可编辑可修改5 1 So 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26图 4. 八数码题宽度优先搜索树五、实验结果及分析上机试验时 , ，经多次程序调试，最后得一下结果。此结果所得节点（状态图）很多 ，可知宽度优先搜索的盲目性很大，当目标节点距离初始节点较远时，就会产生大量的无用节点，搜索效率低。但是，只要问题有解，用宽度优先搜索总可以找到它的解。2 8 31 0 42 0 32 1 42 8 31 6 42 8 31 6 42 8 31 6 40 8 32 1 42 0 31 8 42 8 30 1 42 3 41 8 02 8 31 4 02 8 37 1 42 3 01 8 42 8 31 4 51 2 30 8 40 2 31 8 42 8 37 1 42 8 01 4 32 0 81 4 32 8 30 6 42 8 31 4 58 3 02 1 48 8 32 0 42 8 31 6 01 2 38 0 42 8 37 1 42 8 37 0 4精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 5 页，共 15 页 - - - - - - - - - - v1.0 可编辑可修改6 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 6 页，共 15 页 - - - - - - - - - - v1.0 可编辑可修改7 图 5. 程序运行结果六、结论人工智能搜索可分为盲目搜索和启发式搜索。盲目搜索算法有宽度优先算法、深度优先算法（有界深度优先算法） ，启发式搜索算法有A算法、 A*算法。本实验采用的是宽度优先 （广度优先）算法，这种算法是按预定的控制策略进行，在搜素的过程中所获得的信息不用来改进控制策略。由于搜索总是按预定的路线进行，没有考虑问题本身的特性， 这种缺乏问题求解的针对性，需要进行全方位的搜索，而没有选择最优的搜索路径。 所以图 4 宽度优先搜索树及程序运行结果图 5 得到的节点（状态图）很多, 而解路径为，其它节点是没有用的节点，搜索效率很低。通过这次实验更加熟悉状态空间的宽度优先搜索、深度优先搜索和启发式搜索算法及计算机语言对常用数据结构如链表、队列等的描述应用。 学到了不少知识。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 7 页，共 15 页 - - - - - - - - - - v1.0 可编辑可修改8 七、源程序及注释#include #include #include using namespace std;const int ROW = 3;价函数值 int index; ist != MAXNUM) return false; return true;bool isEqual(int index, int digitCOL) igitij != 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 ij ; os endl; return os;精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 8 页，共 15 页 - - - - - - - - - - v1.0 可编辑可修改9 void PrintSteps(int index, vector& rstep_v)ndex; while (index != 0) (node_vindex); index = node_vindex.index; for (int i = () - 1; i = 0; i-)igitij;int GetMinNode() ist = 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 (); i+) if (isEqual(i, ) return false; return true;精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 9 页，共 15 页 - - - - - - - - - - v1.0 可编辑可修改10 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 ij = 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);精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 10 页，共 15 页 - - - - - - - - - - v1.0 可编辑可修改11 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_vindex.digitij = 0) x =i; y = j; flag = true; break; else flag = false; if(flag) break; Node node_up; Assign(node_up, index);ep + 1; (node_up); Node node_down; Assign(node_down, index);ep + 1;精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 11 页，共 15 页 - - - - - - - - - - v1.0 可编辑可修改12 (node_down); Node node_left; Assign(node_left, index);ep + 1; (node_left); Node node_right; Assign(node_right, index);ep + 1; (node_right); node_vindex.dist = MAXNUM;int main() . endl; clock_t start = clock(); while (1) if (isEmptyOfOPEN() cout Cannt solve this statement! endl; return -1; 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 12 页，共 15 页 - - - - - - - - - - v1.0 可编辑可修改13 else int loc; endl; break; else ProcessNode(loc); return 0;十五数码问题的截图 (对行和列数进行修改 )：精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 13 页，共 15 页 - - - - - - - - - - v1.0 可编辑可修改14 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 14 页，共 15 页 - - - - - - - - - - v1.0 可编辑可修改15 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 15 页，共 15 页 - - - - - - - - - -