我正在实施 Karger 的算法。据我了解，最后两个节点之间的边数并不总是最小切。我难以理解的是我如何真正从这个算法中得到最小切分。我一直在寻找很多关于概率的东西，但对我来说这一切都像是胡言乱语......
根据我的阅读，我认为我需要在图表上多次运行 Karger 算法。这将使我很有可能成功击中最小切线。我认为？...
有人可以用更简单的方式解释一下吗？如何找到运行此算法的次数？我上面所说的是否正确？
问问题
1422 次
1 回答
5
每次你运行 Karger 算法时，它都会给你一个（半随机的）切割。该切割是最小切割的概率是P = 1 / (n^2/2 - n/2)，这比完全随机选择切割要好得多。
如果你运行一次算法，你得到最小切割P的概率是 ，但你没有得到它的概率是1 - P。如果你运行算法两次，那么你没有得到最小切割的机会是(1 - P) * (1 - P)，因为你必须第一次错过最小切割，第二次。
那好多了。运行该算法两次使我们找到最小割的可能性更高。
如果我们运行算法T次，那么没有得到最小切割的概率是(1 - P)^T，这意味着得到最小切割的概率是1 - (1 - P)^T。
在这一点上，你问自己你有多渴望正确的解决方案。弥补一些概率（1,000,000 分之一？），然后求解 T。这就是您应该运行算法的次数。
设置 是很常见的，因为这样你找不到最小切割T = C * (n choose 2) * ln(n)的机会更少，这是一个更容易推理的公式，特别是如果你设置为 1。那么，你得到错误切割的机会比您会随机选择图形的单个节点。如果您的图表很大，那就太好了。(1 / n)^CC
总之，C根据获得正确答案的必要性进行选择。如果您不知道它的必要性，那么这C = 1是一个很好的猜测，只需运行您的算法(n choose 2) * ln(n)时间。
（大部分数学取自维基百科页面。您可以在那里找到更多详细信息）
于 2014-05-09T04:24:50.283 回答