algorithm - 随机最小割，Karger 算法

Question

我正在实现 Karger 算法。据我了解，最后两个节点之间的边数并不总是 Min Cut。我无法理解的是我实际上如何从该算法中获得最小切割。我一直在寻找很多关于概率的东西，但对我来说它们看起来都是胡言乱语......

根据我所阅读的内容，我认为我需要在一张图上多次运行 Karger 算法。这将使我很有可能成功达到最低限度。我想？...

有人可以用更简单的方式解释一下吗？我如何找到运行此算法的次数？我上面说的对吗？

Answer 1

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

如果你运行该算法一次，你得到最小割的概率是 P，但你没有得到它的概率是 1 - P。如果你运行该算法两次，那么你没有得到最小切割的机会是 (1 - P) * (1 - P)，因为你必须第一次错过最小切割，并且第二次。

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

如果我们运行算法 T 次，那么没有得到 min cut 的概率是 (1 - P)^T，这意味着得到的概率最小切割是 1 - (1 - P)^T。

在这一点上，您问自己您多么想要正确的解决方案。弥补一些概率(1,000,000 分之一？)，并求解 T。这就是您应该运行该算法的次数。

设置 T = C * (n choose 2) * ln(n) 很常见，因为这给你的小于 (1/n)^C找不到最小切割的机会，这是一个更容易推理的公式，尤其是当您将 C 设置为 1 时。这样，与随机切割相比，您获得错误切割的可能性更低选择图形的单个节点。如果您的图表很大，那就太好了。

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

(大部分数学运算取自 the wikipedia page。您可以在那里找到更多详细信息)