隨機最小切，Karger算法

Question

我正在實施Karger算法。據我所知，最後兩個節點之間的邊數並不總是最小割。我無法理解的是如何真正從這種算法中獲得最小的優勢。我一直在尋找很多可能性的東西，但對我來說這一切看起來都很亂...

從我讀過的內容中，我想我需要在圖上多次運行Karger算法。這會讓我很有可能擊中最低分。我認爲？...

有人可以請簡單解釋一下嗎？我如何找到運行此算法的次數？我剛纔所說的正確嗎？

Answer 1

每次運行Karger算法時，它都會給你一個（半隨機）切割。該剪輯是最小剪輯的概率是P = 1/(n^2/2 - n/2)，這比僅僅完全隨機地剪切剪輯要好得多。

如果你運行算法一次，你得到最小切割的概率是P，但你沒有得到它的概率是1 - P。如果你運行算法兩次，那麼你沒有得到最小分數的機會是(1 - P) * (1 - P)，因爲你將不得不錯過第一次和第二次分鐘。

這比較好一點。兩次運行算法使我們更有可能找到最小切割。

如果我們運行算法T次，再沒有得到最小切割的概率爲(1 - P)^T，這意味着越來越最小切割的概率爲​​。

在這一點上，你問自己多麼糟糕，你想要正確的解決方案。彌補一些概率（1,000,000？中的1）？解決T.這就是你應該運行算法的次數。

這是常見設置T = C * (n choose 2) * ln(n)，因爲這讓你不到(1/n)^C機會沒有找到最小切割，這是一個更容易的公式推理，特別是如果你設置C爲1。然後，你有一個較低的得到一個不正確的剪輯的機會比隨機選擇圖形的單個節點的機會要多。如果你的圖表很大，這很好。

總之，選擇C基於它是多麼有必要得到正確的答案。如果你不知道它有多必要，那麼C = 1是一個很好的猜測，並且只需運行你的算法(n choose 2) * ln(n)次。

（大多數這種數學是從the wikipedia page服用。你可以找到更多的細節有）