← 返回刚才阅读的位置

知识卡片

普通读书笔记卡 · 3787.a.3

A星维护待查已查节点与父链

理解等级:中级

网格 A* 给每个方格记三个值:g 是从起点走到该格的实际代价,h 是到终点的估计代价,f=g+h(见 [[A星用实际代价加剩余估价排序]])。它用 OPEN 保存待检查方格,用 CLOSED 记录已处理方格;取出 OPEN 中 f 最小者,检查可达邻居。新邻居加入 OPEN 并记录父节点;已在 OPEN 的邻居若经当前节点得到更小的 g,就更新代价与父节点。确定目标后沿父链回溯路径。若允许八方向移动,需按斜向成本选择匹配的启发函数;原书在八邻居案例直接举曼哈顿距离,不能无条件保留最短路保证。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《智能算法导论》第 176 项《18.2.2 A*算法简单案例》(源文件:`_epub-src/EPUB/xhtml/chapter18_0004.xhtml`) - 结论依据:正文按 OPEN/CLOSED、最小 `f`、邻居代价更新与父节点回溯讲解网格寻路;图 18.1 展示可通行与不可通行方格。正文同时写“相邻 8 个点”和采用曼哈顿距离,但未限定斜向成本,卡片保留这一适用条件。 - 原始内容:OPEN列表储存待检查方格……CLOSED列表,用于保存所有不需要再次检查的方格……找出OPEN列表中f最小的点……若该点已在OPEN列表中,则检查这条路径是否更优,用g值作参考……从目标点开始沿着父节点回到起点。