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）。