この問題があります。私は、残りの辺の数が最大になる（または切断される辺の数を最小限に抑える）という制約の下で、xノードとn-xノードの2つのサブグラフに分割したいn個のノードのグラフを持っています。グラフ理論：グラフを分割する
それが理にかなっているかどうかわかりません。グラフ理論者ではありませんが、これは私の問題の抽象版です。それをどのように見なければならないのでしょうか？
これは宿題の問題ではありません。私は思うけど興味深い問題！
私はCで実装する予定です。
x = n - xを最小二等分問題といい、NP困難な特殊ケースです。これはあなたの問題をNP困難にもします。局所探索（例えば、ランダムカットから開始し、カットのサイズを減少させる繰り返しの頂点のペア）およびスペクトル法（例えば、第2の固有ベクトルを計算し、閾値化する）を含む、ウィキペディアの記事graph partitioningに記載されているいくつかの発見的方法がある。 。 nが小さい場合、整数プログラミングも可能です。
これは答えです。 –
Yikes。おそらく、コンピュータ以外の科学者にとってはあまりにも進歩しています。 xが小さければ遺伝的アルゴリズムを使用する方が良いでしょうか？ランダムなx = 10の集合を取って、グラフがちょうど2つの部分に分割されている場合は、最小カットの点で上位10％をとり、それらを一連の世代に突き合わせます。効果があると思いますか？あるいは、それはデータセットに完全に依存していますか？私はそれを試してみるかもしれないと思います。 – JoshDG
ローカル検索は簡単に実装することができます。ちょうどカットから始め、小さな変更を加えることで改善してみましょう。固有ベクトルの計算はそれほど悪くはありませんが、数学の知識が必要です。整数プログラミングは難しいですが、無料のライブラリがあります。私はコンビナトリアル問題の遺伝的アルゴリズムが好きではありませんが、あなたがそれらに十分なサイクルを送りたいならば、ローカル検索よりも良いかもしれません。 – uty
多分、ノード上の深さの最初の検索。一度にノードを1つずつ割り当て、今までのカット数を数えます。その数が最適解の数を超えている場合は、これを打ち切ってバックトラックします。ノードSのフルセットが与えられると
をしましょうProlog型のアルゴリズムとして、Cでそれを行うことはそれほど難しくありません。バックトラックとは、最後に割り当てられたノードの割り当てを解除することを意味します。
基本的には、min-cut問題の修正版があります。
片方の修正がありますkarger's algorythm Karger's algoでは、2つの頂点で終わるまで、ランダムな辺に沿って頂点を縮小します。残りの辺はカットを表します。ランダムなので、これを何度もやって、カット内の最小限のエッジでソリューションを維持してください。
修正されたバージョンでは、頂点がx回折り畳まれたら、折り畳みを止めて出て行くエッジをカウントすることができます（これらはあなたのケースのカットになります）。問題を解決するために、計算を何度繰り返して満足度を上げるかを計算することです。
ミニカットの問題は、固定された 'x' [カットの片側にある頂点の数]がなく、特定の' source'と 'sink'を持っています。 min-cutの問題を軽減するには、答えに追加してください。 – amit
私はKarger'sにいくつかの種類の変更がこの問題を解決できると思います。 min cut問題自体にシンクとソースはありません。それは、いくつかのalgorythmsが問題を最大フローに減らすということだけです。固定されたxケースを扱うkargerの良い修正を思いつくことができれば答えを編集します（ある明確な方法がありますが、正しい結果が得られるかどうかは分かりません） – AntonioD
xはパラメータですか、2つのサブグラフだけを探していますか？ xがパラメータでない場合は、エッジ数が最も少ないノードを探し、グラフから切り捨てますか？ – brianestey
はい。申し訳ありませんが、私はそれをより明確にすべきでした。 xが10で、ノードの総数が25であるとします。私は2つのグラフを必要とします.1つは10ノード、もう1つは15 ...エッジの最小数を「切断」します。 – JoshDG
間違いなく面白い問題。実際、単一のノードを探すことについて私の最初の仮定は間違っています - 私はそれが真ではないグラフを考え出しました。解決策を見つけることを幸運！ – brianestey