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

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

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


回答:

正如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

使用LSTM在Python中预测未来值

这段代码可以预测指定股票的当前日期之前的值,但不能预测…

如何在gensim的word2vec模型中查找双词组的相似性

我有一个word2vec模型,假设我使用的是googl…

dask_xgboost.predict 可以工作但无法显示 – 数据必须是一维的

我试图使用 XGBoost 创建模型。 看起来我成功地…

ML Tuning – Cross Validation in Spark

我在https://spark.apache.org/…

如何在React JS中使用fetch从REST API获取预测

我正在开发一个应用程序,其中Flask REST AP…

如何分析ML.NET中多类分类预测得分数组?

我在ML.NET中创建了一个多类分类项目。该项目可以对…

发表回复

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