この番号グループシーケンスを解決できるアルゴリズムはありますか？

Question

私は以下に説明する問題があります。あなたは良い解決策を持っていますか、あるいはこの問題は単に "古典"や "解決された"問題の別の形ですか？

問題がある：

番号、例えばいくつかのグループがあります。

A（1 8 9）

B（1 4）

C（2 4 6）

D（3 4 7）

E（2 10 11）

F（3 12 13）

"AF" 6基があります。数字は「1,2,3,4,5,6,7,8,9,10,11,12,13」です。 今度は、各グループを満たす最小セット数が、少なくともこのセット内の数字を持つ必要があります。例えば、Aが「1」、Bが「1,4」、Cが「2,4」、Dが「4」、Eが「2」であるセット「1 4 2 13 12」を見つけることができる。 Fは「12,13」です。

しかし、 "1 2 4"と設定されているとは限りませんが、Fにはセット内に数字がありません。

ベストセットは「1,2,3」で、すべてのグループはセット内に番号があり、セットのサイズは最適です。それは3つの数字しかありません。これは私たちが望むものです。最良のセットがたくさんある場合、いずれかを見つけることはOKです。ありがとう。

Answer 1

これはset cover problemに相当します。この場合、あなたのセットA、B、...、Fのそれぞれは、セットカバー問題の要素であり、数字1,2、...、13のそれぞれがセットです。例えば、この写像1は{A、B}になり、11は集合{E}となる。

セットカバーはNP困難です。リンクされたWikipediaのページにある整数線形計画は、正確な解を得るためのものと同じくらい良いものです。貪欲なアルゴリズムは、大きな問題のためのまともな近似があります。

Answer 2

この問題はNP困難NP-hardvertex cover problemから還元を介して（グラフ与え、あなたがグラフ内の各頂点は、いくつかの選択されたノードに隣接するようにk個のノードの集合を見つけることができますか？）

あります削減は以下の通りです。グラフ1,2,3、...、nのすべてのノードに、任意の順序で番号を付けます。次に、グラフの各辺について、辺の端点である2つの数だけの集合を構築します。元のグラフにkノードの頂点カバーがある場合、各セットから1つの番号が選択されるように、選択できるk個の番号のセット（つまり、頂点カバー内のノード）があります。これは、多項式時間で計算することができます。

縮小が機能する理由を確認するには、サイズkのセットがある場合、構造内の各セットに少なくとも1つの要素が選択されるように選択できます。これらの数値に対応する頂点はk要素元のグラフの頂点のカバー。

この削減は多項式時間で行うことができるので、NP-hard頂点被覆問題から問題まで多項式時間を短縮します。したがって、この問題はNP困難です。したがって、P = NPを除き、この問題の多項式時間アルゴリズムはありません。

希望すると便利です。