首页 » 算法技术手册 » 算法技术手册全文在线阅读

《算法技术手册》分析

关灯直达底部

A*搜索的行为完全取决于启发函数。最近的研究结果(Russel和Norvig,2003)表明,如果|h(x)-h*(x)|≤logh*(x),那么性能将会是O(d),d表示解的距离,而不是O(bd),b表示搜索树的分支因子。但是,这个条件难以满足,在八数码问题表现很好的GoodEvaluator函数也不能满足这个条件。

随着棋面状态变得越来越复杂,启发式函数越来越重要,同时也越来越难以设计。首先启发式函数必须足够高效,或者能够影响整个搜索过程。但是,即使是最差的启发式函数都能够较好地剪枝搜索空间。例如,十五数码问题,八数码问题的一个扩展,使用八数码问题的GoodEvaluator函数扩展时,目标状态如下:

初始状态如下:

A*搜索在处理39个棋面状态之后,快速找到了一个15步的解,这个时候开放集合中还有43个棋面状态,如图7-13所示。

图 7-13 十五数码问题的A*搜索树

由于有着15步的限制,深度优先搜索在处理22 136个棋面状态之后,仍然没有找到解。而广度优先搜索在处理172 567个状态(85 213在闭合集中,剩余87 354在开放集中)时,已经耗尽了所有的64MB内存。当然你可以加内存或者增大搜索深度限制,但是这些并不是你无法解出这些问题的理由。

不要被A*搜索这么容易解出十五数码所迷惑,当初始棋面状态更加复杂时,例如:

A*搜索也耗尽了内存。很明显,这个评估函数并不高效,这个例子有超过1025个可能的状态(Korf,2000)。