随机最小割，卡杰尔算法

Question

4

我正在实现Karger算法。据我所知，最终两个节点之间的边数并不总是最小割。我遇到的问题是如何从这个算法中得到最小割。我一直在找很多关于概率的东西，但对我来说都像乱码一样...

从我所读的内容来看，我认为我需要在一个图上多次运行Karger算法。这将给我高成功概率，以达到最小割。我想是这样的？...

有人能用更简单的方式解释一下吗？我应该运行多少次这个算法？我上面说的是正确的吗？

- Flyingcows00

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Stu Gla · Accepted Answer

每次运行 Karger 算法时，它将给出一个（半随机的）切割。该切割是最小切割的概率为 P = 1 / (n^2/2 - n/2)，比完全随机选择要好得多。

如果您运行算法一次，获得最小切割的概率是 P，而未获得的概率则是 1 - P。如果您运行算法两次，则未获得最小切割的概率为 (1 - P) * (1 - P)，因为您必须在第一次和第二次都错过最小切割。

这要好得多。运行算法两次使我们更有可能找到最小切割。

如果我们运行算法 T 次，则未获得最小切割的概率为 (1 - P)^T，这意味着获得最小切割的概率是 1 - (1 - P)^T。

此时，您可以考虑自己有多么需要正确的解决方案。假设某个概率（100 万分之一？），并求解 T。这就是您应该运行算法的次数。

通常将 T = C * (n choose 2) * ln(n)，因为这样可以使你找到最小割的概率小于 (1 / n)^C，这个公式更容易理解，特别是当你将 C 设为1时。然后，你得到的错误割的几率比随机选择一个节点要小。如果你的图很大，那就非常好了。

总之，根据需要获得正确答案的程度来选择 C。如果你不知道有多必要，那么 C = 1 是一个好的猜测，只需运行你的算法 (n choose 2) * ln(n) 次即可。

（大部分数学内容来自维基百科页面，你可以在那里找到更多细节。）