問題タブ [kargers-algorithm]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
algorithm - ランダム化された最小カット、Karger のアルゴリズム
Karger のアルゴリズムを実装しています。私が理解していることから、最後の 2 つのノード間のエッジの数は必ずしも最小カットではありません。私が理解に苦しんでいるのは、このアルゴリズムから実際に最小カットを取得する方法です。私は確率に関する多くのことを見つけ続けていますが、それはすべて意味不明なように見えます...
私が読んだことから、グラフで Karger のアルゴリズムを複数回実行する必要があると思います。これにより、最小カットを達成する高い確率が得られます。おもう？...
誰かがこれをもっと簡単に説明できますか？このアルゴリズムを実行する回数を見つけるにはどうすればよいですか? 私が上で言ったことは正しいですか？
python - Karger の最小カット アルゴリズム
カーガーの最小カットアルゴリズムをPythonで実装している間、私は出力を次のように取得しています
これは最小カットが 5 であることを意味しますか? 次のコードを使用しています。
Python で Karger のアルゴリズムを学習しようとしていますが、これが正しいかどうかはわかりません。
python - グラフの最小カットのランダム化された収縮アルゴリズム
最小カット問題を解決するための Karger のアルゴリズムの実装を作成しようとしました。これが私のコードです
コメントはありませんが、一目瞭然です。「g」は、キーがグラフの頂点であり、それぞれが接続されている頂点の値を持つ辞書です。randomVertices は縮小したいエッジを与え、mergeVertices は 2 番目の頂点を削除し、この頂点にリンクされたキーの値を更新し、自己ループを取り除くことによって辞書 (したがってグラフ) を更新します。私には問題ないように見えますが、テストグラフで実行すると、その段階で KeyError が発生し、l = g[x]なぜこれが起こっているのか理解できません。あなたの何人かが私を助けることができることを望んでいました。ありがとう。
編集:私のコードは実際には問題ありません。エラーは、隣接するリストでファイルをロードした方法にありました。Cobarzan、私が実際にエッジを一様に選んでいないことを指摘してくれてありがとう.
algorithm - Karger のアルゴリズム 有向グラフの最小カット
カーガーのアルゴリズムが無向グラフでどのように機能するかのロジックを理解するのに苦労しています。Ford-Fulkersson アルゴリズムなどの max-flow アルゴリズムがあることは知っていますが、無向グラフでこのアルゴリズムを使用した後ではありません。
Karger のアルゴリズムを有向グラフで使用する場合と Karger のアルゴリズムを無向グラフで使用する場合の違いを誰かが説明できますか。
前もって感謝します！