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

最近更新

二零二五年度银行上门收款业务标准化合同模板.. 10页

2025年摄影扩印服务项目发展计划 58页

数据泄露检测模型-全面剖析 35页

次性赔偿协议书(22篇) 43页

电子商务毕业生实习心得体会 5页

程序员辞职报告汇编(3篇) 4页

一次飑线(冰雹)天气过程中尺度分析 2页

一机部召开锅炉、压力容器行业工艺纪律座谈会.. 2页

说明文作文300字集锦九篇 8页

第7课《致空气》同步练习(语文版初二下)doc初.. 3页

《光纤与电缆及其应用技术》1988年总目录 2页

“营改增”对建筑施工企业的影响及对策 2页

“新三论”、社会学与地震对策研讨会在吉林省.. 2页

北西尚小学防溺水安全保证书 2页

СТб片梭提花织机在丝织行业的应用 2页

YG811型织物悬垂性测定仪的理论分析与应用 2页

x60级管线钢应力腐蚀性能的研究 2页

U—200型压型钢板在神头电厂工程中的应用 2页

2025年幼儿园安全工作总结及反思五篇 14页

初中新旧德育教科书的比较研究 1页

2025年幼儿园元旦节活动总结篇2025 27页

R-P磷酸工艺球磨机结构设计及操作 2页

2025年(完整版)《人力资源管理》试题及答案 7页

2025年工程竣工自评报告三篇 19页

《高等教育学》考试卷参考答案 5页

深基坑工程施工安全检查验收表 4页

水土保持方案范文5篇 16页

工业工程概论复习题(必过) 14页

苹果采摘机械手设计【水果采摘机】(含CAD图纸.. 38页

旋刀式割草机的改进设计【旋刀式割草机的设计.. 19页