什么时候启发式是可接受的但不一致？

Question

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

请提供一个属于这种情况的示例。

Answer 1

正如 Russel 和 Norvig 在《人工智能：现代方法》（最常用的人工智能教科书）中指出的那样，提出一种可接受但不一致的启发式方法是具有挑战性的。 显然，您可以为图中的节点选择值，使得它们表示的启发式是可接受的但不一致。

Felner 等人的这篇论文

有一个很好的例子，说明了这两种可能的方法，但它有点密集，所以我总结一下：

此启发式在

c1
• 处不一致，因为它给出的达到目标的成本下限比其父节点更低（即信息较少）。通过父节点到达目标的成本估计至少为 10（因为到

  p

  的路径成本为 5，并且

  p

  处的启发式估计也是 5）。然而，通过

  c1

  到达目标的成本估计仅为 8（父级 (5) 的成本，加上父级 (1) 的路径成本，加上

  c1

  (2) 处的启发式估计）。由于该图是无向的，因此该启发式在
c2
• 处也是不一致的，因为从

  c2

  到

  p

  具有与上面相同的问题。
Felner 等人还提供了一些可接受但不一致的启发式的具体示例。考虑 8 谜题：

在这个拼图中有 8 个编号为 1-8 的滑动瓷砖和一个空白区域。瓷砖开始时是无序的（如左图所示）。目标是仅通过将瓷砖滑入空白区域来使拼图进入右上所示的状态。此问题的经典启发式（每个图块到其应有位置的曼哈顿距离）是可接受的且一致的。

但是，您可以想出不同的启发法。也许您只想查看 1、2 和 3 到它们应该处于目标状态的位置的曼哈顿距离（即相距的平方数）。尽管启发式的信息量不如所有图块的曼哈顿距离，但仍然是可接受的且一致的。

但是假设您选择了一组额外的方格，可能是 5、6 和 7。然后假设您计算每个节点的启发式的方法是随机选择这些集合中的一个（1,2 和 3） ) 或 (5、6 和 7) 并计算他们到目标位置的曼哈顿距离。这种启发式方法“仍然是可接受的”——它只能低估或匹配达到目标状态所需的移动次数。然而，它

不再一致

——每个节点的启发式估计之间没有明确的关系。 可接受的启发式

Answer 2

一致性启发式

一致启发式：对于由任何操作 a 生成的每个节点 n 和 n 的每个后继 n'： h(n) ≤ c(n,a,n') + h(n')

仅适用于 A* 图形搜索的应用

• 每一个一致的启发式也是可接受的。
死了很久了，但无论如何我都会捐出我的两分钱。我认为到目前为止最简单的思考方法是，可接受的启发式表示在到达特定定义的目标节点时不能超调，而一致的启发式表示在到达任何节点时都不能超调。这使得关系变得清晰：由于目标节点是某个节点，因此可以接受一致的启发式。但由于admissible仅保证一个节点的这一属性，因此admissible并不意味着一致性。

Answer 3

最好将一致启发式视为遵循三角不等式的可接受启发式：

Answer 4

对于搜索空间中的任意三个节点 a、b 和 c，请理解成本是使用相邻节点之间的实际成本计算的，否则使用启发式计算。