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

最近更新

三氯乙醛的土壤污染及其降解研究 2页

2025年幼儿园庆元宵节活动策划方案大全 6页

2025年幼儿园年度教学工作计划最新版 20页

2025年幼儿园师德师风考核制度(7篇) 21页

三、电渗析的进水水质指标和工艺系统的选择 2页

2025年幼儿园小班教育笔记-:如何对待幼儿的打.. 9页

一类球面的扁薄壳体结构的应力分析和计算实例.. 2页

2025年幼儿园家长会工作计划范文3篇 7页

2025年幼儿园安全防范措施方案 35页

一种简便的改进锁相环路牵引能力的方法 2页

一种新的水煤浆制备技术试验成功 2页

一种改进的校准参考标准加速度计的方法 2页

二年级数学上册期中试卷(附参考答案) 7页

二年级数学上册期末标准测试卷及答案 6页

机场跑道工程承揽居间合同3篇 53页

机场扩建土方运输服务合同3篇 55页

木材运输劳务合同样本3篇 53页

服装鞋帽国际海运合同3篇 50页

服装物流配送标准合同模板3篇 50页

服装店装修全包合同模板3篇 48页

月子中心装修合同3篇 51页

智慧旅游用地居间合同样本3篇 57页

时尚街区商场装修合同3篇 54页

旧城改造渣土运输合同3篇 51页

旅游集散中心装修合同模板3篇 53页

旅游地产居间合同样本3篇 51页

五年级语文上册期末考试卷(免费) 8页

2025年大学中国新能源电动汽车消费者调研报告.. 24页

艺术舞蹈老师简历模板 1页

煤炭资源地质勘查设计编写提纲 14页