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

1、 实 验 报 告一、实验问题八数码问题求解二、实验软件 VC6.0 编程语言或其它编程语言 三、实验目的 1. 熟悉人工智能系统中的问题求解过程； 2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用； 3. 熟悉对八数码问题的建模、求解及编程语言的应用。 四、实验数据及步骤 （一、） 实验内容 八数码问题：在3×3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。 2 8 3 1 2 3 1 4 8 4 7 6 5 7 6 5 (a) 初始状态 (b) 目标状态 图

2、 1 八数码问题示意图 （二、）基本数据结构分析和实现1.结点状态 我采用了struct Node数据类型typedef struct _Node int 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.发生器函数

3、 定义的发生器函数由以下的四种操作组成： (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)将当前状

4、态的空格右移Node node_right; Assign(node_right, index);/向右扩展的节点 int dist_right = MAXDISTANCE;通过定义结点状态和发生器函数，就解决了8数码问题的隐式图的生成问题。接下来就是搜索了。3.图的搜索策略经过分析，8数码问题中可采用的搜速策略共有：1.广度优先搜索、2.深度优先搜索、2.有界深度优先搜索、4.最好优先搜索、5.局部择优搜索，一共五种。其中，广度优先搜索法是可采纳的，有界深度优先搜索法是不完备的，最好优先和局部择优搜索法是启发式搜索法。 实验时,采用了广度(宽度)优先搜索来实现。（三、）广度(宽度)优先搜索原

5、理 1. 状态空间盲目搜索宽度优先搜索 其基本思想是，从初始节点开始，向下逐层对节点进形依次扩展，并考察它是否为目标节点，再对下层节点进行扩展（或搜索）之前，必须完成对当层的所有节点的扩展。再搜索过程中，未扩展节点表OPEN中的节点排序准则是：先进入的节点排在前面，后进入的节点排在后面。其搜索过程如图（1）所示。 SABCFDEGHIJ 图2、宽度优先搜索示意图 2. 宽度优先算法如下： 步1 把初始结点S0放入OPEN表中 步2 若OPEN表为空，则搜索失败，问题无解 步3 取OPEN表中最前面的结点N放在CLOSE表中，并冠以顺序编号n 步4 若目标结点Sg=N，则搜索成功，问题有解 步5

6、 若N无子结点，则转步2 步6 扩展结点N，将其所有子结点配上指向N的放回指针，依次放入OPEN表的尾部，转步2 3.宽度优先算法流程图 起始 把S放入OPEN表Fangru 否是OPEN是否为空表?失败把第一个节点n,从OPEN表移出,并把它放入CLOSED表扩展n,把它的后继节点放入OPEN表的末端,提供回到n的指针是否有任何后继节点为目标节点?否是成功 图3、宽度优先算法流程图 48数码难题用宽度优先搜索所生成的搜索树如图4。搜索树上的所有节点都标记它们所对应的状态描述，每个节点旁边的数字表示节点扩展的顺序（按顺时针方向移动空格）。图中有26个节点，也就是源程序运行结果。2 8

7、 31 0 47 6 5 1 So2 8 31 4 07 6 52 0 31 8 47 6 52 8 30 1 47 6 52 8 31 6 47 0 5 2 3 4 5 6 7 8 9 10 11 12 130 8 32 1 47 6 50 2 31 8 47 6 52 3 01 8 47 6 52 8 31 4 57 6 02 8 01 4 37 6 52 8 31 6 47 5 02 8 31 6 40 6 52 8 37 1 40 6 5 14 15 16 17 18 19 20 21 1 2 30 8 47 6 52 0 32 1 47 6 52 8 37 1 46 0 52 3 4

8、1 8 07 6 52 8 31 6 07 5 42 8 30 6 41 7 52 8 31 4 57 0 62 0 81 4 37 5 6 22 23 24 25 261 2 38 0 47 6 52 8 37 1 46 5 02 8 37 0 46 1 58 3 02 1 47 6 58 8 32 0 47 6 5图4.八数码题宽度优先搜索树五、实验结果及分析 上机试验时,，经多次程序调试，最后得一下结果。此结果所得节点（状态图）很多 ，可知宽度优先搜索的盲目性很大，当目标节点距离初始节点较远时，就会产生大量的无用节点，搜索效率低。但是，只要问题有解，用宽度优先搜索总可以找到它的解。 图5

9、.程序运行结果六、结论 人工智能搜索可分为盲目搜索和启发式搜索。盲目搜索算法有宽度优先算法、深度优先算法（有界深度优先算法），启发式搜索算法有A算法、A*算法。本实验采用的是宽度优先（广度优先）算法，这种算法是按预定的控制策略进行，在搜素的过程中所获得的信息不用来改进控制策略。由于搜索总是按预定的路线进行，没有考虑问题本身的特性，这种缺乏问题求解的针对性，需要进行全方位的搜索，而没有选择最优的搜索路径。所以图4宽度优先搜索树及程序运行结果图5得到的节点（状态图）很多,而解路径为1-3-8-16-26，其它节点是没有用的节点，搜索效率很低。通过这次实验更加熟悉状态空间的宽度优先搜索、深度优先搜索

10、和启发式搜索算法及计算机语言对常用数据结构如链表、队列等的描述应用。学到了不少知识。七、源程序及注释 #include <iostream>#include <ctime>#include <vector>using namespace std;const int ROW = 3;/行数const int COL = 3;/列数const int MAXDISTANCE = 10000;/最多可以有的表的数目const int MAXNUM = 10000;typedef struct _Node int digitROWCOL; int dist; / d

11、istance 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> node_v; / store the nodes存储节点bool isEmptyOfOPEN() /open表是否为空 for (int

12、 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<<

13、;(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<Node>& rstep_v)/输出每一个遍历的节点 深度遍历 rstep_v.push_back(node_vindex); index = node_vindex

14、.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

15、 = 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 node for (int i = 0; i < node_v.size(); i+) if (node_vi.d

16、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 < node_v.size(); i+) if (isEqual(i, node.digit) return false; return true;int Distance(Node& node, int digitCOL) i

17、nt 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;

18、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 < 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, inde

19、x);/向上扩展的节点 int dist_up = MAXDISTANCE; if (x > 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

20、_down, index);/向下扩展的节点 int dist_down = MAXDISTANCE; if (x < 2) Swap(node_down.digitxy, node_down.digitx + 1y); if (isExpandable(node_down) dist_down = Distance(node_down, dest.digit); node_down.index = index; node_down.dist = dist_down; node_down.dep = node_vindex.dep + 1; node_v.push_back(node_d

21、own); Node node_left; Assign(node_left, index);/向左扩展的节点 int dist_left = MAXDISTANCE; if (y > 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

22、.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.di

23、st = 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 < COL; j+) cin >> number; src.digitij = number; src.index = 0; src.dep = 1; cout << "Input destination:" << endl;/输入目的表 for (int m = 0; m < ROW;