3.A星寻路算法的基本原理
3.1 题目
请简单描述A星寻路算法的基本原理。
3.2 深入解析
关键点
- 寻路消耗公式：
f(寻路消耗)=g(离起点距离)+h(离终点距离) - 开启列表：记录待检查的节点。
- 关闭列表：记录已检查的节点。
基本原理
A星（A*）是一种启发式图搜索算法，常用于网格/导航图寻路。在启发函数 h 可采纳（不高估实际代价）等前提下，能保证得到最优路径；其基本原理如下：
初始化：
- 将起点加入开启列表。
- 设定起点的g值为0，h值为起点到终点的估算距离。
循环过程：
- 从开启列表中取出f值最小的节点作为当前节点。
- 将当前节点从开启列表移到关闭列表。
- 检查当前节点的所有相邻节点：
- 如果相邻节点是终点，则路径找到，算法结束。
- 如果相邻节点不在关闭列表中，计算其g值和h值，并将其加入开启列表。
- 如果相邻节点已在开启列表中，检查新的g值是否更小，如果是则更新该节点的g值和父节点。
结束条件：
- 如果开启列表为空，则表示没有找到路径。
- 如果找到终点，则可以通过节点的父节点链回溯到起点，得到完整路径。
3.3 答题示例
“A* 算法是基于启发式搜索的图遍历算法，它为每个节点维护：
- g：从起点移动到该节点的实际代价，
- h：该节点到终点的估算代价（启发式函数，如曼哈顿距离），
- f = g + h：总估算代价。
核心流程：
将起点放入“开启列表”；
每次从开启列表取 f 最小的节点作为当前节点，移到“关闭列表”；
对其相邻节点计算 g、h 和 f：
- 若相邻节点未入开启或关闭列表，则加入开启列表；
- 若已在开启列表且新 g 更小，则更新其 g 和父节点；
重复直到遇到终点或开启列表空。
最终通过父节点指针从终点回溯到起点得到路径；若 h 可采纳，该路径为最优解。”
3.4 关键词联想
- 启发式函数（Heuristic）
- g(n) = 起点→当前代价
- h(n) = 当前→终点估算
- f(n) = g + h
- 开启列表（Open Set）
- 关闭列表（Closed Set）
- 曼哈顿距离 / 欧氏距离
- 节点回溯（Parent Pointer）
- 最短路径
- 优先队列（Priority Queue）
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com
