知识卡片
A星用实际代价加剩余估价排序
A* 用 f(n)=g(n)+h(n) 给待扩展节点排序:g 是从起点已走出的实际代价,h 是到目标的剩余代价估计。每次选择估计总代价最小的待处理节点,再检查邻居;若找到更低的 g,需更新邻居的父节点和代价。h=0 时退化为按已知代价扩展的 Dijkstra 搜索。这个拆分让启发信息影响顺序,但不会替代已发生的路径成本。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- * · 查看原书依据
18.2 A*算法实现 * 18.2 A算法实现 * 18.2.1 A算法原理 A*算法是一种启发式搜索算法,其原理是设计一个代价估计函数: 其中,g(n)为从起点到任意节点n的实际距离,h(n)为任意节点n到目标节点的估计距离(根据采用的评估函数不同而变化),f(n)则为从起点通过节点到达目标节点的最小代价路径的估计值。
参考来源
- 位置:《智能算法导论》第 175 项《18.2 A*算法实现/18.2.1 A*算法原理》(源文件:`_epub-src/EPUB/xhtml/chapter18_0003.xhtml`)
- 结论依据:式(18-1)给出 `f=g+h`;正文分别解释三项含义、按最小估价继续搜索,并指出 `h=0` 对应 Dijkstra 算法。
- 原始内容:g(n)为从起点到任意节点n的实际距离,h(n)为任意节点n到目标节点的估计距离,f(n)则为从起点通过节点到达目标节点的最小代价路径的估计值……每次搜索都找到代价估计值最小的节点再继续进行搜索。