我正在阅读我的人工智能教材,我想知道启发式的单调性和可接受性之间的区别是什么(我知道它们并不互斥)。
据我所知,可接受的启发式只意味着如果存在解决方案,则确保您获得最短路径。
我遇到困难的是单调性概念。 有人能用我可能理解的方式来描述这一点吗?
同样,我如何确定给定的启发式是单调/可接受的?书中给出的一个例子是8碎片滑动拼图。 我考虑的一个启发式是放错的瓷砖数目,直觉上我可以说我知道它是可接受的,但我没有正式的方法来显示它是否是可接受/单调的。
我正在阅读我的人工智能教材,我想知道启发式的单调性和可接受性之间的区别是什么(我知道它们并不互斥)。
据我所知,可接受的启发式只意味着如果存在解决方案,则确保您获得最短路径。
我遇到困难的是单调性概念。 有人能用我可能理解的方式来描述这一点吗?
同样,我如何确定给定的启发式是单调/可接受的?书中给出的一个例子是8碎片滑动拼图。 我考虑的一个启发式是放错的瓷砖数目,直觉上我可以说我知道它是可接受的,但我没有正式的方法来显示它是否是可接受/单调的。
第二种解决方法是确保到达任何重复状态的最优路径始终是第一条遵循的路径——就像均匀成本搜索一样。如果我们对
h(n)
施加额外的一致性要求(也称为单调性),则该特性成立。
当涉及函数时,单调意味着函数增加或减少,但不会同时发生。换句话说,在定义域中,范围的排序保持不变。因此,在您的问题中,无论从哪个步骤开始,该解决方案都会维护最短路径。
启发式的可接受性属性意味着到达目标的成本永远不会被高估(即乐观估计)(第98页)。
可接受性:
如果搜索算法能够保证找到最小路径解决方案,则该算法是可接受的。广度优先搜索是可接受的,因为它在考虑第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。
单调学习是指代理程序不会学习任何与其已知知识相矛盾的知识。例如,它不会用其否定形式替换一个语句。因此,知识库只能以单调方式增长新事实。单调学习的优点包括:
1.大大简化了真实维护
2.在学习策略上有更多选择
非单调学习是指代理程序可以学习与其已知知识相矛盾的知识。因此,如果它认为有充分的理由这样做,它可以用新知识替换旧知识。非单调学习的优点包括:
1.增加了对真实领域的适用性
2.在学习顺序上有更大的自由度
相关属性是知识的一致性。如果架构必须维护一致的知识库,则其使用的任何学习策略都必须是单调的。