27

在树中搜索时，我对统一成本搜索的理解是，对于给定的节点 A，其子节点 B、C、D 的相关成本为 (10, 5, 7)，我的算法将选择 C，因为它有更低的花费。展开 C 后，我看到节点 E、F、G 的成本为 (40, 50, 60)。它将选择 40，因为它具有两个 3 中的最小值。

现在，这不就像贪婪搜索一样，你总是选择看起来最好的动作吗？

此外，在定义从某些节点到其他节点的成本时，我们应该考虑从树的开头到当前节点的全部成本，还是只考虑从节点 n 到节点 n' 的成本本身？

谢谢

4

4 回答 4

39

没有。你的理解不太对。

在统一成本搜索的情况下要访问的下一个节点将是 D，因为它具有从根开始的最低总成本（7，而不是 40+5=45）。

贪婪搜索不会返回树 - 它选择最低值并承诺。Uniform-Cost 将从整个树中选择最低的总成本。

于 2010-01-17T20:45:52.627 回答
8

在统一成本搜索中，您始终考虑到目前为止您看到的所有未访问的节点，而不仅仅是那些连接到您查看的节点的节点。因此，在您的示例中，选择 C ​​后，您会发现访问 G 的总成本为 40 + 5 = 45，这高于从根重新开始访问 D 的成本，后者的成本为 7。所以您将访问下一个 D。

于 2010-01-17T20:46:17.040 回答
7

它们之间的区别在于，Greedy 选择具有最低启发值的节点，而 UCS 选择具有最低动作成本的节点。考虑下图：

如果你同时运行这两种算法，你会得到：

  • 统一通信系统

选择：S（成本 0）、B（成本 1）、A（成本 2）、D（成本 3）、C（成本 5）、G（成本 7）

答案：S->A->D->G

  • 贪婪的：

*假设它选择A而不是B；A 和 B 具有相同的启发式值

选择：S、A (h = 3)、C (h = 1)、G (h = 0)

答案：S->A->C->G

因此，根据对问题定义的理解，将到达节点的操作成本与启发式值区分开来很重要，启发式值是添加到节点的一条信息。

于 2012-10-13T23:46:20.147 回答
0

贪婪搜索（对于这个答案的大部分内容，当我说贪婪搜索时，请考虑贪婪的最佳优先搜索）是一种知情搜索算法，这意味着被评估以选择要扩展的节点的函数具有 f(n) = h(n)，其中 h 是给定节点 n 的启发式函数，它将从该节点 n 返回到目标状态的估计值。如果您尝试前往某个地方，启发式函数的一个示例是返回从节点 n 到您的目的地的估计距离。

另一方面，统一成本搜索是一种不知情的搜索算法，也称为盲搜索策略。这意味着对于给定节点 n 的函数 f 的值 f(n)，对于不知情的搜索算法，考虑了 g(n)，即从根节点到节点 n的总动作成本，即路径成本。除了问题描述之外，它没有关于问题的任何信息，所以它只能知道这些。您没有任何信息可以帮助您确定一个节点与目标状态的接近程度，只有根节点。您可以在此处观看节点扩展（统一成本算法的动画），并了解如何使用从节点 n 到根的成本来选择要扩展的节点。

贪心搜索，就像任何贪心算法一样，采用局部最优解，并使用一个函数将给定节点 n 的估计值返回到目标状态。您可以在此处观看节点扩展（Greedy Best First Search | Quick Explanation with Visualization），并查看启发式函数从节点 n 到目标状态的返回如何用于选择要扩展的节点。

顺便说一句，有时，贪心搜索选择的路径不是全局最优的。例如，在视频中的示例中，节点 A 永远不会扩展，因为始终存在具有较小 h(n) 值的节点。但是，如果 A 具有如此高的值，而下一个节点的值非常小，因此是全局最优值怎么办？这可能会发生。一个糟糕的启发式函数可能会导致这种情况。陷入循环也是可能的。A* 也是一种贪心搜索算法，它通过利用路径成本（这意味着知道已经访问过的节点）和启发式函数来解决这个问题，即 f(n) = g(n) + h(n ）。

到目前为止，您可能仍然不清楚统一成本如何知道还有另一条在本地看起来更好但在全球范围内看起来更好的路径。告诉你如果所有路径都具有相同的成本，那么统一成本搜索与广度优先搜索（BFS）是一样的，应该会很清楚。它将像 BFS 一样扩展所有节点。

于 2022-02-07T23:07:10.380 回答