一致且可接受的启发式函数

Question

任何一种连贯的启发式算法都是可接受的。但是什么情况下启发式算法是可接受的而不是连贯的（单调）？

请提供一个这种情况的例子。

- RoarG

Answer 1

作为Russel和Norvig在《人工智能：一种现代方法》（最常用的人工智能教材）中指出的，设计一个既是可接受但不一致的启发式算法非常具有挑战性。

显然，你可以选择图中节点的值，使得它们所代表的启发式算法是可接受但不一致的。Felner等人在这篇论文中给出了一个很好的例子来说明这两种情况的可能性，但它有点难懂，所以我会进行总结：

这个启发式算法在处不一致，因为它给出的达到目标的代价下限比其父节点的代价下限更低（即信息量更少）。通过父节点到达目标的代价估计至少为10（因为到

处的路径代价为5，

处的启发式估计也为5）。然而，通过到达目标的代价估计只有8（父节点的代价（5）加上从父节点到的路径代价（1），再加上处的启发式估计（2））。

由于这张图是无向的，所以这个启发式算法在处也不一致，因为从到

的过程与上述问题相同。

Felner等人还提供了一些关于可接受但不一致的启发式算法的具体例子。考虑八数码难题：

在这个拼图中，有8个滑动方块，编号为1-8，还有一个空格。方块最初是无序的（如左侧图像所示）。目标是通过将方块滑入空格来将拼图完全变成右侧所示的状态。对于此问题的经典启发式方法（每个方块到其应该在的位置的曼哈顿距离）是可接受且一致的。但是，您可以想出不同的启发式方法。也许您只想查看1、2和3到它们在目标状态中应该处于的位置的曼哈顿距离（即格数）。虽然这种启发式方法比所有方块的曼哈顿距离信息少，但仍然是可接受和一致的。

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

- seaotternerd

---

Felner等人在第6节中写道：“正如之前引用的《人工智能：一种现代方法》[38]中所示，人们认为不一致的可接受启发式很难创建。然而，事实证明这并不是真的。” - 其余部分，回答得非常好，谢谢。 - user1544337

Answer 2

可接受的启发式算法

从不高估到达目标的成本。 f(n)从不高估沿着n的当前路径的解决方案的成本。 一个明显的可接受的启发式算法的例子是直线距离。

一致性启发式算法

• 一致性启发式算法：对于每个节点n和通过任何操作a生成的n的每个后继n'：h(n) ≤ c(n,a,n') + h(n')
• 仅在将A*应用于图搜索时需要一致性启发式算法。
• 每个一致性启发式算法也都是可接受的。

- avimimoun

---

每个一致的启发式函数也是可接受的。这个要点为我解决了所有问题。现在我非常理解了，谢谢！ - Frank H

Answer 3

虽然已经过去了很久，但我还是会说出我的看法。我认为最容易理解的方法是，可接受的启发式函数表示当到达特定定义的目标节点时，你不能超越它，而一致的启发式函数则表示在到达任何节点时都不能超越它。这使关系清晰：由于目标节点是某个节点，因此一致的启发式是可接受的。但由于可接受只能保证一个节点的属性，因此可接受不能暗示一致。

- Sam Bobel

---

实际上，这不合理。一个可接受但不一致的启发式算法仍然不能“超出”任何节点，其中“超出”意味着估计成本大于实际成本。一致性关注的是启发式算法自身估计的单调性，而不是绝对的真实成本，而这正是可接受性所关注的。只是碰巧如果在每个步骤中一个启发式算法都是一致的，在k步后，它就不能高估节点的成本，因此一致性始终是可接受的。 - ealfonso

除了@ealfonso的评论之外，启发式是从任意节点到达目标的估计成本，而不是到达任意节点的成本，在这种情况下，您需要两个参数，即起始节点和结束节点。在前一种情况下，也就是通常使用的情况下，谈论到达任意节点的估计成本是没有意义的。 - xyz

我认为这个解释很好。这里的超调意味着新的总路径成本不应该比必须的更高，这意味着你总是能够到达最有前途的节点。 - Kataran

Answer 4

最好将一致性启发式函数视为一个符合三角不等式的可接受启发式函数。

Cost(a -> c) <= Cost(a -> b) + Cost(b -> c)

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

- Rabih Kodeih