何时启发式是可采纳的但不一致?

任何一致的启发式也是可采纳的。但是,启发式何时是可采纳的但不一致(单调的)呢?

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


回答:

正如Russel和Norvig在《人工智能:现代方法》(最常用的AI教科书)中指出的那样,提出一个可采纳但不一致的启发式是具有挑战性的。

显然,你可以在图中的节点上选择值,使它们代表的启发式是可采纳的但不一致的。Felner等人的这篇论文很好地展示了这两种可能的方式,但内容有点密集,所以我来总结一下:

一个可采纳但不一致的启发式

  • 这个启发式在c1处不一致,因为它给出的到达目标的成本下限(即较少的信息量)低于其父节点。通过父节点到达目标的成本估计至少为10(因为到达p的路径成本为5,且p处的启发式估计也为5)。然而,通过c1到达目标的成本估计仅为8(父节点的成本(5),加上从父节点到c1的路径成本(1),再加上c1处的启发式估计(2))。
  • 由于这个图是无向的,这个启发式在c2处也不一致,因为从c2p的路径存在与上述相同的问题。

Felner等人还提供了一些可采纳但不一致的启发式的具体例子。考虑8拼图问题:

8拼图问题

在这个拼图中,有8个编号为1-8的滑动瓷砖和一个空格。瓷砖开始时是无序的(如左图所示)。目标是通过将瓷砖滑动到空格中,使拼图达到右图所示的状态。这个问题的经典启发式(每个瓷砖到其应在位置的曼哈顿距离)是可采纳且一致的。

然而,你可以提出一个不同的启发式。也许你只想查看1、2和3到它们在目标状态中应在位置的曼哈顿距离(即相隔的方格数)。虽然这个启发式比所有瓷砖的曼哈顿距离提供的信息少,但它仍然是可采纳且一致的。

但假设你选择了另一组方块,比如5、6和7。然后假设你在每个节点计算启发式的方式是随机选择其中一组(1、2和3)或(5、6和7),并计算它们到目标位置的曼哈顿距离。这个启发式仍然是可采纳的——它只能低估或匹配到达目标状态所需的移动次数。然而,它不再是一致的——各节点的启发式估计之间没有明确的关系。

Related Posts

L1-L2正则化的不同系数

我想对网络的权重同时应用L1和L2正则化。然而,我找不…

使用scikit-learn的无监督方法将列表分类成不同组别,有没有办法?

我有一系列实例,每个实例都有一份列表,代表它所遵循的不…

f1_score metric in lightgbm

我想使用自定义指标f1_score来训练一个lgb模型…

通过相关系数矩阵进行特征选择

我在测试不同的算法时,如逻辑回归、高斯朴素贝叶斯、随机…

可以将机器学习库用于流式输入和输出吗?

已关闭。此问题需要更加聚焦。目前不接受回答。 想要改进…

在TensorFlow中,queue.dequeue_up_to()方法的用途是什么?

我对这个方法感到非常困惑,特别是当我发现这个令人费解的…

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注