完全な答えではありません。それがあなたにとってどれほど役立つかわかりません。しかし、ここに行きます：
ハミング距離は私を赤ニシンのように襲います。あなたの問題文は、それが少なくとも1でなければならないと言いますが、1000になる可能性があります。各ノードのセットメンバーシップのビットエンコーディングは一意であると言えば十分です。
問題のステートメントはそれを詳しく説明していませんが、上記の解決策は、すべてのノードが少なくとも 1 つのセットのメンバーである必要があることを示唆しています。すなわち。すべての 0 のビット エンコーディングは、どのノードのセット メンバーシップにも許可されていません。
接続されたノードをしばらく無視すると、バラバラのノードは簡単です。未使用のビット エンコーディングを使用して順番に番号を付けるだけです。それらを最後に保存します。
上記の例では有向エッジを使用していますが、繰り返しになりますが、それは赤いニシンとして私を襲います。A=>D という理由で A が D と同じセットに含まれない場合、D=>A であるかどうかに関係なく、D は A と同じセットに含まれません。
少なくとも log(N) セットが必要であると述べています。また、最大で N 個のセットがあります。全結合グラフ ((N^2-N)/2 個の無向辺を持つ) には、それぞれが単一のノードを含む N セットが必要です。
実際、グラフに M+1 個の頂点と (M^2+M)/2 個の無向辺を持つ M 次元 (M in 1..N-1) の全結合シンプレックスが含まれている場合、少なくとも M+1 が必要になります。セット。
上記の例では、2 つの頂点 {A,D} と 1 つの (無向) エッジ {(A,D)} を持つシンプレックス (M=1) が 1 つあります。
あなたの問題は、グラフ内の最大の完全に接続されたシンプレックスを見つけることに要約されるようです。別の言い方をすれば、ルーティングの問題があります。交差しないようにエッジをルーティングするには、いくつの次元が必要ですか? 非常にスケーラブルな問題のようには思えません。
最初に見つけられる大きなシンプレックスは簡単です。すべての頂点ノードは、独自のビットを持つ新しいセットを取得します。
ばらばらのノードは簡単です。接続されたノードが処理されたら、以前に使用されたビット パターンをスキップして、互いに素なノードに順番に番号を付けます。上記の例から、A と D は 01 と 10 を受け取るため、B で次に使用できるビット パターンは 11 です。
難しい部分は、新しいビットで新しいセットを作成する前に、残りのシンプレックスを可能な限り既存の範囲に折り畳む方法です。フォールディングでは、各ノードに 2 つ以上のビット (セット) を使用する必要があり、ビット (セット) は隣接するノードのビット (セット) と交差してはなりません。
上記の例に別のノード C を追加するとどうなるかを考えてみましょう。
C が A と D の両方に直接接続する場合、最初の問題は、3 つの頂点 {A,C,D} と 3 つのエッジ {(A,c),(A,D),(C,D) を持つ 2-シンプレックスを見つけることになります。 )}。A、C、および D がビット パターン 001、010、および 100 を取得すると、互いに素な B で使用可能な最小のビット パターンは 011 になります。
一方、C が A または D を直接接続し、両方を接続しない場合、グラフには 2 つの 1-シンプレックスがあります。最初にビット パターン 01 と 10 を与える頂点 {A,D} を持つ 1-シンプレックスを見つけたと仮定すると、問題は C をその範囲に折り畳む方法になります。少なくとも 2 ビットのビット パターンは 11 だけですが、これは C が接続するノードと交差するため、新しいセットを作成して C を入れる必要があります。この時点で、ソリューションは上記のものと似ています。
C が互いに素である場合、B または C のいずれかがビット パターン 11 を取得し、残りの 1 つは新しいセットを必要とし、ビット パターン 100 を取得します。
C が B に接続されているが、A または D には接続されていないとします。この場合も、グラフには 2 つの 1-シンプレックスがありますが、今回はバラバラです。上記のように {A,D} が最初に検出され、A と D にビット パターン 10 と 01 が与えられたとします。B または C を既存の範囲に折りたたむことができます。範囲内で使用可能な唯一のビット パターンは 11 であり、どちらも A または D に隣接していないため、B または C のいずれかがそのパターンを取得できます。11 が使用されると、2 つ以上のビットが設定されたビット パターンは残りません。残りのノードにビット パターン 100 を与える新しいセット。
C が 3 つの A、B、D のすべてに接続しているとします。この場合、グラフには 3 つの頂点 {A,C,D} を持つ 2-シンプレックスと 2 つの頂点 {B, C} を持つ 1-シンプレックスがあります。上記のように処理を進めると、最大のシンプレックスを処理した後、A、C、および D のビット パターンは 001、010、100 になります。 111. 101 を除くこれらすべてが C と交差するため、B はビット パターン 101 を取得します。
問題は次のようになります:最大の全結合シンプレックスをどれだけ効率的に見つけることができるでしょうか?
最大の全結合シンプレックスを見つけるのにコストがかかりすぎる場合は、接続に関して最大最小値を見つけることにより、潜在的な全結合シンプレックスに近似の上限を設定できます。
エッジをスイープし、接続エッジの数で頂点を更新します。
接続されたノードごとに、最初はゼロの Cn カウントの配列を作成します。ここで、Cn はノード n に接続されたエッジのカウントです。
接続されたノード n1 と n2 のエッジを再度スイープし、Cn2 に対応する n1 のカウントをインクリメントします。逆も同様です。Cn2 > Cn1 の場合、n1 配列の最後のカウントを更新し、その逆も同様です。
接続されたノードを再度スイープし、各ノードが属する最大のシンプレックスの上限を計算します。ノードをスイープするときに、各上限の頂点のリストを使用して鳩の穴配列を作成できます。
ピジョン ホール アレイを最大から最小まで処理して、ノードを抽出し、一意のセットに折りたたみます。
ノードがセット N にあり、エッジがセット E にある場合、複雑さは O(|N|+|E|+O(Step 5)) になります。
上記の概算で十分な場合、問題は次のようになります:要件が与えられた場合、どの程度効率的にノードを既存の範囲に折りたたむことができますか?