Did*_*344 5 greedy graph-algorithm
如果 Kruskal 算法贪婪，为什么它会找到最小生成树？最小生成树不是全局优化问题吗？贪婪的意义不是在于您有可能找不到最佳解决方案吗？那么 Kruskal 如何能够在贪婪的同时找到最小生成树呢？
小智 6
好的，让我们假设您是对的，因此 Kruskal 的算法没有找到最佳解决方案。让 Kruskal 算法找到解决方案S，并找到最佳解决方案T。
必须有一个边e = (u, v)出现在S但不在 上T。就像T生成树一样， nodeu和 node之间必须有一条路径v。
现在，我们应该注意到路径上至少有一条边的u-v权重不小于e。否则，克鲁斯卡尔的算法将选择路径上的所有边u-v而不是边e。
这意味着，如果我们删除该边并添加e解决方案T，则解决方案不会变得更糟。正如我们假设的那样T是最优的，在这个改变之后，树仍然是最优的。如果我们反复应用这个逻辑，我们总是可以使S.
| 归档时间： |
|
| 查看次数： |
3324 次 |
| 最近记录： |