このタスクに役立つ可能性のあるものを見つけようとしています: 可変数のビット シーケンス (すべて個別に同じ長さになります) があり、シーケンスのどの組み合わせがすべての 1 の OR になるかを見つける必要があります。可能な限りシーケンス。1が最も多いシーケンスから始めて、空白を埋めようと考えていましたが、ビット比較を実際に行ったことがないので、これを単純化するアルゴリズムまたはビットロジックのプロパティがあるかどうかはわかりませんでした。ありがとう。
質問する
190 次
2 に答える
4
残念ながら、この問題は、セット カバー問題からの縮小により、最も一般的なケースでは NP 困難です。セット カバー問題では、要素のセットのコレクションがあり、和集合にすべての要素が含まれる最小数を見つけたいと考えています。特定のセットにその項目がある場合は各位置に 1 があり、そうでない場合は 0 である各セットのビットベクトルを作成することにより、セット カバーの問題を問題に簡単に減らすことができます。OR がすべて 1 になるビットベクトルの最小数は、和集合がすべての要素を含むセットの最小グループに相当します。
たとえば、セット {a, b, e}、{b, c}、{b, d, f}、および {a, f} を指定すると、次のビットベクトルが得られます。
{a, b, e} 110010
{b, c} 011000
{b, d, f} 010101
{a, f} 100001
セット カバー問題は NP 困難であることが知られているため、これは、P = NP でない限り、問題に対する多項式時間アルゴリズムがないことを意味します。さらに悪いことに、多項式時間で O(log n) の係数内で最適解を近似できないことが知られています。ここで、n は要素の総数です。おそらく、ヒューリスティックを探すか、貪欲なアルゴリズムを使用して O(log n) 近似に満足するのが最善です。
お役に立てれば！
于 2012-08-02T22:47:37.697 に答える
0
私はこの問題について少し考えました、そしてここに私が思いついた考えがあります：
まず、すべてのビットに対してリストを作成し、すべてのリストで、このビットに「1」が付いているすべてのシーケンスを見つけます。これには、シーケンスの数と特定のシーケンスの長さを表すO（n * m）が必要です。
次に、すべてのビットシーケンスのすべての出現をカウントし、[リスト、整数]のこれらすべてのタプルを構造体（AVLツリーまたはヒープまたは任意のもの）にスローして、それらを並べ替えます。（つまり、シーケンス'a'はすべてのリストで15回発生し、シーケンスbは10回発生します）。O（nlogn）<O（n * m）であるため、これもO（n * m）を取ります
次のステップでは、優先度が最も高いシーケンスを使用し、このシーケンスを含むステップ1のすべてのリストを削除します。次に、すべてのリストを削除するまで、手順2に戻ります。最悪の場合、これをm回実行する必要があります。
したがって、合計でO（n * m ^ 2）の時間があります。質問の一部を誤解した場合、または間違いをした場合は、訂正してください;）意味の簡単な例を次に示します。
ビット文字列：
a： 100101
b：010001
c：011100
d：000010
したがって、これによりリストが作成されます
。L1：a
L2：b、c
L3：c
L4：a、c
L5：d
L6：a、b
次に、カウントして並べ替えます：
a：3
c：3
b：2
d：1
したがって、最終リストにaを取り、次のリストを削除します：
L1、L4、L6
ここでもう一度数えます：
c：2
b：1
d：1
したがって、リストからcを取り、
L2、L3を削除して、
dのみを含むL5のみを残します。
したがって、最終的な最小セットが見つかりました：a、c、d
于 2012-08-03T01:52:56.253 に答える