面试题库 › 客户端 › A* 算法如何保证找到最优路径

A* 算法如何保证找到最优路径

难度 ★★☆在 2 场真实面经中被问到 方向:客户端考点:寻路与空间加速

哪些公司问过

米哈游2

常见岗位:C++ / Qt 客户端、游戏客户端

答案要点

  1. f(n)=g(n)+h(n),h 是到终点的估计代价
  2. 可采纳:h 永不高估真实代价,是保证最优的条件
  3. 使用关闭列表时需一致性:h(n) ≤ c(n,n') + h(n')
  4. 终点从开放列表中取出时才结束
  5. h 越接近真实越高效;h=0 退化为 Dijkstra,高估可能次优

易错点

面试官常见追问

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

相关面试题