Forever Loop.

Trouble Busters

Thoughts on Pathfinding – 启发式

启发式函数h(n)用于告知A*从图中任意一个顶点n到终点的最小预计花费。因此选择(构造)一个好的启发式函数是非常重要的。

启发式在A*中的体现:

启发式可以用来控制A*的表现。

  • 在极端情况下,如果h(n)为0,那么这时只有g(n)在负责A*,于是A*算法就变成了能够保证找到最短路径的Dijkstra算法。
  • 如果h(n)总是低于(或者等于)从n移动到终点的花费,A*依旧能够保证找到最短路径。h(n) 越小,A*拓展的节点越多,使得运行速度变慢。
  • 如果h(n)正好等于从n移动到终点的花费,那么A*将只快速得追踪生成的最短路径并且不再拓展节点。尽管这种情况并不可能常常发生,但是你可以在某些特别的环境下使用这种特性。只要你给了A*所需要的最佳的信息,A*的表现将非常优秀。
  • 在另一个极端情况下,如果h(n)相对于g(n)实在是太高了,那么这时只有h(n)在负责A*,于是A*算法就变成了贪婪最优优先搜索。

于是,我们对于h(n)如何控制A*的表现有了一个有趣的认识:在非常恰好的情况下,我们会非常快速得获得最短路径。但如果h(n)太低了,尽管我们依然能够获得最短路径,可是运行速度却变慢了。反之如果h(n)太高了,我们不一定能够获得最短路径,但是运行速度会变快。

A*的这个属性是非常有用的。举个例子,在某些情况下,你可能宁可需要一个只要“足够了”的路径而不是“完美”的路径。于是此时只要改变g(n)和h(n)之间的平衡,你就可以获得自己想要的结果。

注意:从技术上来讲,如果启发式功能没被使用,那么A*算法应该只被称为A。但是,我将仍然称之为A*因为它们的实现仍然是相同的,而且社区上几乎从来不会特意区分A还是A*。

(更多…)