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年过敏性紫癜日常护理要点解析 47页

城市大龄单身青年婚恋境遇的质性研究 6页

关于自然区划中“主导因素”原则的讨论 2页

关于算术平均数动态分析法中几个问题的商榷 2页

关于矿棉应用中几个问题的探讨 2页

关于用统计阶差法选择趋势曲线的理论研究 2页

2025年胃肠肿瘤诊断与治疗策略 37页

关于海风洗衣皂质量问题的分析研究报告 2页

关于构建我国“新材料产业体系”的思考 2页

关于提高景德镇陶瓷坯料干燥机械强度的研究 2页

关于技术图纸缩微胶片化若干问题的探讨 2页

2025年肌肉骨骼系统影像诊断要点解析 57页

2025年红色卫生员传奇 19页

2025年混流泵项目合作计划书 69页

关于小型理发业卫生监督的初步探讨 2页

常用经支气管镜介入诊疗技术课件 79页

关于基桩抗冻拔验算中几个问题的分析及阐述 2页

关于图书馆是不是阶级斗争工具问题的初步探讨.. 2页

关于吸引外资改善投资环境的思考 2页

关于双轴拉伸高聚物形态结构的研究 2页

关于农村人民公社积累与消费若干问题初探 2页

2025年正确调整呼吸机参数技巧 59页

2025年校园恋爱心理解码 26页

关于“金属矿床的成矿流体性质及成矿、改造深.. 2页

2025年意识丧失紧急处理与照料指南 50页

2025年急性中毒急救策略与处理方法解析 78页

全程底吹小氧量的复吹转炉工艺特点 2页

全国锰矿石工艺特性分类的调查与研究 2页

2025年女性盆腔超声检查攻略 64页