A*寻路算法的原理与实现
答案要点
- f(n)=g(n)+h(n),g 为起点到 n 的实际代价,h 为到终点的启发估计
- 开放列表用按 f 排序的优先队列,关闭集合记录已确定节点,父指针回溯路径
- h 可采纳(不高估)保证最优;h 满足一致性时出队节点无需重新打开
- h=0 退化为 Dijkstra,h 高估接近贪心最佳优先,速度快但可能不是最短路
- 启发选择:四方向曼哈顿距离,八方向对角距离,任意方向欧氏距离
易错点
- 启发函数高估了真实代价却仍声称结果最优
- 八方向移动却用曼哈顿距离作启发,可能高估导致路径非最优
- 找到更小的 g 时只改了 g 没改父指针,回溯出错误路径
面试官常见追问
- A* 和 Dijkstra、BFS 有什么关系?
- 大地图上 A* 太慢怎么优化?
- 开放列表里同一个节点出现多次怎么处理?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。