N 個のペアが与えられます。各ペアには 2 つの数値が含まれます。与えられた N 個のペアから J (1<=J<=K) 個のペアを組み合わせた場合、選択されたすべての J 個のペアに少なくとも J 個の異なる数があるように、最大数 K を見つける必要があります。同じペアを複数持つことができます。
たとえば、ペア (1,2) (1,2) (1,2) (7,8) (9,10) を考えます。この場合、K = 2 です。K > 2 の場合、 (1,2) の場合、1 と 2 の 2 つの異なる数しかありません。
可能な組み合わせを 1 つずつチェックすると、非常に時間がかかります。問題を解決するための効率的なアルゴリズムは何でしょうか?
MinCut/MaxFlowに関連しているようです。これをMinCut/MaxFlowに減らす試みは次のとおりです。
- Produce one vertex for each number
- Produce one vertex for each pair
- Produce an edge from number i to a pair if the number is present in the pair, weight 1
- Produce a source node and connect it to all numbers, weight 1 for each connection
- Produce a sink node and connect it to all numbers, weight 1 for each connection
これでMaxFlowを実行すると、番号が得られます。これはK、合計2つの番号のみを含む3つのペアのセットは、番号からの出力エッジの制約によって「ブロック」されるためです。
これが最速の解決策かどうかはわかりません。どこかにマトロイドが隠れているかもしれないと思います。その場合、貪欲なアプローチがあります。しかし、私はあなたが構築しているセットのマトロイド特性の証拠を見つけることができません。
これは、グラフ内の最小のサイクルを和音で結ぶ和音を見つけることに相当します。非常に単純なアルゴリズムは次のようになります。
エッジを削除すると、エッジに対応する頂点を含むサイクルが生じるかどうかを確認します。はいの場合、最小サイクルの長さを書き留めます。
私はそれについてある程度の進歩を遂げましたが、まだ効率的な解決策ではありません。しかし、それは道を示すかもしれません。
ポイントがペアであるグラフを作成し、それらが数を共有する場合、ポイントのペアを接続します。次に、サブグラフの場合、その中の数値の数は、頂点の数からエッジの数を引いたものです。したがって、問題は、頂点よりも多くのエッジを持つ最小のサブグラフ (存在する場合) を見つけることと同じです。
辺と頂点の数が同じ最小サブグラフは、サイクルです。したがって、探しているグラフは、1 つ以上の頂点を共有する 2 つのサイクル、またはパスで接続された 2 つのサイクルのいずれかです。可能な最小型は他にありません。
幅優先検索を使用すると、かなり簡単にサイクルを見つけて列挙することができます。それらはたくさんあるかもしれませんが、これは実行可能です。これらのサブタイプのサブグラフを探すことができます。(最小のサイクルを列挙し、ポイントを共有するペアまたは接続されているペアを探します。) しかし、それが多項式であるとは限りません。平均的にはかなり良いものになると思いますが、最悪の場合は非常に悪い. しかし、それはあなたが今していることよりも効率的かもしれません。
私は、ある種の幅優先探索が多項式時間でこれらを見つけることができると考え続けていますが、それを行う方法を正確に理解できていません。
数値ごとに頂点を 1 つ、ペアごとにエッジを 1 つ持つグラフを作成します。
このグラフがチェーンまたはツリーの場合、「ペア」の数に 1 を加えた数の「数」があります。このグラフから任意の数のエッジを削除した後、頂点がエッジより少なくなることはありません。
このチェーン/ツリーに 1 つのサイクルを追加します。頂点と辺の数は同じです。このグラフから任意の数のエッジを削除した後でも、頂点がエッジより少なくなることはありません。
次に、切断されたコンポーネントをいくつでも追加します。それぞれに複数のサイクルが含まれないようにしてください。繰り返しになりますが、任意の数のエッジを削除した後、エッジより頂点が少なくなることはありません。
次に、切断されたコンポーネントのいずれかに 2 番目のサイクルを追加します。他のすべてのコンポーネントを取り外した後。ついに、頂点よりも多くのエッジができました (数よりも多くのペア)。
これらすべては、K+1 が、2 つのサイクルと、おそらくこれらのサイクルを接続するチェーンで構成される、可能な限り最小のサブグラフのエッジの数であるという結論につながります。
接続されたコンポーネントごとに、Floyd-Warshall アルゴリズムを使用して、すべてのノードを通過する最短サイクルを見つけます。
次に、(単一コンポーネント内の) サイクルの重複しないペアごとに、ダイクストラのアルゴリズムを使用して、1 つのサイクルに少なくとも 3 つのエッジを持つ任意のノードから開始し、他のサイクルへの最短パスを見つけます。両方のサイクルの長さの合計と、それらを接続する最短パスを計算します。重複するサイクルのペアごとに、それらのエッジの数を計算するだけです。
これらすべてのサブグラフの最小の長さを見つけます。そして1を引きます。
上記のアルゴリズムは、グラフに少なくとも 1 つのダブル サイクル コンポーネントがある場合に K を計算します。そのようなコンポーネントがない場合、K = N です。