知识卡片
A星维护待查已查节点与父链
网格 A* 给每个方格记三个值:g 是从起点走到该格的实际代价,h 是到终点的估计代价,f=g+h(见 [[A星用实际代价加剩余估价排序]])。它用 OPEN 保存待检查方格,用 CLOSED 记录已处理方格;取出 OPEN 中 f 最小者,检查可达邻居。新邻居加入 OPEN 并记录父节点;已在 OPEN 的邻居若经当前节点得到更小的 g,就更新代价与父节点。确定目标后沿父链回溯路径。若允许八方向移动,需按斜向成本选择匹配的启发函数;原书在八邻居案例直接举曼哈顿距离,不能无条件保留最短路保证。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- * · 查看原书依据
同时创建一个CLOSED列表,用于保存所有不需要再次检查的方格。
参考来源
- 位置:《智能算法导论》第 176 项《18.2.2 A*算法简单案例》(源文件:`_epub-src/EPUB/xhtml/chapter18_0004.xhtml`)
- 结论依据:正文按 OPEN/CLOSED、最小 `f`、邻居代价更新与父节点回溯讲解网格寻路;图 18.1 展示可通行与不可通行方格。正文同时写“相邻 8 个点”和采用曼哈顿距离,但未限定斜向成本,卡片保留这一适用条件。
- 原始内容:OPEN列表储存待检查方格……CLOSED列表,用于保存所有不需要再次检查的方格……找出OPEN列表中f最小的点……若该点已在OPEN列表中,则检查这条路径是否更优,用g值作参考……从目标点开始沿着父节点回到起点。