我正在实现Karger算法。据我所知,最终两个节点之间的边数并不总是最小割。我遇到的问题是如何从这个算法中得到最小割。我一直在找很多关于概率的东西,但对我来说都像乱码一样...
从我所读的内容来看,我认为我需要在一个图上多次运行Karger算法。这将给我高成功概率,以达到最小割。我想是这样的?...
有人能用更简单的方式解释一下吗?我应该运行多少次这个算法?我上面说的是正确的吗?
从我所读的内容来看,我认为我需要在一个图上多次运行Karger算法。这将给我高成功概率,以达到最小割。我想是这样的?...
有人能用更简单的方式解释一下吗?我应该运行多少次这个算法?我上面说的是正确的吗?
P >= 2/(n(n-1))
。2/(n(n-1))
是最坏情况下的下限。通常情况下,该算法的表现要比这好得多。 - Björn Lindqvist