3

可能なセットの組み合わせをすべて作り、それが最小解であるかどうかを検証することで、セットカバー問題を解くことができます。現在、「n」がセットの数である場合、最大 2^n のセットの組み合わせを持つことができます。

したがって、このアプローチの複雑さは O(2^n) になるはずです。ただし、ウィキペディアには、「セット カバー問題の複雑さは m^n であり、m は宇宙のサイズであり、n はコレクション内のセットの数です」と記載されています。

複雑さが O(m^n) であり、O(2^n) ではないことを誰かが説明できますか?

前もって感謝します。

4

2 に答える 2

1

あなたはほぼ正しいです。ブルート フォース アルゴリズムの複雑さは、モデルに依存する対数係数までは O(m 2^n) です。これらのセットの操作は自由ではないためです。O(m^n) は、おそらく、m 個の要素のそれぞれについて、それをカバーするために最大で n 個のセットの 1 つを選択するという考えから来ています。私が提供できる最も慈善的な説明は、各要素が最大 k 個のセットに属するセット カバーのインスタンスについて、一次情報源が O(m^k) の境界を述べていることです。これは、近似アルゴリズムのコンテキストで考慮される特殊なケースです (多項式時間の k 近似があります)。

于 2014-10-16T13:14:01.160 に答える
0

私にはかなり単純に思えます。

問題の視覚化:

  • ユニバースをパスのセット (ノードのセット) と想像してください。
  • コレクションを宇宙のパスのサブセットと想像してください。
  • ユニバースのすべてのノードには、それが含まれるパスが少なくとも 1 つ存在します。

def Set Cover = すべてのノードを含めるために必要な最小パスは何ですか。

ブルート フォース ソリューション:

a = find number of unique nodes in universe
b = find all path permutations as list
c = find b elements where number of unique nodes equals a  
d = order c by path count and pick first

すべての順列を見つけることは O(m^n) ではなく O(n!) であり、宇宙が大きい場合、これは非常に非効率的です。ただし、すべてのパス順列が必要なわけではありません。サイズ x までのパス順列を見つけることができます。ここで、x は 1 から a まで列挙されます。しかし、私はあなたがアイデアを得ると思います。

于 2014-10-16T10:49:08.000 に答える