2

据说 Kruskal 的 MST 构造算法是贪心的，但该算法选择全局最小值，而不是像 Prim 算法那样选择局部最小值。有人可以解释一下 Kruskal 的算法是如何被认为是一种贪婪的方法吗？

4

3 回答 3

1

我们在克鲁斯卡尔做什么？首先根据它们的权重对边缘进行排序。然后我们选择权重最小的边。如果它没有循环，我们添加该边。我们就这样贪婪地前进。所以这是贪婪的方法。:)

贪心方法之所以称为贪心方法，是因为它在期望的每个阶段都进行了最优选择，这将给出一个完全最优的解决方案。

于 2014-12-24T16:58:41.077 回答
1

首先，贪婪是什么意思？

贪心算法是任何遵循问题解决启发式的算法，即在每个阶段做出局部最优选择，目的是找到全局最优。
----维基百科 https://en.wikipedia.org/wiki/Greedy_algorithm

因此，“贪心算法”是关于按顺序做出选择，使得每个单独的选择根据一些有限的“短期”标准是最好的，评估成本不会太高。

在 Kruskal 的算法中，“选择”是“挑选具有下一个最低权重的边，并且不要与已经挑选的边形成一个循环”，并且在给定排序算法和联合查找数据结构的情况下评估并不太昂贵。

您在问题中提到的局部最小值应该更多地理解为图形的当前知识，而不是相邻的顶点或边。

于 2020-03-10T04:55:03.753 回答
0

这是一个贪心算法，因为您选择根据可用的最小权重在每一步合并两组顶点，您选择了目前看起来最优的边。这是一个贪心步骤，因此该算法被称为贪心算法。

在来自维基百科的伪代码（附加）中，贪心步骤是在 的选择中(u,v)，它是连接两个未连接组件的最低加权边。

KRUSKAL(G):
1 A = ∅
2 foreach v ∈ G.V:
3   MAKE-SET(v)
4 foreach (u, v) ordered by weight(u, v), increasing:
5    if FIND-SET(u) ≠ FIND-SET(v):
6       A = A ∪ {(u, v)}
7       UNION(u, v)
8 return A
于 2014-12-24T16:55:52.467 回答