0

セットカバー問題は、次の要素で構成されています。

与えられた:

  1. アイテムUのセット。

  2. それぞれが U からのアイテムを含むセット S のセット。

次のような集合 C の集合を見つけます。

  1. C は S のサブセットです。
  2. C のセットには、U のすべての項目が含まれます (少なくとも 1 回)。

オプションで、最小Cを見つけることができます。つまり、|C| はできるだけ小さいです。

カバー問題を設定するための Wiki リンク

SCP は NP 完全であり、MSCP (または最適な SCP) は NP 困難であり、それを見つけるために多くの手法 (貪欲アルゴリズム、遺伝的アルゴリズム、人工ニューラル ネットワーク) のいずれかを使用できることを理解しています。

ただし、C のサイズ (つまり |C|) を見つけることも NP 困難であるかどうかを尋ねたいと思います。

例を示すには:

Given the following S:
[2 4 6], [1 3 5], [3 2 1], [5 4 6], [2 3 5]

And U being: 
1 2 3 4 5 6

A possible Set-Cover (C) is:
[2 4 6], [1 3 5], [2 3 5]

However, the Optimal Set-Cover (C) is:
[3 2 1], [5 4 6]

Thus |C|, the size of the Optimal Set-Cover is 2.

|C|を見つけたい 問題を解決せずに。これはNPハードですか？そうでない場合、どうすればこれを見つけることができますか?

4

1 に答える 1