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

Question

我正在阅读我的人工智能教材，我想知道启发式的单调性和可接受性之间的区别是什么（我知道它们并不互斥）。

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

我遇到困难的是单调性概念。 有人能用我可能理解的方式来描述这一点吗？

同样，我如何确定给定的启发式是单调/可接受的？书中给出的一个例子是8碎片滑动拼图。 我考虑的一个启发式是放错的瓷砖数目，直觉上我可以说我知道它是可接受的，但我没有正式的方法来显示它是否是可接受/单调的。

- mmcdole

---

Dana the Sane的帖子应该会有很大帮助。为了展示可接受性，只需证明您的启发式算法总是猜测需要比实际最优路径少走几步的解决方案。对于滑动拼图和#个错误块启发式算法来说，简单地说，一个错位的块必须移动才能到达它的位置，因此我的启发式算法的猜测必须是最优的或者比实际步数更少。要证明不可接受性，请展示一个反例（通常很容易快速找到不可接受的启发式算法）。 - Nick Larsen

有关单调性（也称一致性）和可接受性以及它们不重叠的情况和上下文的进一步讨论，请参见我的答案：https://dev59.com/CWIj5IYBdhLWcg3wMinW#20532330。 - seaotternerd

这个问题在StackOverflow上是否相关？听起来更像是cs.stackexchange的问题。 - CodyBugstein

@Imray，在这个问题被问出来的时候（2009年），cs.stackexchange.com网站还不存在。 - mmcdole

Answer 1

《Russel和Norvig，第二版第99页》说：

第二种解决方法是确保到达任何重复状态的最优路径始终是第一条遵循的路径——就像均匀成本搜索一样。如果我们对h（n）施加额外的一致性要求（也称为单调性），则该特性成立。

当涉及函数时，单调意味着函数增加或减少，但不会同时发生。换句话说，在定义域中，范围的排序保持不变。因此，在您的问题中，无论从哪个步骤开始，该解决方案都会维护最短路径。

启发式的可接受性属性意味着到达目标的成本永远不会被高估（即乐观估计）（第98页）。

- Dana the Sane

---

从同一本书中，他们很好地通过在NxN滑动面板游戏中使用曼哈顿距离来说明可接受性。这是一个理解启发式算法的好章节。 - Nick Larsen

Answer 2

可接受性：

如果搜索算法能够保证找到最小路径解决方案，则该算法是可接受的。广度优先搜索是可接受的，因为它在考虑第n+1层状态之前会查看第n层的每个状态。

单调性：

这个属性要求算法是局部可接受的——也就是说，在搜索空间中，它始终低估任意两个状态之间的成本。回想一下，A*不要求g(n) = g*(n)。如果启发式函数h满足以下条件，则h是单调的： 1.对于所有状态ni和后代nj，其中nj是ni的后代，h(ni) - h(nj) <= cost(ni,nj)。

2.目标状态的启发式评估为0：h(Goal) = 0。

- jinu

Answer 3

单调学习是指代理程序不会学习任何与其已知知识相矛盾的知识。例如，它不会用其否定形式替换一个语句。因此，知识库只能以单调方式增长新事实。单调学习的优点包括：

1.大大简化了真实维护

2.在学习策略上有更多选择

非单调学习是指代理程序可以学习与其已知知识相矛盾的知识。因此，如果它认为有充分的理由这样做，它可以用新知识替换旧知识。非单调学习的优点包括：

1.增加了对真实领域的适用性

2.在学习顺序上有更大的自由度

相关属性是知识的一致性。如果架构必须维护一致的知识库，则其使用的任何学习策略都必须是单调的。

- Rahul

---

我认为你可能没有仔细区分“知识”和“信念”的区别。为什么一个代理从交通灯是红色变成了绿色？这两者之间的矛盾是两个知识之间的矛盾吗？在人工智能中，通常用于描述这种现象的术语是“信念修正”。 - Charles Stewart