組み合わせた独立したセット/ハミング距離のアルゴリズム/近似

Question

入力：グラフG出力：いくつかの独立したセット。すべての独立したセットへのノードのメンバーシップが一意になるようにします。したがって、ノードには、独自のセットのノードへの接続がありません。これがパスの例です。

ここでは別のrephrasalに明確化が呼ばれたため：

特定のグラフをセットに分割して、

1. セットIがセットにのみ存在する場合、セットのメンバーシップによって他のすべてのノードを伝えることができます。

   セットAとBにノードjが存在する場合、セットAとBのみに他のノードが存在する必要はありません。ノードのメンバーシップがビットパターンでコーディングされている場合、これらのビットパターンには少なくとも1つの距離があります

2. グラフに2つのノードが隣接している場合、それらは同じセットに存在しないでください。したがって、独立したセットになります

例：bには隣接するノードがありませんd => a、a => d

解決：

1. ab /
2. / bd

Aにはビットパターン10があり、セットに隣接するノードはありません。 Bにはビットパターン11があり、隣接するノードはありません。Dには01しているため、すべてのノードにはハミング距離が少なくとも1に隣接するノードなし=>正しい

dとaが接続されているため、間違っています：

1. ADB
2. / db

Aは、セットにビットパターン10とDがあり、それらは隣接しています。 Bにはビットパターン11があり、隣接するノードはありません。DにはBが11にあるため、このソリューションには2つのエラーがあるため、受け入れられません。

もちろん、少なくとも必要なので、グラフ内のノードの数が増加するにつれて、これはより多くのセットに拡張する必要があります log(n) セット。

私はすでにMAX-SATへの変換を書き、これにsat-solverを使用しました。しかし、条項の数はただ大きいだけです。より直接的なアプローチがいいでしょう。これまでのところ、近似がありますが、正確な解決策または少なくともより良い近似が必要です。

粒子群を使用して、任意のソリューションからより良いソリューションに向けて最適化するアプローチを試しました。しかし、実行時間はかなりひどく、結果は素晴らしいとはほど遠いものです。私は動的なアルゴリズムか何かを探していますが、この問題を分割して征服する方法を推測することはできません。

Answer 1

完全な答えではなく、それがあなたにとってどれほど有用であるかはわかりません。しかし、ここにあります：

ハミング距離は私を赤いニシンとして襲います。問題の声明は、少なくとも1でなければならないが、1000である可能性があると述べています。各ノードのセットメンバーシップのビットエンコードは一意であると言うだけで十分です。

問題のステートメントはそれを綴りませんが、上記のソリューションは、すべてのノードが少なくとも1セットのメンバーでなければならないことを示唆しています。すなわち。すべての0のエンコードは、ノードのセットメンバーシップでは許可されていません。

接続されたノードをしばらく無視すると、分離ノードは簡単です。未使用のビットエンコードで順番に番号を付けます。最後にそれらを保存します。

上記の例では、監督されたエッジを使用していますが、再び、それは私を赤いニシンとして襲います。 a => dであるため、aがdと同じセットにできない場合、dはd => aであるかどうかに関係なく、aと同じセットにすることはできません。

少なくともログ（n）セットが必要であることに言及します。また、せいぜいNセットもあります。完全に接続されたグラフ（（n^2-n）/2無向エッジ）には、単一のノードを含むNセットが必要です。

実際、グラフにM+1の頂点を持つ完全に接続されたM寸法（1..n-1のm）と（m^2+m）/2の無向エッジが含まれている場合、少なくとも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を取得すると、Disjoint Bで利用可能な最低ビットパターンは011です。

一方、Cが両方ではなく直接AまたはDを接続する場合、グラフには2つの1シンプレックスがあります。頂点{a、d}のある1シンプルが最初にビットパターン01と10を与えるとしたら、問題はCをその範囲に折りたたむ方法になります。少なくとも2ビットの唯一のビットパターンは11ですが、ノードCが接続するノードCと交差するため、新しいセットを作成してCを入れなければなりません。この時点で、ソリューションは上記のものに似ています。

Cの場合、BまたはCのいずれかがビットパターン11を取得し、残りのパターンには新しいセットが必要になり、ビットパターン100が取得されます。

CがBに接続しますが、AまたはDには接続しないと仮定します。繰り返しますが、グラフには2つの1シンプレックスがありますが、今回はばらばらです。 {a、d}が上記のように最初に見つかったと仮定します。AおよびDビットパターン10および01を与えます。BまたはCを既存の範囲に折ります。範囲の唯一の利用可能なビットパターンは11で、BまたはCのいずれかがAまたはDに隣接していないため、そのパターンを取得できます。残りのノードの新しいセットは、ビットパターン100を提供します。

Cが3 A、B、およびDすべてに接続するとします。この場合、グラフには3つのvertexes {a、c、d}を備えた2シンプレックスと2つのvertexes {b、c}を持つ1シンプレックスがあります。上記のように進み、最大のシンプレックスを処理した後、A、C、およびDにはビットパターン001、010、100があります。この範囲にBを折り畳むと、2ビット以上の使用可能なビットパターンは：011、101、110、および111.これらはすべて、101を除くすべてがCと交差するため、ビットパターン101を取得します。

質問は次のようになります。 最大の完全に接続されたシンプレックスをどの程度効率的に見つけることができますか？

最大の完全に接続されたシンプレックスを見つけることが高すぎる場合, 、接続の観点から最大の最小値を見つけることにより、潜在的な完全に接続されたシンプレックスに近い上限を置くことができます。

1. エッジをスイープして、接続エッジのカウントで頂点を更新します。

2. 接続されたノードごとに、最初にCNカウントの配列を作成します。ここで、CNはノードnに接続されたエッジのカウントです。

3. 接続されたノードN1とN2の場合、エッジを再度スイープして、CN2に対応するN1のカウントを増やし、その逆も同様です。 CN2> CN1の場合、N1アレイの最後のカウントを更新し、その逆も同様です。

4. 接続されたノードを再度スイープして、各ノードが一部になる可能性がある最大のシンプレックスの上限を計算します。ノードをスイープするときに、上限ごとに頂点のリストを使用して、ピジョンホールアレイを構築できます。

5. 最大から最小の抽出、折りたたみノードを一意のセットに折りたたみ、最小のアレイに操作します。

ノードがセットnに、エッジが設定されている場合、複雑さは次のとおりです。

上記の近似で十分な場合、質問は次のようになります。 要件を考慮して、既存の範囲にノードをどれだけ効率的に折りたたむことができますか？

Answer 2

これはあなたが期待するかもしれない答えではないかもしれませんが、私はコメントを追加する場所を見つけることができません。ここで直接入力します。私はあなたの質問を完全に理解することができません。それとも、理解するために特定の知識が必要ですか？この独立したセットは何ですか？私が知っているように、指示されたグラフから独立したセットのノードには、このセットの他のノードへの双方向パスがあります。あなたの概念は同じですか？

この問題が私が想定しているもののような場合、このアルゴリズムで独立したセットを見つけることができます。1。指示されたグラフで深さ第一検索を行い、このノードによってルート化されたツリーの時間が通過します。 2.次に、このグラフのすべてのエッジを逆にします。3。修正されたグラフで深さフリスト検索を再度実行します。 algoriHtmは本で正確に説明されています 「Alogrithmの紹介」