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年彼岸花的花语是什么有什么含义 5页

2025年度酒吧行业顾客饮酒免责安全约定 7页

电子产品销售合同范文 7页

2025年度跨境电商公司员工劳动合同及福利保障.. 8页

2025年度购房定金协议及新房团购合同 8页

电力销售合同 6页

2025年度虚拟现实产品研发合作合同 9页

2025年度艺术品寄卖与展览策划合同 8页

2025年经皮肾镜碎石技巧与并发症应对策略 28页

2025年度航空航天维修合作购买厂房及维修设备.. 9页

动作捕捉技术在动画创作中的作用-全面剖析 21页

2025年甲状腺髓样癌诊疗攻略 18页

环保设施施工承包合同书 8页

2025年犯罪心理形成机制深度解析教学指导 27页

2025年度美容院美容养生项目推广合作合同 9页

独资企业股权转让合同模板 7页

2025年度网络安全行业人力资源劳动合同细则 8页

2025年开学第一课演讲稿优秀范文20篇 35页

2025年教育评估心理探索与策略优化 24页

2025年开学相关作文00字 14页

2025年开学心理健康第一课学生观后感 26页

2025年开学典礼教师致辞模板五篇 19页

高速加工中心的温度管理研究-全面剖析 24页

2025年度纺织面料国际贸易代理购销合同 9页

物业管理合同的范本 7页

2025年建筑类年度考核工作总结汇报七篇 30页

2025年度社区老年人免费体检服务合同书 9页

2025年度矿山安全生产技术服务合同 9页

2025年度监护人责任免除与监护权变更协议 8页

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