单调性和启发式的可接纳性之间有什么区别? [英] What is the difference between monotonicity and the admissibility of a heuristic?

问题描述

我正在阅读我的AI教科书，并对单调性和启发式的可接纳性之间的区别感到好奇(我知道它们不是互斥的).

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?

类似地，我如何确定给定的启发式是否单调/可允许的?书中给出的示例之一是8片滑动拼图.我正在考虑的一种启发式方法是不适当地砖的数量，直觉上我可以说我知道它是可以接受的，但是我没有正式的方式来表明它是否是可以接受的/单调的.

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.

推荐答案

第二个解决方案是确保到达任何重复状态的最佳路径始终是第一个重复路径-统一成本搜索就是这种情况.如果我们对h(n)施加额外要求，即 consistency (也称为单调性)，则该属性成立.

The second solution is to ensure that the optimal path to any repeated state is always the first one followed -- as is the case with uniform-cost search. This property holds if we impose an extra requirement on h(n), namely the requirement of consistency (also called monotonicity).

在谈论函数时，单调表示函数增加或减少，但不能同时增加或减少.换句话说，范围中的顺序在整个域中保持不变.因此，无论您从哪一步开始，解决方案都将保持最短的路径.

When you're talking about functions, monotone means that a function increases or decreases, but not both. In other words, the ordering in the range stays the same throughout the domain. For this reason in your problem, the solution maintains the shortest path no matter what step you start at.

启发式的可接纳性属性意味着，达到目标的成本永远不会被高估(即乐观)(第98页).

The admissibility property of a heuristic means that the cost to reach the goal is never overestimated (i.e. it's optimistic) (page 98).

这篇关于单调性和启发式的可接纳性之间有什么区别?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！