请写一个A*算法的启发函数
时间: 2023-06-13 20:03:42 浏览: 109
A*算法的启发函数是一种估计算法从当前节点到终点的距离的函数。一个好的启发函数可以大大提高A*算法的效率。
其中一个常用的启发函数是曼哈顿距离启发函数。对于一个节点 (x1, y1) 和终点 (x2, y2),它的曼哈顿距离启发函数为:
h(x1, y1, x2, y2) = |x1 - x2| + |y1 - y2|
这个函数计算的是两点在水平和垂直方向上的距离(即曼哈顿距离)。它可以有效地估计从当前节点到终点的距离,因为在一个网格地图中,只能向上、下、左、右四个方向移动。
如果你的问题不是网格图,你可以使用其他的启发函数,例如欧几里得距离启发函数、切比雪夫距离启发函数等。
阅读全文