【算法】图解A* 搜索算法 |
您所在的位置:网站首页 › 算法流程图怎么画 › 【算法】图解A* 搜索算法 |
最新版本参考(含代码实现):【机器人】路径规划 - 图解A* 搜索算法 - 知乎 A* 算法是启发式搜索算法,是根据Dijkstra算法改进而来。 问题引入如下图所示,S为起始(start)节点,G为目标(goal)节点。 节点之间连线是两点的路径长度,如A到E的路径长度c(A,E) = 9。节点旁的h值时当前节点到达目标节点(G)的预估值,如h(A)=15, 表示从当前点A到达目标点G的估计路径长度为15,此处h(x)即为启发函数,启发函数的设计有很多方法,具体可参考链接,此处不再扩展。从起点S到达当前节点x的路径长度表示为g(x) 。从起点S到达目标G并经过点x的估计距离长度表示为f(x) = g(x) + h(x),该公式是A*算法的核心公式。A*算法通过不断的选择估计距离f最小的节点,逐渐构建最短路径。创建两个集合OPEN集,CLOSED集,算法核心是从OPEN集中选择最优(f值小最优,或f相同时,h小的更优)的节点到CLOSED集中,然后将其后继节点放入OPEN集中,然后重复操作选取最优节点,直到到达目标,或者OPEN为空为止。最后再CLOSED集中根据目标G所包含的前序节点逆序查找最后到达起点S,这个链路的逆序即最优路径,具体流程如下图。 以下是前面网络的搜索过程展开图。 组合块中: 灰色为前序节点蓝色当前节点xg:起点S到当前节点x的路径距离。h:当前节点x到终点G的估计距离f:起点S途径x到达终点G的估计距离,即 f = g + h绿色框为当前OPEN集合中的最优节点红色框表示当前OPEN集合中需要被删除的节点在OPEN、CLOSED中每一行表示一次完整迭代完成时两集合中的节点集合。 最后的最优路径是:S->B->F->k->G 注:当两个节点f相同时,h小的更优 更多阅读 【机器人】 D*算法-动态路径规划 |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |