目前,我是人工智能的新手。我对贪婪搜索算法有一个问题。我在一个教程中看到一个问题,但无法理解如何回答它。请帮助我。任何帮助不胜感激。
考虑给定的图 1。每个节点中的值表示从该节点到目标节点（G）的启发式成本，弧内的值表示两个节点之间的路径成本。
如果 B 是起始节点，G 是目标节点，
使用贪婪搜索算法查找遍历。
使用 A * 搜索算法查找遍历
Using the result of part (1) show that greedy search is not optimal.
我假设你提到的贪婪搜索算法具有如下的贪婪选择策略：选择与当前节点相邻并且与当前节点的成本 / 距离最小的下一个节点。请注意，贪婪解决方案根本不使用启发式成本。
Consider the following figure well crafted such that it proves that greedy solution is not optimal.
用红色突出显示的路径显示贪婪算法采用的路径，用绿色突出显示的路径显示启发式 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
通过上面的例子，我们可以看到启发式路径的成本小于贪婪算法。因此贪婪算法并不总是最优的。
本站系公益性非盈利分享网址，本文来自用户投稿，不代表边看边学立场，如若转载，请注明出处
评论列表（32条）