A* 算法如何保证找到最优路径
哪些公司问过
答案要点
- f(n)=g(n)+h(n),h 是到终点的估计代价
- 可采纳:h 永不高估真实代价,是保证最优的条件
- 使用关闭列表时需一致性:h(n) ≤ c(n,n') + h(n')
- 终点从开放列表中取出时才结束
- h 越接近真实越高效;h=0 退化为 Dijkstra,高估可能次优
易错点
- 用会高估的启发函数,仍认为结果最优
- 第一次生成终点节点就返回,而不是等其出队
- 八方向移动仍用曼哈顿距离,导致高估
面试官常见追问
- 只满足可采纳、不满足一致性会怎样?
- 网格地图上常用哪些启发函数?
- 为什么有时故意用加权 A*?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。