セット内の少なくとも 1 つのベクトルに設定されたビットがすべてのインデックスに含まれるように、バイナリ ベクトルの最適なセットを見つける効率的なアルゴリズムを見つける必要があります。
面白い動機：城に侵入して宝物を盗みたい。それを行うには、青いドア、赤いドア、黄色、緑の 4 つのドアのロックを解除する必要があります。小人は 3 人いて、それぞれに異なる鍵のセットがあります。ドワーフ 1 には、青のキーと赤のキーがあります。ドワーフ 2 には、赤鍵と黄鍵があります。ドワーフ 3 には、ブルー キーとグリーン キーがあります。城に入るために最低限のドワーフを倒したい。したがって、この場合、すべてのキーを取得するにはドワーフ 2 とドワーフ 3 のみを強制終了する必要があり、ドワーフ 1 を強制終了する必要がないことは明らかです。
一般に、サイズ m (n 個のドワーフと m 個のドア) の n 個のバイナリ ベクトルがあります: a0、a1....a(n-1)。ベクトル内のすべてのインデックスに対して少なくとも 1 つのキーを持つような一連のベクトルが必要です。a1[5]=1 の場合、2 番目のベクトルの 6 番目のビットが設定されていることがわかります。ドワーフ #2 がキー #6 を持っていることを意味します。最初の例は実際には次のようになります: a0 (1,1,0,0) a1 (0,1,1,0) a2 (1,0,0,1) したがって、取得するベクトル: a1,a2 を選択します。最小限のベクトルで完全にカバーします。
ブルート フォース ナイーブ アルゴリズムは、すべてのオプションを試してから最小量のベクトルで解を返すことですが、n 個のベクトルがあるため、2^n 個のオプションがあります。
次に、毎回最も多くのキーを持つベクトルを取る貪欲なアルゴリズムを考えました。しかし、この方法が間違っていることを証明する反例を次に示します。
- a0 (1,1,1,0,0,0) --貪欲で間違った選択--
- a1 (1,0,0,1,0,0)
- a2 (0,1,0,0,1,0)
- a3 (0,0,1,0,0,1)
このアルゴリズムでは、4 つのベクトルすべてを選択しますが、最適解には 3 つのベクトル {a1,a2,a3} しかありません。
ここで、別の貪欲なアルゴリズムを考えました。最もレアなキーを持つベクトルを選択します (同点の場合は、次のレア キーなどを検索します)。しかし、ここでも反例を見つけました。
- a0 (1,1,1,0,0,0) --貪欲で間違った選択--
- a1 (1,0,0,1,0,0)
- a2 (0,1,0,0,1,0)
- a3 (0,0,1,0,0,1)
- a4 (0,0,0,1,0,0)
- a5 (0,0,0,0,1,0)
- a6 (0,0,0,0,0,1)
この例では、すべてのインデックスが同じ「希少性」(2) を持っているため、最終的に a0 を選択することになりますが、a0 を持つスロット ({a0,a1,a2,a3} など) には少なくとも 4 つのベクトルがあり、最適解は{a1,a2,a3} は 3 つだけです。
別のベクトルのサブセットであるベクトル (たとえば、a6 は a3 のサブセット) を削除すると、このアルゴリズムが機能する可能性があると思いますが、それでも、これをチェックするには n! のコストがかかります。
効率的なアルゴリズムを見つけるのを手伝ってくれるか、そのようなアルゴリズムが存在しないことを証明するのを手伝ってくれることを願っています.