1 / 11
文档名称:

A星算法详解.docx

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

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

分享

预览

A星算法详解.docx

上传人:百里登峰 2021/7/3 文件大小:18 KB

下载得到文件列表

A星算法详解.docx

相关文档

文档介绍

文档介绍:初识A*算法
写这篇文章的初衷是应一个网友的要求,当然我也发现 现在有关人工智能的中文站点实在太少,我在这里抛砖引玉, 希望大家都来热心的参与。
还是说正题,我先拿 A*算法开刀,是因为 A*在游戏中 有它很典型的用法,是人工智能在游戏中的代表。
A*算法在人工智能中是一种典型的启发式搜索算法,为 了说清楚A*算法,我看还是先说说何谓启发式算法。
一、何谓启发式搜索算法
在说它之前先提提状态空间搜索。状态空间搜索,如果 按专业点的说法就是将问题求解过程表现为从初始状态到 目标状态寻找这个路径的过程。通俗点说,就是在解一个问 题时,找到一条解题的过程可以从求解的开始到问题的结果
(好象并不通俗哦)。由于求解问题的过程中分枝有很多, 主要是求解过程中求解条件的不确定性,不完备性造成的, 使得求解的路径很多这就构成了一个图,我们说这个图就是 状态空间。问题的求解实际上就是在这个图中找到一条路径 可以从开始到结果。这个寻找的过程就是状态空间搜索。
常用的状态空间搜索有深度优先和广度优先。广度优先 是从初始状态一层一层向下找,直到找到目标为止。深度优 先是按照一定的顺序前查找完一个分支,再查找另一个分支,
以至找到目标为止。这两种算法在数据结构书中都有描述, 可以参看这些书得到更详细的解释。
前面说的广度和深度优先搜索有一个很大的缺陷就是 他们都是在一个给定的状态空间中穷举。这在状态空间不大 的情况下是很合适的算法,可是当状态空间十分大,且不预 测的情况下就不可取了。 他的效率实在太低,甚至不可完成。 在这里就要用到启发式搜索了。
启发式搜索就是在状态空间中的搜索对每一个搜索的 位置进行评估,得到最好的位置,再从这个位置进行搜索直 到目标。这样可以省略大虽无畏的搜索路径,提到了效率。 在启发式搜索中,对位置的估价是十分重要的。采用了不同 的估价可以有不同的效果。我们先看看估价是如何表示的。
启发中的估价是用估价函数表示的,如:
f(n) = g(n) + h(n)
其中f(n)是节点n的估价函数,g(n)实在状态空间中从初 始节点到n节点的实际代价,h(n)是从n到目标节点最佳路 径的估计代价。在这里主要是 h(n)体现了搜索的启发信息,
因为g(n)是已知的。如果说详细点,g(n)代表了搜索的广度的 优先趋势。但是当h(n)>>g(n)时,可以省略g(n),而提高效率。 这些就深了,不懂也不影响啦!我们继续看看何谓 A*算法
二、初识A*算法
启发式搜索其实有很多的算法,比如:局部择优搜索法、 最好优先搜索法等等。 当然A*也是。这些算法都使用了启发 函数,但在具体的选取最佳搜索节点时的策略不同。象局部 择优搜索法,就是在搜索的过程中选取“最佳节点”后舍弃 其他的兄弟节点,父亲节点,而一直得搜索下去。这种搜索 的结果很明显,由于舍弃了其他的节点,可能也把最好的节 点都舍弃了,因为求解的最佳节点只是在该阶段的最佳并不 一定是全局的最佳。最好优先就聪明多了,他在搜索时,便 没有舍弃节点(除非该节点是死节点) ,在每一步的估价中
都把当前的节点和以前的节点的估价值比较得到一个“最佳 的节点”。这样可以有效的防止“最佳节点”的丢失。那么 A*算法乂是一种什么样的算法呢?其实 A*算法也是一种最
好优先的算法。只不过要加上一些约束条件罢了。由于在一 些问题求解时,我们希望能够求解出状态空间搜索的最短路 径,也就是用最快的方法求解问题, A*就是干这种事情的!
我们先下个定义,如果一个估价函数可以找出最短的路径, 我们称之为可采纳性。A*算法是一个可采纳的最好优先算法。 A*算法的估价函数可表示为:
f(n) = g'(n) + h'(n)
这里,f(n)是估价函数,g'(n)是起点到终点的最短路径 值,h'(n)是n到目标的最断路经的启发值。由于这个 f(n)其
实是无法预先知道的,所以我们用前面的估价函数 f(n)做近
似。g(n)代替g'(n),但g(n)>=g'(n)才可(大多数情况下都是满 足的,可以不用考虑),h(n)代替h'(n),但h(n)<=h'(n)才可(这 一点特别的重要)。可以证明应用这样的估价函数是可以找 到最短路径的,也就是可采纳的。我们说应用这种估价函数 的最好优先算法就是 A*算法。哈!你懂了吗?肯定没懂! 接
着看!
举一个例子,其实广度优先算法就是 A*算法的特例。其 中g(n)是节点所在的层数,h(n)=0,这种h(n)肯定小于h'(n), 所以由前述可知广度优先算法是一种可采纳的。实际也是。 当然它是一种最臭的 A*算法。
再说一个问题,就是有关 h(n)启发函数的信息性。h(n)
的信息性通俗点说其实就是在估计一个节点的值时的约束 条件,如

最近更新

关于向市场经济机制转换中若干茶业问题的探讨.. 2页

2025年环境污染对人体健康的影响与对策 34页

关于农产品“卖难”的起因与对策的研究 2页

关于与农药研究有关的专利、文献的调查 2页

关于“南水北调中线干线工程”年度价格指数的.. 2页

2025年护士早间交接流程标准化指南 16页

2025年急性弥漫性脑脊髓炎症候群 21页

2025年小儿肺炎合并心力衰竭治疗策略 40页

2025年PCR结核检测技能培训攻略 14页

全国丹霞地貌旅游开发学术讨论会在丹霞山召开.. 2页

光电保护在具有刚性离合器压力机上的应用 2页

2025年全面护理体检攻略 11页

体育教师述职报告怎么(15篇下载) 40页

2025年频繁性呼吸不畅问题解析 23页

关于小班教案锦集5篇 12页

2025年膝关节半月板损伤MRI诊断要点 56页

2025年脑溢血患者家庭护理要点 20页

大学生安全责任承诺书集锦(8篇) 13页

学校学生会主席工作计划(16篇) 18页

2025年泌尿系统疾病护理要点解读 59页

2025年婴儿新生儿抢救技巧 67页

二零二五年度企业员工职称评定补贴合同 8页

二零二五年度人民币单位协定存款账户资金结算.. 8页

二零二五年度人力资源公司劳动合同履行与员工.. 8页

二零二五年度交通事故当事人自愿赔偿执行协议.. 7页

2025年感恩亲情作文一千五百字 12页

二零二五年度临建设施转让合同书,涵盖临时工.. 9页

二零二五年度中学兼职教师合同协议书(文学教.. 8页

二零二五年度个体经营户员工劳动法适用劳动合.. 7页

二零二五年度个人车库买卖合同(附车位改造协.. 8页