- 1、本文档共12页,可阅读全部内容。
- 2、原创力文档(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
实验一 启发式搜索算法
姓名:尹鹏飞 学号:S201407031 日期:2014/10/22
一、实验目的:
熟练掌握启发式搜索算法及其可采纳性。
二、实验内容:
使用启发式搜索算法求解8数码问题。
编制程序实现求解8数码问题算法,采用估价函数
,
其中:是搜索树中结点的深度;为结点的数据库中错放的棋子个数;为结点的数据库中每个棋子与其目标位置之间的距离总和。
本实验采用+ 作为启发式函数.
三、实验原理:
问题描述:
八数码问题也称为九宫问题。在3×3的棋盘,摆有八个棋子,每个棋子上标有1至8的某一数字,不同棋子上标的数字不相同。棋盘上还有一个空格(以数字0来表示),与空格相邻的棋子可以移到空格中。
要求解决的问题是:给出一个初始状态和一个目标状态,找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。
所谓问题的一个状态就是棋子在棋盘上的一种摆法。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。
原理描述:
2.1 有序搜索算法:
(1)原理:
在搜索过程中,OPEN表中节点按照其估价函数值以递增顺序排列,选择OPEN表中具有最小估价函数值的节点作为下一个待扩展的节点,这种搜索方法称为有序搜索。
在本例中,估价函数中的取错放的棋子个数,为节点n的状态与目标状态之间错放的个数,即函数。
(2)算法描述:
把起始节点S放到OPEN表中,并计算节点S的;
如果OPEN是空表,则失败退出,无解;
从OPEN表中选择一个值最小的节点。如果有几个节点值相同,当其中有一个
为目标节点时,则选择此目标节点;否则就选择其中任一个节点作为节点;
把节点从 OPEN 表中移出,并把它放入 CLOSED 的已扩展节点表中;
如果是个目标节点,则成功退出,求得一个解;
扩展节点,生成其全部后继节点。对于的每一个后继节点:
计算;如果 既不在OPEN表中,又不在CLOCED表中,则用估价函数把
它添入OPEN表中。从加一指向其父节点的指针,以便一旦找到目标节点时记住一个解答路径;如果已在OPEN表或CLOSED表中,则比较刚刚对计算过的和前面计算过的该节点在表中的值。如果新的较小,则
(I)以此新值取代旧值。
(II)从指向,而不是指向他的父节点。
(III)如果节点在CLOSED表中,则把它移回OPEN表中。
转向②,即GOTO②。
算法流程图:
2.2启发式搜索技术
(1)原理
启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估,得到最好的位置,再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径,提高了效率。在启发式搜索中,对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。
(2)估价函数
计算一个节点的估价函数,可以分成两个部分:
已经付出的代价(起始节点到当前节点);
将要付出的代价(当前节点到目标节点)。
节点n的估价函数定义为从初始节点、经过n、到达目标节点的路径的最小代价的估计值,即 = + 。
是从初始节点到达当前节点n的实际代价;
是从节点n到目标节点的最佳路径的估计代价,体现出搜索过程中采用的启发式信息(背景知识),称之为启发函数。
所占的比重越大,越趋向于宽度优先或等代价搜索;反之,的比重越大,表示启发性能就越强。
本实验中我们使用函数,其值是节点n与目标状态节点相比较,每个错位棋牌在假设不受阻拦的情况下,移动到目标状态相应位置所需走步(移动次数)的总和。显然比更接近于,因为不仅考虑了错位因素,还考虑了错位的距离。
算法描述:
参考有序搜索算法描述,基本相同。流程图亦参考有序算法流程图。
实验程序及其说明:
程序开发语言采用C#和面向对象的设计思想,设计的类内容如下:
类视图
SplashForm用来显示启动界面;
MainForm 用来显示数据设置界面;
ShowForm 用来显示结果界面;
Number用来记录每个节点当前的状态和权值;
属性: private int[] num;//保存当前输入的八数码状态
private int w, p;//分别记录当前的八数码搜索深度和不在位棋子数
private Number next;//指向下一个节点
private Number parent;//指向父节点
private int index;//定义当前0所在的位置
方法: //复写父类比较方法
public override bool Equals(Object num)
//两个对象的比较方法
public bool CompareLow(Number num)
NumberUtil类,工具类,对八数码的各种状态进行控制管理
private Queue numQue
您可能关注的文档
- 清华大学物理试题库所有习题.docx
- 清华学堂物业投标书.doc
- 清洗地毯规范及操作.doc
- 庆建国66周年主题征文:忆往昔庆国庆.doc
- 庆运辉腾公司简介.doc
- 庆祝新中国成立70周年系列纪念活动方案 关于举办庆祝建国70周年文艺演出方案 2019年庆祝新中国成立70周年活动方案.doc
- 秋天的雨---导学案.doc
- 求职礼仪论文.doc
- 区段站站场设计.doc
- 区妇联组织机构及主要职责.doc
- 2024届高考专题复习:“五抓一验”攻克5类病句修改+.pptx
- 2024届高考专题复习+:常见标点符号及其作用.pptx
- 2024届高三二轮备考之文言文提分策略+课件.pptx
- 2024届高考写作指导:巧借材料++拟分论点.pptx
- 2024届高考语文作文备考:立足材料,打造分论点+课件.pptx
- 诗歌形象之景物形象-冲刺2024年高考语文古代诗歌鉴赏精品课件(全国通用).pptx
- 诗歌形象之事物形象-冲刺2024年高考语文古代诗歌鉴赏精品课件(全国通用).pptx
- 诗歌形象之意象意境-冲刺2024年高考语文古代诗歌鉴赏精品课件(全国通用).pptx
- 文言文阅读:文言句式(下篇)(课件)-备战2024年高考语文素质教育精讲课堂专题复习(新高考卷区通用).pptx
- 2024届高考小说复习之从文体特征去解答小说特殊叙述手法题+课件.pptx
文档评论(0)