4

これが確立されたコンピューター サイエンスの問題であるかどうか、多項式時間の解または近似があるかどうか疑問に思っています。

true 値と false 値で構成されるリスト X があるとします。

X = [True, False, True, False, True...True]

Xと同じ長さで、真と偽の値を持つ他のリストのセットもあります

A = [False, True, True, True, True, False .... False]
B = [False, False, True, False, True, False .... False]
...etc

ここで、これらの他のリストの「合計」を見つけたいと思います (ビットごとの OR 演算子を各要素に適用しています..つまり、 F + F = F 、 F + T = T 、 T + T = T) を最もよく説明しますリスト X に見られる観察結果 (一致に対して何らかのスコアを与え、ソリューションの不一致に対してペナルティを与えるスコアリング システムを導入できます)。多くの可能なソリューションが存在する可能性があるため、アルゴリズムにペナルティを課したいと考えています。ソリューションで使用するより多くのリスト。

4

1 に答える 1

5

あなたが説明している問題は、NP困難であることが知られている最小セットカバー問題からの削減により、NP困難です。

減額は以下の通りです。n 個の要素のセット S が与えられた場合、リスト X として "true" の n 個のコピーのリストを作成します。次に、セット カバーで許可される可能性のある各セットについて、各スポットで true または false を持つリストに置き換えます。セットに S の特定の要素が含まれているか含まれていないかに基づいています。不一致に無限のペナルティを割り当て、各リストに 1 のコストを割り当てると、元のサイズ k 以下のセット カバーが存在します。問題にコスト k 以下の解がある場合にのみ、カバー問題を設定します。

これは、この問題に対する既知の多項式時間アルゴリズムがないことを意味します。おおよその答えを受け入れるか、一部の入力でプログラムを長時間実行する必要があります。

お役に立てれば！

于 2013-01-15T17:21:59.310 に答える