知识卡片
A星最优性依赖启发函数边界
A* 按 f=g+h 排序(g 为已走代价,h 为剩余代价估计),用 OPEN 表存待扩展节点、CLOSED 表存已扩展节点。启发值若从不高估真实剩余代价,称为可采纳;它使搜索有保留最短解的依据。高估可能减少扩展,却会失去最优性保证。
图搜索还要处理“已关闭节点后来又找到更短路径”的情况:常见做法是要求启发值一致(对每条边 n→n′,有 h(n) ≤ 边代价 + h(n′),即估价沿边的下降不超过边的代价),或允许把这类节点重新打开。
停止时机也影响最优性。示例(补充):S→G 直连代价 10;S→A 代价 1,A→G 代价 1;h(A)=1、h(G)=0,均不高估。扩展 S 后,G 以 f=10 进入 OPEN,A 以 f=2 进入 OPEN。若“G 一进 OPEN 就停”,会返回长度 10 的路径;继续取最小 f 的 A,会把 G 的 g 更新为 2,等 G 作为最小 f 节点被取出时才得到真正最短的 2。因此应在目标被取出时判定成功,原书案例的提前停止规则不宜照搬。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- * · 查看原书依据
如果h(n)总是比从n移动到目标的代价小(或相等),那么A*算法保证能找到一条最短路径。
参考来源
- 位置:《智能算法导论》第 175 项《18.2 A*算法实现/18.2.1 A*算法原理》(源文件:`_epub-src/EPUB/xhtml/chapter18_0003.xhtml`)
- 补充位置:第 176 项《18.2.2 A*算法简单案例》(源文件:`_epub-src/EPUB/xhtml/chapter18_0004.xhtml`)
- 结论依据:正文比较低估与高估的最短路径保证;后续步骤写到目标加入 OPEN 即结束。卡片据最优性条件指出该结束规则的风险,并补明图搜索中关闭节点处理的条件。S–A–G 小图为依据可采纳条件补充的教学反例,非书中案例;一致性定义为补充的标准条件,原书未给出。
- 原始内容:如果h(n)总是比从n移动到目标的代价小(或相等),那么A*算法保证能找到一条最短路径……如果h(n)比从n移动到目标的代价高,则A*算法无法保证找到一条最短路径……当目标点B加入OPEN列表或者OPEN列表中没有任何点时,结束循环。