search - 一致和可接受的启发式

Question

任何一致的启发式也是可以接受的。但是什么时候启发式可以接受但不一致(单调)？

请举例说明这种情况。

Answer 1

正如 Russel 和 Norvig 在《人工智能:现代方法》(最常用的 AI 教科书)中指出的那样，提出一种可接受但不一致的启发式方法具有挑战性。

显然，您可以为图中的节点选择值，使得它们所代表的启发式方法是可接受的但不一致。 This paper by Felner et al有一个很好的例子说明了这两种方式，但它有点密集，所以我总结一下:

此启发式在 c1 处不一致因为它给出了比其父节点更低(即信息更少)的成本下限。通过父节点到达目标的成本估计至少为 10(因为到 p 的路径成本是 5，而在 p 处的启发式估计也是 5)。通过 c1 达到目标的成本估算，然而，只是 8(父 (5) 的成本，加上来自父 (1) 的路径成本，加上 c1 (2) 处的启发式估计)。

由于此图是无向图，因此此启发式在 c2 处也不一致。 ，因为来自 c2至 p有与上述相同的问题。

Felner 等人还提供了一些可接受但不一致的启发式的具体示例。考虑8-puzzle问题:



在这个拼图中有 8 个滑动瓷砖，编号为 1-8，还有一个空白区域。瓷砖开始乱序(如左图所示)。目标是通过将瓷砖滑入空白区域，使拼图进入如上图所示的状态。这个问题的经典启发式(每个瓦片到它应该在的位置的曼哈顿距离)是可以接受的和一致的。

但是，您可以提出不同的启发式方法。也许您只想查看 1、2 和 3 到它们应该处于目标状态的位置的曼哈顿距离(即距离的平方数)。启发式虽然比所有瓦片的曼哈顿距离提供的信息少，但仍然是可接受和一致的。

但是假设您选择了一组额外的方块，可能是 5、6 和 7。然后假设您在每个节点上计算启发式的方法是通过随机选择其中一组(1、2 和 3)或 (5、6 和 7) 并计算他们到目标位置的曼哈顿距离。这个启发式是 仍然可以接受 - 它只能低估或匹配达到目标状态所需的移动次数。然而，它是 不再一致 - 每个节点的启发式估计之间没有明确的关系。