1 / 26
文档名称:

实验三:a星算法求解8数码问题实验.doc

格式:doc   大小:159KB   页数:26页
下载后只包含 1 个 DOC 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

实验三:a星算法求解8数码问题实验.doc

上传人:beny00001 2019/5/4 文件大小:159 KB

下载得到文件列表

实验三:a星算法求解8数码问题实验.doc

文档介绍

文档介绍:实验三:A*算法求解8数码问题实验实验目的熟悉和掌握启发式搜索的定义、估价函数和算法过程,并利用A*算法求解N数码难题,理解求解流程和搜索顺序。实验内容八数码问题描述所谓八数码问题起源于一种游戏:在一个3×3的方阵中放入八个数码1、2、3、4、5、6、7、8,其中一个单元格是空的。将任意摆放的数码盘(城初始状态)逐步摆成某个指定的数码盘的排列(目标状态),如图1所示图1八数码问题的某个初始状态和目标状态对于以上问题,我们可以把数码的移动等效城空格的移动。如图1的初始排列,数码7右移等于空格左移。那么对于每一个排列,可能的一次数码移动最多只有4中,即空格左移、空格右移、空格上移、空格下移。最少有两种(当空格位于方阵的4个角时)。所以,问题就转换成如何从初始状态开始,使空格经过最小的移动次数最后排列成目标状态。、:定义一个评价函数f,对当前的搜索状态进行评估,找出一个最有希望的节点来扩展。先定义下面几个函数的含义:f*(n)=g*(n)+h*(n)(1)式中g*(n)表示从初始节点s到当前节点n的最短路径的耗散值;h*(n)表示从当前节点n到目标节点g的最短路径的耗散值,f*(n)表示从初始节点s经过n到目标节点g的最短路径的耗散值。评价函数的形式可定义如(2)式所示:f(n)=g(n)+h(n)(2)其中n是被评价的当前节点。f(n)、g(n)和h(n)分别表示是对f*(n)、g*(n)和h*(n)3个函数值的估计值。利用评价函数f(n)=g(n)+h(n)来排列OPEN表节点顺序的图搜索算法称为算法A。在A算法中,如果对所有的x,h(x)<=h*(x)(3)成立,则称好h(x)为h*(x)的下界,它表示某种偏于保守的估计。采用h*(x)的下界h(x)为启发函数的A算法,称为A*算法。针对八数码问题启发函数设计如下:f(n)=d(n)+p(n)(4)其中A*算法中的g(n)根据具体情况设计为d(n),意为n节点的深度,而h(n)设计为把S放入OPEN表,记f=hOPEN=NULL?是失败扩展BESTNODE,ESSOR选取OPEN表上未设置过的具有最小f值的节点BESTNODE,ESSOR返回BESTNODE的指针计算g(SUC)=g(BES)+k(BES,SUC)SUC∈OPEN开始g(SUC)<g(OLD)SUC=OLD,把它添加到BESTNDOE的后继结点表中重新确定OLD的父辈节点为BESTNODE,并修正父辈节点的g值和f值,记下g(OLD)是成功SUC∈ESSOR放入OPEN表,添进BESTNODE的后裔表计算f值是否是否是否否否图2A*算法流程图p(n),意为放错的数码与正确的位置距离之和。由于实际情况中,一个将牌的移动都是单步进行的,没有交换拍等这样的操作。所以要把所有的不在位的将牌,移动到各自的目标位置上,至少要移动从他们各自的位置到目标位置的距离和这么多次,所以最有路径的耗散值不会比该值小,因此该启发函数h(n)满足A*算法的条件。A*算法流程图,如图2A*,把起始状态添加到开启列表。,重复如下工作:a)寻找开启列表中f值最低的节点,我们称它为BESTNOEb)把它切换到关闭列表中。c)对相邻的4个节点中的每一个*如果它不在开启列表,也不在关闭列表,把它添加到开启列表中。把BESTNODE作为这一节点的父节点。记录这一节点的f和g值*如果它已在开启或关闭列表中,用g值为参考检查新的路径是否更好。更低的g值意味着更好的路径。如果这样,就把这一节点的父节点改为BESTNODE,并且重新计算这一节点的f和g值,如果保持开启列表的f值排序,改变之后需要重新对开启列表排序。d)停止把目标节点添加到关闭列表,这时候路径被找到,或者没有找到路径,开启列表已经空了,这时候路径不存在。,保存路径。从目标节点开始,沿着每一节点的父节点移动直到回到起始节点。这就是求得的路径。5、数据结构采用结构体来保存八数码的状态、f和g的值以及该节点的父节点;structNode{ints[3][3];//保存八数码状态,0代表空格intf,g;//启发函数中的f和g值structNode*next;structNode*previous;//保存其父节点};6、实验结果,如图3所示图3A*算法求解八数码问题实验结果7、源代码//-----------------------------------------------------------------------------//代码:利用A*算法求解八数码问题。//八数码问题的启发函数设计为:f(n)=d(n)+p(n),其中A*算法中的g(n)根据具体情

最近更新

2025年女性妇科疾病检查全攻略 30页

版国有土地使用权租赁合同(宗地租赁合同) 6页

2025年度生物科技研发与转让交易合同协议书 9页

2025年度生物技术研发免责与成果转化合同 9页

版公司战略合作法律顾问合同 6页

2025年度生态循环农业养殖合作意向书 9页

2025年医院感染防控技能提升培训 30页

2025年BIM技术在养老公寓成本控制与项目管理中.. 30页

2025年免疫学核心揭秘免疫系统与器官功能奥秘.. 27页

2025年度生态农业合伙入股种植合同 8页

2025年度生态保护区临时土地租赁及生态环境保.. 9页

2025年人心解析社会心理学奥秘 20页

2025年度环保项目中介服务合同模板 9页

2025年度环保设备制造员工自愿解除劳动合同协.. 7页

2025年度环保型清洁用品采购及保洁服务合同 9页

2025年个人健康记录管理 37页

2025年度特色课程培训学校品牌授权转让协议 8页

2025年度特色商业街区前期物业管理服务协议 8页

2025年度特种作物种植用地租赁合同范本 8页

2025年度物流园区前期物业管理服务合同 8页

2025年度物业门卫服务质量监控合同 8页

2025年度灾害预防工程外包安全协议 9页

2025年度深圳金融服务业劳动合同电子版规范文.. 8页

2025年度海洋工程设备全新安装合同及海洋环境.. 9页

2025年度海上风电场建设施工协议 9页

2025年度河北省房屋租赁及租期调整合同 8页

2025年度汽车维修保养委托协议合同 9页

2025年度汽车动产质押合同——汽车租赁公司车.. 8页

2025年度水利工程质保金监管与服务协议 8页

2025年安徽省初中学业水平考试名校联考(一)数.. 2页