什么启发式评估函数或算法可以被视为不可接受

Question

我已经学习了几个启发式函数，它们可以用来处理经典的8字谜问题，我知道你可以将一个因子乘以一个可接受的函数，使其不可接受，然而，我想知道是否有其他不可接受的启发式函数来处理8字谜问题？

Answer 1

对于这个难题，有各种各样不可接受的启发式方法。不可接受的启发式方法只需要高估解决给定难题所需的步骤数，因此一个简单的不可接受的启发式方法是

h(S) = infinity

由于任何可解的难题都可以在少于无限步的时间内解决，因此启发式是不可接受的。

一个更棘手、更有趣的问题是，有什么好的可接受的启发式算法，因为它们要求您尽可能地给出最大的值，而不是高估距离。对于这个问题，我没有一个好的答案。:-)

Answer 2

启发式评估函数估计了单智能体路径查找问题中两个状态之间的最优路径的成本。

阅读更多关于Heuristic evaluation function的文章。

Answer 3

基本上，任何高估成本的函数都是不可接受的，这意味着构造不可接受的函数是很容易的。

Wikipedia有一个很好的描述