[转]A*算法中启发函数的使用(1)

链接:http://godorz.info/2009/11/heuristics-1/


A*算法使用启发函数h(n)来获得对于从任意结点n走到目标结点的最小代价的估计,因此选用一个好的启发函数是非常重要的.

A*算法中启发函数的使用
启发函数可以用来控制A*算法的行为.

在极端情况下,如果h(n)=0,那么只有g(n)实际上是有用的,这时A*算法也就是迪杰斯特拉算法,它能保证一定可以找到一条最优路径.
如果h(n)总是小于(或者等于)从结点n走到目标结点的步数,那么A*算法是一定可以找到最优路径的.h(n)越小,A*扩展的结点越多,导致A*算法越慢.
如果h(n)恰好等于从结点n走到目标结点的步数,A*算法扩展的所有结点都在最优路径上,它不会扩展任何其他无关结点,此时A*算法的速度是非常快的.尽管你无法总是做到这一点,但在某些特定情况下你确实做到.知道A*算法可以在某些时候运行的很好是一件很值得高兴的事.
如果h(n)所给出的信息有时大于从结点n走到目标结点的步数,那么A*算法将无法确保能够找到最优路径,但它会运行得更快.
在另一种极端的情况下,如果h(n)非常接近于g(n),那么只有h(n)将起作用,此时A*算法实际上变成宽度优先搜索.

注意:

从纯粹的技术上说,如果启发函数是对实际耗散值的过低估计的话,A*算法应该叫做简单的A算法.然而,由于在实现上 ,两种算法并无不同的地方,而且在游戏开发社区中,A*算法和A算法并不会被区分开来,所以,接下来我仍然称之为A*算法.
经过上述的讨论后,我们会发现我们面临一个很有趣的问题:我们能通过A*算法得到什么呢?正确的答案是,我们可以很快地得到最优路径.如果h(n)值太低了,那么我们一定能够得到最优路径,但这是以牺牲了算法速度为d代价的.如果h(n)值太高了的话,那么A*算法速度会变快,但是我们无法确保所得到的路径一定是最优的.

在游戏中,A*的这种特性是非常有用的.举个例子,某些时候,你宁愿更快得找出”较优”路径而不是慢悠悠地等着”最优的”路径.为了在h(n)和g(n)中找到平衡,你可以修改其中一个的具体实现.

速度还是准确度?
正如我们提过的,A*算法的表现取决于它的启发函数和耗散函数,这一点在游戏中是很有价值的.权衡速度和准确度的,可以让你的游戏运行得更快.对于大多数游戏而言,你没有必要一定要找出两点间的最优路径.你需要的仅仅是足够接近的答案.你需要什么应视游戏进度和电脑多快决定.

假设你的游戏地图中有两种地形:平原和山地,而且在平原上的单位距离移动代价是1,在山地上的单位距离移动代价是3.(A*算法的目标是找出地图上两点间的最优路径),那么A*算法每在山地上搜索1个单位距离,它在平原上将搜索3个单位距离.这是因为也许存在一条最优路径,它一碰到山地就绕行,即该路径仅仅经过平原地形.通过将两点间的估计距离(即启发信息)设定为1.5,A*算法的速度就可以得到提升了.这时A*算法将比较的是3和1.5,而不是导致它变慢的比较3和1,在山地地形上它的效率将不像后者那么不尽如人意,因此它不会花费太多的时间.或者,你可以通过将A*算法在山地上搜索单位距离的代价降低来提高它的效率–比如说设定为2而不是3,这时A*算法每在山地上搜索1个单位距离,它在平原上将仅仅搜索2个单位距离.两种方法都无法找到最优路径,但能够更快地找到较优路径.

在速度和准确度上的选择并不一定是一成不变的.你可以动态地权衡,这决定于CPU的速度,找出路径的时间对游戏的影响,地图上的结点数目,结点的重要程度,路径群组的大小,游戏的难度级别,或者其他的一些因素.一种动态权衡的方法是,假定最优路径通过单位方格的代价为1,修正的耗散函数如下:

g'(n) = 1 + alpha * (g(n) - 1)
如果alpha=0,那么这个修正的将永远是1.这时,单位距离的代价是被忽略的,A*算法仅是运行在简单的可达方格/不可达方格的程度.如果alpha=1,此时修正的耗散方程将还是原来的耗散方程,这时A*算法效率将带来更好的效率.你可以将alpha设定为[0,1]之间的任意值.

同时,你应该考虑使启发函数返回的是期望最小代价,而不是绝对最小代价.比如说,如果你的地图大部分是单位距离移动代价为2的草地,小部分是单位距离移动代价为1的小路,那么也许你会考虑整副地图启发信息都为2,意味着地图上没有小路.

在速度和准确度上的选择并不一定是全局的.你可以根据某些地图上准确度的重要性来灵活选择.举个例子,假如我们在某些点能够结束路径的重新计算或者改变路径方向,那么选择接近于当前所在结点的路径可能是更为重要的,这样的话,为什么我们还要费事纠结于千里之外的其他路径呢?再举意个例子,在地图上的安全区域,找到最优路径是比较重要的,但是在偷偷的经过敌对势力占领的村子时,快速地得到一条安全的较优路径的要求来得将更为迫切.

比例
A*算法计算f(n)=g(n)+h(n).因此,g(n)和h(n)必须拥有协调的比例.如果g(n)以小时计算,而h(n)以米计算,那么A*算法将会认为g(n)或者h(n)过大,这样的话,要么你无法得到最优路径,或者A*算法将比它原本可以的速度要慢.

精确的启发
如果你的启发函数给出的两个结点间的估计距离恰好等于最优路径上该两点间的距离,那么,正如你将在下一节的图表中看到的,A*算法扩展极少结点.发生在A*算法内部的是,在每一结点,它都会计算f(n)=g(n)+h(n),当h(n)整好等于g(n)时,在遍历最优路径上的结点时,每一结点上的f(n)值恒定不变.所有不在最优路径上的结点的f值都会比最优路径上的结点的f值要高.因为A*算法在考虑完所有拥有较低的f值的结点之前,它并不会考虑f值更高的结点,因此它永远不会偏离最优路径.

已计算过的准确启发信息

一种构造精确启发函数的方法是,预计算最优路径上任意两个结点之间的距离.对于大多数游戏地图而言,这是行不通的.然而,找到近似于精确启发函数的方法是存在的.

考虑所有可能的粗糙结点,它不是最优路径上的结点.预计算任意两个粗糙结点的最短路径.
预计算任意两个拐点(Arthur1989注:请一定猛击链接查看waypoint的定义,才疏学浅的我只能如此翻译了.)之间的最短路径.这是前面粗糙栅格法的一种泛化.
然后,把从任意结点到拐点(Arthur1989注:天阿,为什么又是它,我快自杀了)的估计函数h’加入启发函数h中.最终的启发函数是这样子的:

h(n) = h'(n, w1) + distance(w1, w2), h'(w2, goal)
或者,你可以这样考虑更优的,但是花费计算量更大的启发函数:评价所有临近于起始结点n的结点w1,和所有临近于目标结点的结点w2.

线性精确启发函数

特定情况下,你可以无须通过任何的预计算就得到精确的启发函数.如果你有一个没有任何障碍物的地图,或者地图上没有代价较大的地形,那么从起始结点到目标结点的最优路径就是连接该两点的直线.

如果你正在用着一个简单的启发函数(它并不清楚地图上会有障碍物),那么它将匹配线性精确启发函数,如果不是这样的话,或者在g和h的比例上出现了问题,或者你选择的启发函数类型有些缺陷.