17

この問題があります。残りのエッジの数が最大化される (またはカットされるエッジの数が最小化される) という制約に従って、x ノードと nx ノードの 2 つのサブグラフに分割したい n ノードのグラフがあります。

それが理にかなっているのかどうかはわかりません。グラフ理論の人ではありませんが、これは私の問題の抽象的なバージョンです。役立つ可能性のあるアルゴリズムは何ですか?

これは宿題の問題ではありません。面白い問題だと思います！

Cで実装する予定です。

4

3 に答える 3

11

The special case where x = n - x is called the minimum bisection problem and is NP-hard. This makes your problem NP-hard as well. There are several heuristics described in the Wikipedia article on graph partitioning, including local search (e.g., start with a random cut and repeatedly swap pairs of vertices that decrease the size of the cut) and spectral methods (e.g., compute and threshold the second eigenvector). If n is small, integer programming is also a possibility.

于 2012-04-17T12:42:38.797 に答える
2

おそらく、ノードに対する深さ優先検索です。ノードを 1 つずつ割り当て、それまでのカット数をカウントします。その数が最適なソリューションの数を超える場合、このソリューションを中止してバックトラックします。

  1. ノード S の完全なセットが与えられた場合、P と P' をノードの集合 (最初は空) とし、K をカット エッジの数 (最初は 0) とします。
  2. S*、K* を既知の最適解とその切り口の数とし、K* は最初は無限大です。
  3. ノード N を選択して開始し、それを S に割り当てます。
  4. 割り当てられていないノード M ごとに:
    1. M を S' に割り当て、M から S から K のノードにエッジの数を追加します。
    2. K > K* の場合、これに基づく解は最善のものを打ち負かすことができないため、M を S に割り当てます。
    3. |S|の場合 > X の場合、セットが大きくなりすぎています。バックトラック。
    4. それ以外の場合は、4 から再帰します。
  5. すべてのノードが割り当てられ、K < K* の場合、S* = S および K* = K とします。

私はこれを Prolog タイプのアルゴリズムとして想像してきましたが、C でそれを行うのはそれほど難しいことではありません。バックトラックとは、最後に割り当てられたノードの割り当てを解除することを意味します。

于 2012-04-17T06:08:15.867 に答える
0

基本的に、最小カット問題の修正版を見ています。

1 つの方法は、karger のアルゴリズムを変更することです。 Karger のアルゴリズム では、最終的に頂点が 2 つになるまで、ランダムなエッジに沿って頂点を収縮させます。残りのエッジはカットを表します。ランダムなので、これを何度も行い、カット内のエッジが最も少ないソリューションを維持します。

変更されたバージョンでは、頂点が x 回折りたたまれたら、折りたたみを停止して外向きのエッジをカウントし (これらはあなたのケースではカットになります)、適切な回数だけ実行すると、解決策が得られます。トリッキーな部分は、信頼性を満足のいく限界まで高めるために計算を何回繰り返すかを考え出すことです

于 2012-04-17T06:56:57.873 に答える