22

I'm reading over my AI textbook and I'm curious about what the difference is between monotonicity and admissibility of heuristics (I know they aren't mutually exclusive).

As far as I can tell, an admissible heuristic simply means you are ensured to get the shortest path to a solution if one exists.

What I'm struggling with is the concept of the monotonic property. Can someone describe this to me in a way I might understand?

Similarly, how can I determine if a given heuristic is monotonic/admissible? One of the examples given in the book is the 8-Piece Sliding Puzzle. One heuristic I'm considering is the # of out of place tiles, and intuitively I can say that I know that it is admissible but I have no formal way of showing if it is admissible/monotonic.

4

3 回答 3

20

Russel 和 Norvig，第 2 版，第 99 页说：

第二种解决方案是确保任何重复状态的最佳路径始终是第一个遵循的路径——就像统一成本搜索的情况一样。如果我们对 施加额外的要求h(n)，即一致性要求（也称为单调性），则此属性成立。

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

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

于 2009-10-14T20:08:58.277 回答
2

可受理性：

一个搜索算法是可以接受的，如果它保证找到一个解决方案的最小路径，只要这样的解决方案存在。广度优先搜索是可以接受的，因为它先查看第 n 层的每个状态，然后再考虑第 n+1 层的任何状态。

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

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

于 2013-12-02T12:02:04.320 回答
-2

单调学习是指代理可能无法学习任何与其已经知道的知识相矛盾的知识。例如，它不能用它的否定代替一个陈述。因此，知识库可能只会随着新事实以单调的方式增长。单调学习的优点是：

1.大大简化了真相维护

2.学习策略的更多选择

非单调学习是指代理可能学习与其已经知道的知识相矛盾的知识。因此，如果它认为有足够的理由这样做，它可能会用新知识代替旧知识。非单调学习的优点是：

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

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

一个相关的属性是知识的一致性。如果架构必须保持一致的知识库，那么它使用的任何学习策略都必须是单调的。

于 2010-10-26T15:06:34.803 回答