时间戳

首页 > 解决方案 > 贪心搜索算法

artificial-intelligence - 贪心搜索算法

问题描述

目前，我是人工智能的新手。我对贪心搜索算法有疑问。我在教程中看到一个问题，但不明白如何回答。请帮我。非常感谢任何帮助。

考虑给定的图 1。每个节点中的值表示从该节点到目标节点 (G) 的启发式成本，弧内的值表示两个节点之间的路径成本。

  1. 如果 B 是起始节点，G 是目标节点，
  • 使用贪心搜索算法找到遍历。
  • 使用 A* 搜索算法找到遍历
  1. 使用第（1）部分的结果表明贪婪搜索不是最优的。 在此处输入图像描述

标签： artificial-intelligence

解决方案

我假设您所指的贪心搜索算法具有如下贪心选择策略：选择与当前节点相邻且与当前节点的成本/距离最小的下一个节点。请注意，贪心解决方案根本不使用启发式成本。

考虑以下精心制作的图，它证明贪婪解决方案不是最优的。 在此处输入图像描述

以红色突出显示的路径表示贪心算法采用的路径，以绿色突出显示的路径表示启发式 A* 算法采用的路径。

解释：

贪心算法

  • 从节点 B 开始，贪心算法看到路径成本（A 为 6，C 为 6，E 为 5）
  • 我们贪婪地移动到节点 E，因为它的路径值最小。
  • 从 E 我们只有一个选择可以移动到 F
  • 从 F 我们再次只有一个选项可以移动到 H 并且从 H 我们移动到 G（目标状态/节点）

贪婪算法的路径成本（以红色突出显示）：B -> E -> F -> H -> G= 5+6+6+3=20

A* 算法（在继续之前查看 A* 算法的wiki页面，如果您还没有理解这个概念，请了解什么g(n)和是什么）：h(n)

  • 从节点 B 开始，我们有三个选项 A、C 和 E。对于我们计算的每个节点f(n) = g(n) + h(n)。这里 g(n) 是弧上的直接成本，h(n)是节点上的启发式值
    • 对于节点 A，f(n) = 6 + 12 = 18
    • 对于节点 B，f(n) = 6 + 10 = 16
    • 对于节点 C，f(n) = 5 + 14 = 19
  • 我们选择继续处理具有最少 的节点f(n)。所以我们移动到节点 B。
  • 我们以类似的方式继续，找到以绿色突出显示的路径。
  • A*算法的路径是B -> C -> D -> H -> G，它的成本是6+6+4+3=19

通过上面的例子我们可以看到启发式路径的成本低于贪心算法。因此贪心算法并不总是最优的。

推荐阅读