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)根据具体情

最近更新

二零二五年度中铁建大桥局与人力资源公司的招.. 8页

2025年公立医院绩效评价与提升策略 109页

2025年意大利留学需要的费用清单 10页

2025年儿童营养健康疾病防控指南 63页

2025年惊蛰的具体时间 5页

二零二五年度个人租赁车辆租赁服务合同模板 8页

二零二五年度个人租房合同协议书——共享办公.. 8页

2025年儿童溺水急救护理探讨 38页

二零二五年度个人投资入股环保科技企业合同 8页

二零二五年度个人房屋租赁合同版专业版(租赁.. 8页

二零二五年度个人存款赠与及税务筹划合同 7页

2025年总经理2025下半年工作计划 10页

2025年思想方面个人总结怎么写7篇 15页

2025年怎样删除word中的简历表格线 2页

2025年怎么规范写低保申请书2025 7页

2025年怎么样安排放暑假的时间 7页

2025年传染病报告卡规范填写攻略 18页

2025年怎么写高中贫困申请书 10页

2025年怎么写申请贫困申请 17页

2025年乙肝患者抗病毒药物正确使用攻略 66页

2025年怀念已逝亲人的悲伤故事:老宅 13页

中铁建大桥局2025年度与咨询机构的工程咨询服.. 8页

个人土地承包经营权合作开发合同(2025年度).. 8页

2025年快乐学习的演讲稿精选篇 11页

矿产资源勘查权竞拍合同范本 7页

最新部编版三年级下册语文全册教案 106页

2级经销商分销协议 5页

村后备干部笔试试题及答案 5页

土地整理项目技术交底教学内容 4页

中医技能知识考试题+答案 20页