面试题库 › 游戏开发 › A* 算法的原理与实现

A* 算法的原理与实现

难度 ★★★在 7 场真实面经中被问到 方向:游戏开发考点:图论

哪些公司问过

灵犀互娱2字节跳动1网易1文远知行1米哈游1游戏公司合集1

常见岗位:游戏客户端、游戏服务端、自动驾驶

答案要点

  1. 评估函数 f = g + h,g 为起点到当前节点的实际代价,h 为到终点的估计
  2. 用优先队列维护开放列表,每次扩展 f 最小的节点,处理过的放入关闭列表
  3. h 可采纳(不高估)才保证最优,满足一致性则节点只扩展一次
  4. h 为 0 退化成 Dijkstra;h 过大偏向贪心,不保证最优
  5. 网格地图常用曼哈顿、对角线、欧氏距离作启发函数

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题