




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、.一、实验内容和要求八数码问题:在33的方格棋盘上,摆放着1到8这八个数码,有1个方格是空的,其初始状态如图1所示,要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。例如:28312316484705765(a) 初始状态 (b) 目标状态图1 八数码问题示意图请任选一种盲目搜索算法(广度优先搜索或深度优先搜索)或任选一种启发式搜索方法(全局择优搜索,加权状态图搜索,A 算法或 A* 算法)编程求解八数码问题(初始状态任选)。选择一个初始状态,画出搜索树,填写相应的OPEN表和CLOSED表,给出解路径,对实验结果进行分析总结,得出结论。二、实验目的1
2、. 熟悉人工智能系统中的问题求解过程;2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用;3. 熟悉对八数码问题的建模、求解及编程语言的应用。三、实验算法A*算法是一种常用的启发式搜索算法。在A*算法中,一个结点位置的好坏用估价函数来对它进行评估。A*算法的估价函数可表示为: f(n) = g(n) + h(n) 这里,f(n)是估价函数,g(n)是起点到终点的最短路径值(也称为最小耗费或最小代价),h(n)是n到目标的最短路经的启发值。由于这个f(n)其实是无法预先知道的,所以实际上使用的是下面的估价函数:f(n) = g(n) + h(n) 其中g(n)是从初始结点到节点n的实际代价,h(
3、n)是从结点n到目标结点的最佳路径的估计代价。在这里主要是h(n)体现了搜索的启发信息,因为g(n)是已知的。用f(n)作为f(n)的近似,也就是用g(n)代替g(n),h(n)代替h(n)。这样必须满足两个条件:(1)g(n)=g(n)(大多数情况下都是满足的,可以不用考虑),且f必须保持单调递增。(2)h必须小于等于实际的从当前节点到达目标节点的最小耗费h(n)=h(n)。第二点特别的重要。可以证明应用这样的估价函数是可以找到最短路径的。3.A*算法的步骤A*算法基本上与广度优先算法相同,但是在扩展出一个结点后,要计算它的估价函数,并根据估价函数对待扩展的结点排序,从而保证每次扩展的结点都
4、是估价函数最小的结点。A*算法的步骤如下:1)建立一个队列,计算初始结点的估价函数f,并将初始结点入队,设置队列头和尾指针。2)取出队列头(队列头指针所指)的结点,如果该结点是目标结点,则输出路径,程序结束。否则对结点进行扩展。 3)检查扩展出的新结点是否与队列中的结点重复,若与不能再扩展的结点重复(位于队列头指针之前),则将它抛弃;若新结点与待扩展的结点重复(位于队列头指针之后),则比较两个结点的估价函数中g的大小,保留较小g值的结点。跳至第五步。4)如果扩展出的新结点与队列中的结点不重复,则按照它的估价函数f大小将它插入队列中的头结点后待扩展结点的适当位置,使它们按从小到大的顺序排列,最后
5、更新队列尾指针。5)如果队列头的结点还可以扩展,直接返回第二步。否则将队列头指针指向下一结点,再返回第二步。四、程序框图五、实验结果及分析输入初始状态:2 8 3目标状态:1 2 31 6 48 0 47 0 57 6 5运行结果屏幕打印OPEN表与CLOSE表:OPENCLOSE1 2 3 4 02 3 4 5 60 12 3 4 6 70 1 52 3 4 6 8 90 1 5 72 3 4 8 9 100 1 5 7 62 3 4 8 11 12 13 0 1 5 7 6 92 3 4 8 12 13 14 150 1 5 7 6 9 113 4 8 12 13 14 15 16 170
6、 1 5 7 6 9 11 24 8 12 13 14 15 16 17 18 190 1 5 7 6 9 11 2 34 8 12 13 14 15 16 17 19 200 1 5 7 6 9 11 2 3 188 12 13 14 15 16 17 19 21 220 1 5 7 6 9 11 2 3 18 412 13 14 15 16 17 19 21 22 230 1 5 7 6 9 11 2 3 18 4 812 13 14 15 16 17 19 21 22 24 250 1 5 7 6 9 11 2 3 18 4 8 2312 13 14 15 16 17 19 21 22
7、24 260 1 5 7 6 9 11 2 3 18 4 8 23 24发现26为目标节点072 8 31 0 47 6 5搜索树:2.112 8 31 6 47 0 5172 0 31 8 47 6 54.112 8 31 4 07 6 53.112 8 30 1 47 6 522.142 8 31 4 57 6 019.122 8 37 1 40 6 521.122 8 31 4 37 6 518.100 8 32 1 47 6 511.142 8 31 6 47 5 010.142 8 31 6 47 0 5692 3 01 8 47 6 5580 2 31 8 47 6 5791 2
8、30 8 47 6 510.112 3 41 8 07 6 520.118 0 32 1 47 6 5注释:每个方格中最上面两个数字分别为编号与启发值,下面九个数字为八数码。较粗的箭头为解路径8.121 2 37 8 40 6 59.101 2 38 0 47 6 511.91 0 38 2 47 6 523.91 2 37 8 46 0 513.131 2 38 4 07 6 512.131 2 38 6 47 0 524.81 2 37 0 46 8 525.121 2 37 8 46 5 014.120 1 38 2 47 6 515.143 1 08 2 47 6 5目标节点六、结论对
9、于八数码问题,BFS算法最慢,A*算法较快。八数码问题的一个状态实际上是09的一个排列,对于任意给定的初始状态和目标,不一定有解,也就是说从初始状态不一定能到达目标状态。因为排列有奇排列和偶排列两类,从奇排列不能转化成偶排列。如果一个数字08的随机排列871526340,用F(X)表示数字X前面比它小的数的个数,全部数字的F(X)之和为Y=(F(X),如果Y为奇数则称原数字的排列是奇排列,如果Y为偶数则称原数字的排列是偶排列。因此,可以在运行程序前检查初始状态和目标状态的排序的奇偶行是否相同,相同则问题可解,应当能搜索到路径。否则无解。七、源程序及注释#include #include #in
10、clude using namespace std;const int ROW = 3;const int COL = 3;const int MAXDISTANCE = 10000;const int MAXNUM = 10000;int abs(int a)if (a0) return a;else return -a;typedef struct _Nodeint digitROWCOL;int dist; / 距离 int dep; / 深度 int index; / 索引值 Node;Node src, dest;vector node_v; / 储存节点 bool isEmptyO
11、fOPEN() /判断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
12、(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;
13、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() /获取启发值最
14、小的节点 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.s
15、ize(); 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)
16、 + 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) Swap(node_up.digitxy, node_up.digitx - 1y); if (isExpan
17、dable(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 (
18、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 =
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 牦牛饲养的生物安全管理体系
- 哲学研究之我见
- 大学人生轨迹
- 音乐的力量与影响
- 多元融合盘活农村闲置资源的背景意义及必要性
- 部门砥砺前行
- 推动教育创新之路
- 脊柱外科护理科普知识
- 2025年修补漆项目规划申请报告
- 2025合作合同范本合资企业合同模板
- 北京大学国际政治经济学教学大纲
- 跨文化沟通的本质-PPT课件
- 合肥市建设工程消防设计审查、消防验收、备案与抽查文书样式
- 《电气工程基础》熊信银-张步涵-华中科技大学习题答案全解
- 财政一体化业务系统
- 北美连续油管技术的新进展及发展趋势李宗田
- 行政单位会计实习报告(共36页)
- 110千伏变电站工程检测试验项目计划
- 《铁路货物运价规则》
- YD_T 3956-2021 电信网和互联网数据安全评估规范_(高清版)
- 小学三年级下册音乐《春天举行音乐会》人音版(简谱2014秋)(18张)(1)ppt课件
评论
0/150
提交评论