-1

これは宿題ではありませんが、調査中に遭遇した質問です。この問題が NP 困難かどうかを知る必要があります。前者の場合は近似アルゴリズムが必要であり、後者の場合は最適解を提供する効率的なアルゴリズムが必要です。

非公式の説明:

p 人が t 個のツールを使用していると想像してください。すべての人がすべてではなく、2、3 のツールしか使用していません。誰がどのツールを使用したかを誰かが書き留めます。質問: 各人が少なくとも k 個のツールを使用し、他の人も使用する最大のグループを見つける方法は? 【事前問題解説：みんなと同じ道具？】 道具の数がt'に制限されている

この問題の正式な説明を作成しました。これは役立つ場合があります。

G=(P,T,E) を2 部グラフとします。ここで、P は人の集合を表し、T はツールの集合を表します。人がそのツールを使用した場合、P のノード p と T の t の間にエッジがあります。目標は、次の条件が適用されるセット P'、T' を見つけることです。1) P' 内の任意の p' から、T' 内の任意の t' に単一のエッジで到達できます。2) |P'|、つまり P' 内のノードの数は最大です。

非効率的なアプローチは、各サブセット P' を取得し、P' 内の p' に関連付けられた各 t' の交差を計算することです。残念ながら、そのようなサブセットの数は指数関数的に増加し、計算はすぐに扱いにくくなります。

どうもありがとうございました！

4

2 に答える 2

1

間違いなく NP ではありません - ハード。貪欲なアプローチをお勧めします。最大番号のツールを見つけるだけです。それを使用している人々の。そのような最大のグループが 2 つのツール A と B を使用すると仮定すると、その数は最大 (A または B を使用する人の数) を超えることはありません。

于 2014-06-27T19:14:16.077 に答える
1

各人が他の人と同じツールを使用している最大のグループを見つけるには、使用するツールのセットによって人をグループ化するだけです。

言い換えると：

  • マップを作成します: (ツールのセット) から (このツールのセットを使用している人の数) まで
  • カウントが最も高いツールのセットを見つけます。

これは間違いなく多項式です。

例えば：

ツール セットが{クロー ハンマー、テープ メジャー、ユーティリティ ナイフ、水分計、チゼル、レベル、ドライバー、ネイル セット、スライディング ベベル、レイアウト スクエア} であるとします( source )

ビットセット (文字列としての整数として表される) から整数 (このツールのセットを使用する人の数) へのマップを作成します。

ここで、ダンのツールが {Claw Hammer, Utility Knife, Sliding Bevel} の場合、次のマップに追加します。

キー: 1010000010、値: 1。

別の人を追加するには、まずキーを計算します。Dave が Dan と同じツールを使用している場合、同じキーを取得するので、カウントを増やします。

キー: 1010000010、値: 2。

--

  • 人のツールリストからビットセットを構築するのはO(T)です
  • そのようなキーが既にマップに存在する場合の検索はO(log(P)∙T) ( O(T)は、長さ T の 2 つの文字列を比較する場合の最悪のケースです。キーがソートされているため、おそらくはるかに優れています。また、O (log(P) は反復構造を無視します)。
  • カウントの増加はO(1)です。代わりに、新しいキーをマップに追加するとO(log(P))になります(実際には、マップが反復的に構築されるため、より優れています)。

要約すると、 O(P∙log²(P)∙T)ですべての人のセットを構築できます。繰り返しますが、もっとうまくやることができますが、これは多項式であることを証明するためのものです。

カウントが最大のキーを見つけるのは O(P) です。これより少ない P 個のキーを含むマップ上を歩きます。

于 2014-06-27T18:12:04.577 に答える