04-09 17:04 韶关学院 算法工程师 发布于广东
关注
#发面经攒人品#面试被要求手撕A*算法,以下是我的理解:
A* 算法的核心在于估价函数：f(n) = g(n) + h(n)
g(n)：从起点到当前节点的实际代价.
h(n)：从当前节点到终点的预期代价启发式函数，常用曼哈顿距离或欧几里得距离）。
实现的话,通常使用 heapq 维护一个优先队列来获取 f(n) 最小的节点。如果 h(n)=0，它退化为 Dijkstra；如果 h(n) 远大于 g(n)，它演变成贪心最佳优先搜索。
A* 算法的核心在于估价函数：f(n) = g(n) + h(n)
g(n)：从起点到当前节点的实际代价.
h(n)：从当前节点到终点的预期代价启发式函数，常用曼哈顿距离或欧几里得距离）。
实现的话,通常使用 heapq 维护一个优先队列来获取 f(n) 最小的节点。如果 h(n)=0，它退化为 Dijkstra；如果 h(n) 远大于 g(n)，它演变成贪心最佳优先搜索。
全部评论
相关推荐
查看14道真题和解析