八数码问题求解--实验报告_第1页
八数码问题求解--实验报告_第2页
八数码问题求解--实验报告_第3页
八数码问题求解--实验报告_第4页
八数码问题求解--实验报告_第5页
已阅读5页,还剩11页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

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;

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论