Karger のアルゴリズムを実装しています。私が理解していることから、最後の 2 つのノード間のエッジの数は必ずしも最小カットではありません。私が理解に苦しんでいるのは、このアルゴリズムから実際に最小カットを取得する方法です。私は確率に関する多くのことを見つけ続けていますが、それはすべて意味不明なように見えます...
私が読んだことから、グラフで Karger のアルゴリズムを複数回実行する必要があると思います。これにより、最小カットを達成する高い確率が得られます。おもう？...
誰かがこれをもっと簡単に説明できますか？このアルゴリズムを実行する回数を見つけるにはどうすればよいですか? 私が上で言ったことは正しいですか？
Karger のアルゴリズムを実行するたびに、(半ランダムな) カットが得られます。そのカットが最小カットである確率はP = 1 / (n^2/2 - n/2)であり、完全にランダムにカットを選択するよりもはるかに優れています。
アルゴリズムを 1 回実行すると、最小カットがP得られる確率は ですが、得られない確率は です1 - P。(1 - P) * (1 - P)アルゴリズムを 2 回実行すると、1 回目と 2 回目で最小カットを逃す必要があるため、最小カットを取得できない可能性はです。
それはかなり良いです。アルゴリズムを 2 回実行すると、最小カットを見つける可能性が高くなります。
アルゴリズムをT回数回実行すると、最小カットが得られない確率は です。(1 - P)^Tつまり、最小カットが得られる確率は です1 - (1 - P)^T。
この時点で、あなたは自分がどれだけ正しい解決策を望んでいるかを自問します。ある確率 (1,000,000 分の 1 ?) を作成し、T について解きます。これは、アルゴリズムを実行する回数です。
を設定するのが一般的です。これにより、最小カットが見つからない可能性がT = C * (n choose 2) * ln(n)低くなります。これは、特に1 に設定した場合に、推論するのがはるかに簡単な式です。グラフの単一のノードをランダムに選択します。グラフが大きい場合は、これで十分です。(1 / n)^CC
要約するCと、正しい答えを得るためにどの程度必要であるかに基づいて選択してください。それがどれほど必要なのかわからない場合C = 1は、良い推測であり、アルゴリズム(n choose 2) * ln(n)時間を実行するだけです。
(この計算の大部分はウィキペディアのページから取得したものです。詳細については、そこを参照してください)