知识卡片
A星效率须按图与启发值检验
A* 的启发函数可把扩展顺序引向目标;启发值越有信息且满足正确性条件,越可能少扩展无关节点。但搜索深度、节点数、内存和运行时间不能只凭“用了启发式”断定更小,还取决于图结构、边权、启发值质量与 OPEN/CLOSED 的实现。若过早丢弃候选或不处理更优到达路径,可能失去最短解;应以固定地图、成本和实现做对照,再评价效率与正确性。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- * · 查看原书依据
18.3 A*算法的优势与缺陷 * 18.3 A算法的优势与缺陷 A*算法利用启发函数估计任意点到目标点的远近程度,省略了大量无用的搜索路径,从而减少了搜索空间,使得搜索方向更加趋向于目标点。
参考来源
- 位置:《智能算法导论》第 177 项《18.3 A*算法的优势与缺陷》(源文件:`_epub-src/EPUB/xhtml/chapter18_0005.xhtml`)
- 结论依据:正文先称启发函数能减少搜索空间、存储与复杂度,随后承认估价不准、过早删除节点会错失最优路径;这些陈述需要与具体图、启发函数及实现条件一同评价。
- 原始内容:A*算法利用启发函数估计任意点到目标点的远近程度……从而减少了搜索空间……引入启发信息的代价函数很难做到完全正确……过早的删除有可能导致算法无法找到最优解。