Fly*_*s00 4 algorithm graph minimum-cut kargers-algorithm
我正在实施Karger的算法.据我所知,最后两个节点之间的边数并不总是Min Cut.我无法理解的是如何实际获得此算法的最小切割.我一直在寻找很多关于概率的东西,但这一切对我来说都是胡言乱语......
根据我的阅读,我认为我需要在图表上多次运行Karger算法.这将使我很有可能成功击中最低限度.我认为？...
有人可以用更简单的方式解释一下吗？如何查找运行此算法的次数？我上面说的甚至是正确的吗？
每次运行Karger算法时,它都会给你一个(半随机)切割.切割是最小切割的概率P = 1 / (n^2/2 - n/2),这比完全随机选择切割要好得多.
如果你运行算法一次,你获得最小切割P的可能性是,但你得到它的可能性是1 - P.如果你运行算法两次,那么你没有获得最小切割的机会是(1 - P) * (1 - P),因为你必须在第一次和第二次错过最小切割.
那要好一点.运行算法两次使我们更有可能找到最小切割.
如果我们运行算法T时间,那么没有获得最小切割(1 - P)^T的概率是,这意味着获得最小切割的概率是1 - (1 - P)^T.
在这一点上,你会问自己,你想要正确的解决方案有多糟糕.弥补一些概率(1/1,000,000？),并解决T.这是你应该运行算法的次数.
设置是很常见的T = C * (n choose 2) * ln(n),因为这样你就不会有(1 / n)^C机会找到最小切割,这是一个更容易推理的公式,特别是如果你设置C为1.那么,你获得不正确的切割的可能性要小于您可以随机选择图表的单个节点.如果您的图表很大,那就非常好.
总之,C根据获得正确答案的必要性进行选择.如果您不知道它有多必要,那么这C = 1是一个很好的猜测,只需运行您的算法(n choose 2) * ln(n)时间.
(大部分数学都来自维基百科页面.你可以在那里找到更多细节)