computer-science - 单调性和启发式的可接受性有什么区别？

Question

我正在阅读我的 AI 教科书，我很好奇启发式的单调性和可接受性之间的区别(我知道它们并不相互排斥)。

据我所知，可接受的启发式方法仅仅意味着如果存在解决方案，您可以确保获得解决方案的最短路径。

我正在努力解决的是单调属性的概念。有人可以用我可能理解的方式向我描述这个吗？

同样，我如何确定给定的启发式是否是单调的/可接受的？书中给出的例子之一是 8 片滑动拼图。我正在考虑的一种启发式方法是# of out place tiles，直观地说我知道它是可接受的，但我没有正式的方式来表明它是否是可接受的/单调的。

Answer 1

Russel and Norvig, 2ed page 99说:

The second solution is to ensure that the optimal path to any repeated state is always the first one followed -- as is the case with uniform-cost search. This property holds if we impose an extra requirement on h(n), namely the requirement of consistency (also called monotonicity).

当您谈论函数时，单调意味着函数增加或减少，但不是两者兼而有之。换句话说，范围内的顺序在整个域中保持不变。出于这个原因，在您的问题中，无论您从哪一步开始，解决方案都会保持最短路径。

受理启发式的属性意味着达到目标的成本永远不会被高估(即它是乐观的)(第 98 页)。