A* 算法的原理与实现
哪些公司问过
答案要点
- 评估函数 f = g + h,g 为起点到当前节点的实际代价,h 为到终点的估计
- 用优先队列维护开放列表,每次扩展 f 最小的节点,处理过的放入关闭列表
- h 可采纳(不高估)才保证最优,满足一致性则节点只扩展一次
- h 为 0 退化成 Dijkstra;h 过大偏向贪心,不保证最优
- 网格地图常用曼哈顿、对角线、欧氏距离作启发函数
易错点
- 启发函数高估代价,导致找不到最优解
- 不说明可采纳和一致性
- 把 A* 说成不需要实际代价 g
面试官常见追问
- A* 里的代价函数怎么定义?
- 混合 A*(Hybrid A*)是什么?
- A* 和 Dijkstra 的区别?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。