A*搜索的效果直接依赖于其启发式函数。如果h*(n)一直为0，那么A*搜索不会比广度优先搜索要好。但是如果h*(n)＞h(n)，那么A*搜索虽然能够给出一些解，但是也许不能够得到最优解。
如果启发函数h*(n)性能可以接受，那么这时候我们就可以使用A*搜索。如果，那么表示启发式函数是可以接受的。这种限制需要满足两个方面的条件，如果h*(n)返回一个负数（表示有时候棋面状态n越过了目标状态），那么g*(n)的效果就会被抵消掉。如果h*(n)＞h(n)，那么A*搜索可能找不到最优解。寻找到一个合适的高效h*(n)函数是非常困难的。不过有大量不可接受的h*(n)，它们可以得到可行解，但是并不最优。
如果h*(n)可行，那么A*搜索将会寻找到最优解。对于八数码问题来说，表7-3列出了下述棋面状态下，三个启发式函数的情况。