1 / 33
文档名称:

A-搜寻算法.docx

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

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

分享

预览

A-搜寻算法.docx

上传人:陈潇睡不醒 2021/1/5 文件大小:54 KB

下载得到文件列表

A-搜寻算法.docx

文档介绍

文档介绍:* 搜寻算法
1968年,的一篇论文,“P. E. Hart, N. J. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths in graphs. IEEE Trans. Syst. Sci. and Cybernetics, SSC-4(2):100-107, 1968”。从此,一种精巧、高效的算法------A*算法横空出世了,并在相关领域得到了广泛的应用。
DFS和BFS在展开子结点时均属于盲目型搜索,也就是说,它不会选择哪个结点在下一次搜索中更优而去跳转到该结点进行下一步的搜索。在运气不好的情形中,均需要试探完整个解集空间, 显然,只能适用于问题规模不大的搜索问题中。
那么,作为启发式算法中的A*算法,又比它们高效在哪里呢?
首先要来谈一下什么是启发式算法。所谓启发式搜索,与DFS和BFS这类盲目型搜索最大的不同,就在于当前搜索结点往下选择下一步结点时,可以通过一个启发函数来进行选择,选择代价最少的结点作为下一步搜索结点而跳转其上(遇到有一个以上代价最少的结点,不妨选距离当前搜索点最近一次展开的搜索点进行下一步搜索)。一个经过仔细设计的启发函数,往往在很快的时间内就可得到一个搜索问题的最优解,对于NP问题,亦可在多项式时间内得到一个较优解。

是的,关键就是如何设计这个启发函数。

A*算法,作为启发式算法中很重要的一种,被广泛应用在最优路径求解和一些策略设计的问题中。而A*算法最为核心的部分,就在于它的一个估值函数的设计上:
f(n)=g(n)+h(n)
其中f(n)是每个可能试探点的估值,它有两部分组成:
一部分为g(n),它表示从起始搜索点到当前点的代价(通常用某结点在搜索树中的深度来表示)。
另一部分,即h(n),它表示启发式搜索中最为重要的一部分,即当前结点到目标结点的估值,
h(n)设计的好坏,直接影响着具有此种启发式函数的启发式算法的是否能称为A*算法。

一种具有f(n)=g(n)+h(n)策略的启发式算法能成为A*算法的充分条件是:
1)搜索树上存在着从起始点到终了点的最优路径。
2)问题域是有限的。
3)所有结点的子结点的搜索代价值>0。
4)h(n)=<h*(n) (h*(n)为实际问题的代价值)。
当此四个条件都满足时,一个具有f(n)=g(n)+h(n)策略的启发式算法能成为A*算法,并一定能找到最优解。([1]P89给出了相关的证明)

对于一个搜索问题,显然,条件1,2,3都是很容易满足的,而
条件4): h(n)<=h*(n)是需要精心设计的,由于h*(n)显然是无法知道的,
所以,一个满足条件4)的启发策略h(n)就来的难能可贵了。
不过,对于图的最优路径搜索和八数码问题,有些相关策略h(n)不仅很好理解,而且已经在理论上证明是满足条件4)的,从而为这个算法的推广起到了决定性的作用。不过h(n)距离h*(n)的呈度不能过大,否则h(n)就没有过强的区分能力,算法效率并不会很高。对一个好的h(n)的评价是:h(n)在h*(n)的下界之下,并且尽量接近h*(n).

继续深入之前,再来看下维基百科对本A*搜索算法的解释:
A*搜寻算法,俗称A星算法。这是一种在图形平面上,有多个节点的路径,求出最低通过成本的算法。常用于游戏中的NPC的移动计算,或线上游戏的BOT的移动计算上。
该算法像Dijkstra算法一样,可以找到一条最短路径;也像BFS一样,进行启发式的搜索。

在此算法中,g(n)表示从起点到任意顶点n的实际距离,h(n)表示任意顶点n到目标顶点的估算距离。因此,A*算法的公式为:f(n)=g(n)+h(n)。这个公式遵循以下特性:
如果h(n)为0,只需求出g(n),即求出起点到任意顶点n的最短路径,则转化为单源最短路径问题,即Dijkstra算法
如果h(n)<=n到目标的实际距离,则一定可以求出最优解。而且h(n)越小,需要计算的节点越多,算法效率越低。

ok,来看下,此A*搜寻算法的算法实现:
closedset := the empty set //已经被估算的节点集合
openset := set containing the initial node //将要被估算的节点集合
g_score[start

最近更新

2025年度实习教师实习期间生活与住宿协议 8页

2025年度学校超市绿色环保包装材料应用与合作.. 9页

2025年度婚礼现场安保责任免除协议 8页

家长在幼儿习惯养成中的作用-培训课件 27页

水泥厂石灰石运输合同3篇 51页

水上石油产品运输合同范本3篇 53页

棋牌室改造维修合同3篇 53页

杭州市艺术馆租赁合同3篇 49页

中和反应的反应热及测定 16页

2025年气浮设备合作协议书 60页

2025年度最佳校运会心得篇 19页

2025年度学校创建文明单位工作计划 25页

2025年店长年终工作总结报告 12页

2025年应该如何投资美股 5页

团支部工作计划范例与团支部工作计划范文2018.. 7页

2025年应届毕业生实习合同电子版本(5篇) 16页

四川省重点小学三年级数学【下册】期末考试试.. 4页

2025年庆祝六一儿童节学校领导国旗下讲话稿 6页

员工转正鉴定评语格式内容与员工辞职报告怎样.. 7页

同学聚会方案:十年情与同学聚会方案:史上最.. 8页

2025年广州市建设工程施工承包合同 5页

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

服装设计合作协议书 5页

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

硫酸铵生产硫酸钾的可行性方案 31页

2022年首都经济贸易大学工商管理专业《管理学.. 22页

学生5mm坐标纸(虚线 word版)直接打印 2页

(完整版)天津大学非线性信息处理技术 12页

中式烹调工艺 2页

燃烧器控制器LFL说明 10页