在 A* 算法中，在每次迭代中，选择一个节点来最小化某个函数，称为评估函数，在 A* 的情况下，它定义为

在哪里$g(n)$是从起始节点到当前节点的最便宜路径的长度（或成本）$n$和$h(n)$是从当前节点估计最便宜路径成本的启发式函数$n$到目标节点。

从给定节点到目标的路径可能不止一条$n$. 但是，这些路径之一是最便宜的路径。可接受的启发式函数是一种启发式函数，它不会高估到达目标节点的成本，也就是说，它估计到达目标的成本小于或等于从$n$，表示为$h^*(n)$. 因此，一个可接受的启发式$h$满足$h(n) \leq h^*(n), \forall n$. 鉴于目标是找到从起点到目标节点的最便宜的路径，直觉上，可接受的启发式是一种乐观的预测函数。

如果 A* 使用可接受的启发式算法，则可以保证找到最优解（或路径）。在《人工智能原理》 （1982）一书的第 2.4 节中，Nils J. Nilsson 提供了这一事实的证明。

然而，并非所有可接纳的启发式都提供相同的信息，因此并非所有可接纳的启发式都同样有效。例如，一个可以接受的启发式函数是$h(n) = 0, \forall n$. 但是，在这种情况下，用于选择下一个要扩展的节点的唯一实际信息仅基于$g(n)$， 那是，$f(n) = g(n)$. 该评估函数对应于统一成本搜索算法的评估函数，它是一种不知情的搜索算法（与 A* 相反，尽管如此，它被认为是一种知情的搜索算法）。

因此，哪种可接受的启发式更明智？考虑 A* 的两个版本，每个版本都有不同的可接受启发式函数

和

在哪里$h_1(n) \leq h^*(n), \forall n$和$h_2(n) \leq h^*(n), \forall n$. 然后 A* 与评估函数$f_1$比 A* 更知情$f_2$如果，对于所有非目标节点$n$,$h_1(n) > h_2(n)$. 请参阅第 2.4.4 节。在引用的书中给出了一个试图证明这一点的例子。

启发式的可接受性取决于问题。例如，在15 谜题的情况下，曼哈顿距离和汉明距离都是可接受的启发式方法。然而，在其他问题中，这些距离可能不会产生可接受的启发式。