一致するデバイスの最長チェーンを見つける

StackOverflow https://stackoverflow.com/questions/8317962

  •  25-10-2019
  •  | 
  •  

質問

Aを設定しますnデバイス。セットBにはMデバイスがあります。 Aの一部のデバイスはBのデバイスと互換性があり、Bの一部のデバイスはAのデバイスと互換性があります。

できるだけ多くの互換性のあるデバイスが接続されていることを望んでいます。 （相互に互換性があるように、デバイスAをAとBのBにBのBに配置する必要はありません。）

明確にするために編集します: ：任意のデバイスは、0、1、または2つの他のデバイスにリンクできますが、それ自体ではありません。

最終的に、すべてのデバイス（または「終了」が満たされない場合は2つを除くすべて）を1対1でリンクする必要があります。1つのデバイスを他のデバイスにリンクすることができます。しかし、Aのデバイスは任意のデバイスと互換性がありません（しかし、それらは リンク可能）、そして同じことがBのデバイスにも当てはまります

If I have A = {a1,a2,a3}, B = {b1,b2,b3} and n=m=3

a1 is compatible with b1,b2
a2 is compatible with b1
a3 is compatible with b1
b1 is compatible with a1,a3
b2 is compatible with a1
b3 is compatible with a1

次に、グラフg

a1 <-> b2 <-> a2 <-> b1 <-> a3 <-> b3 <-> a1

最適なグラフです。

Gは周期的である必要はありませんが、そうかもしれません。

これにアプローチする賢い方法はありますか？

役に立ちましたか？

解決

この問題は、無向の長いパス問題からの減少によりNPハードであると信じています。 計算理論の紹介 理由の詳細については）。

対象のない最も長いパスの問題では、入力として、無向グラフg =（v、e）を入力として与えられ、ノードuとvおよびk kのペアとともに、単純なものがあるかどうかを判断したい（いいえなしノードは2回表示されます）uからuからvまでのパスは、少なくともk。次のように、多項式時間の減少を使用して、これを問題に変換できます。

  • 各ノードvについて私 ∈V、aにデバイスがあります（それをdと呼びます私).
  • 各エッジについて{v私, 、vj}∈V、bにデバイスがあります（eと呼びますI、J).
  • 各ノードvについて私 およびエッジ{v私, 、vj}、デバイスd私 デバイスeと互換性がありますI、J.

生成されたデバイスの総数はサイズ| V |であるため、この削減は多項式サイズです。 + | e |接続の数は2 | e |です。さらに、Vから長さkの経路があることがわかります私 vにj グラフg iffには、dからの長さ2k + 1のデバイスのチェーンがあります私 dj. 。具体的には、（v私1, 、v私2）、（v私2, 、v私3）、...、（v私K -1, 、v私k））はvからの単純なパスです私 vにj, 、その後、チェーンd私1 →e私1, 、 私2 →d私2 →e私2, 、 私3 →d私3 →...→e私K -1, 、 私k →d私k およびその逆。したがって、私たちは次のように、あなたの問題への最長の最も長い経路からの多項式時間の減少を持っています：

  • 入力として与えられる（g、v私, 、vj, 、k）無視されていない最も長いパスの問題へ：
    • 上記のようにセットAとBを構築し、互換性cを上記のように構築します。
    • Dから長さ2K + 1のデバイスのチェーンがあるかどうかを確認します私 dj.
    • もしそうなら、出力「はい」
    • そうでない場合、出力「いいえ」。

この削減は、問題のためにソルバーを使用して、非決定的多項式時間の無向長いパスの問題を解決するため、問題はnpハードです。その結果、問題の多項式時間アルゴリズムを見つけることを期待してはなりません。正確な答えを見つけるには、p = npでない限り指数関数的な時間がかかる可能性があります。

否定的な答えを出して申し訳ありませんが、これが役立つことを願っています！

他のヒント

これはNPハードですが、最大サイクルカバーの問題近似は（サイズ0のエッジを持つ各グループリンクデバイスで）役立つと思います。また、他のすべてのノードに接続された追加ノードを重量0で追加することもできます）この紙： 重量ゼロと1の指示グラフで最大重量サイクルカバーを近似する が手伝う。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top