4

長さ L の N 個のバイナリ シーケンスがあります。ここで、N と L は非常に大きく、これらのシーケンスは非常にまばらで、1 よりも 0 の方が多いとします。

それらから M シーケンス、つまり b_1、b_2、b_3... を選択したい

b_1 | b_2 | b_3 ... | b_M = 1111...11 (L 1s)

それを達成するためのアルゴリズムはありますか？

私の考えは：

STEP1: 1 から L までの位置について、その位置に 1 を持つ配列の総数を数えます。「所有番号」と名前を付けます

STEP2: 保有数が最小のポジ​​ションを考え、そのポジションの保有配列から1の数が最大の配列を選ぶ。

STEP3: 選択したシーケンスを無視し、所有番号を更新して STEP2 に戻ります。

私の方法では最良の答えは得られないと思います。

誰かがより良いアイデアを持っていますか?

4

3 に答える 3

8

これはよく知られている集合被覆問題です。これはNP困難であり、実際、その決定バージョンは標準的なNP完全問題の1つであり、 Karpの1972年の論文に含まれる21の問題の1つでした。したがって、それを解決するための効率的なアルゴリズムは知られていません。

あなたが質問で説明するアルゴリズムは「欲張りアルゴリズム」として知られており、（あなたの問題にあなたが教えていない特別な機能がない限り）それは本質的に最もよく知られているアプローチです。最小のそのようなコレクションのサイズのO（log | N |）倍以下のセットのコレクションを見つけます。

于 2012-09-09T08:49:10.190 に答える
2

典型的なバックトラックタスクのように聞こえます。

はい、あなたがすぐに良い答えを得たいのであれば、あなたのアルゴリズムは合理的に聞こえます。可能な限り少ないサンプルの組み合わせが必要な場合は、すべての組み合わせを試すよりもうまくいくことはできません。

于 2012-09-09T08:42:24.097 に答える
1

問題の正確な構造に応じて、多くの場合うまく機能する（そして実際に最適な結果をもたらす）他の手法があります。

結果にj番目のバイナリシーケンスを含めるx[j]かどうかの選択を表すブール変数とします。x[j]ゼロ抑制二分決定図は、集合に含まれる変数に対応する二分シーケンスのORがすべて1になるように、集合族を（おそらく簡潔に-問題の特性に応じて）表すことができるようになりました。ZDDが簡潔であれば、そのような最小のセットを見つけること（したがって、含まれるシーケンスの数を最小限に抑えること）は比較的簡単です。詳細については、The Art of Computer Programmingの第7.1.4章（第4A巻）を参照してください。

また、すべての位置に1つだけ存在するようにセットのファミリーを取得することにより、正確なカバーに簡単に適応させることができます。

于 2012-09-09T09:19:15.143 に答える