導入
正確なカバレッジ問題は、Karp の 21 個の NP 完全問題の 1 つである NP 完全組み合わせ最適化問題です。
声明
要素のユニバースUとコレクションが与えられると、
言い換えれば、正確なカバレッジはサブコレクションです
要素のユニバースUとコレクションが与えられると、
正確なカバレッジ問題は、制約満足問題の一例です。
例1
U = {0, 1, 2, 3, 4, …} を自然数の世界とし、
- 偶数E = {0, 2, 4, 6, 8, …};
- 奇数I = {1, 3, 5, 7, 9, …};そして
- 素数P = {2, 3, 5, 7, …}。
つまり、サブコレクションは
一方、{ E , P } は、特定の自然数がどの集合にも含まれていないため、正確なカバーではありません。たとえば、1 は偶数でも素数でもありません。さらに、いくつかの自然数は複数の集合に含まれます。たとえば、2、偶数、素数などです。
例 2
U = {1, 2, 3, 4, 5, 6, 7} を 7 つの要素からなる宇宙とし、
- A = {1, 4, 7};
- B = {1, 4};
- C = {4, 5, 7};
- D = {3, 5, 6};
- E = {2, 3, 6, 7};そして
- F = {2, 7}。
つまり、サブコレクションは
さらに、次の引数で示されるように、{ B , D , F } は唯一の正確なカバーです。正確なカバーは 1 をカバーする必要があり、1 を含むセットはAとBだけです。したがって、正確なカバーにはAまたはB が含まれなければなりませんが、両方ではありません。正確なカバーにA が含まれる場合、これらのセットのそれぞれにAと共通の要素が少なくとも 1 つあるため、 B 、 C 、 E 、 F のいずれも含まれません。この場合、正確なカバーの一部である残りのセットはDだけですが、コレクション { A , D } は要素 2 をカバーしません。結論として、 A を含む正確なカバーは存在しません。一方、正確なカバーにB が含まれる場合、これらのセットにはそれぞれBと共通の要素が少なくとも 1 つあるため、 AもC も含まれません。この場合、5 を含む残りのセットはDだけであるため、 D は正確なカバーの一部である必要があります。正確なカバーにD が含まれる場合、 DとEには共通の要素 3 と 6 があるため、 Eは含まれません。この場合、 F は正確なカバーの一部である唯一の残りのセットとなり、コレクション { B , D , F } が真に正確なカバーになります。この引数の行列ベースのバージョンについては、 Knuth の X アルゴリズムを参照してください。
一般化
標準的な正確なカバレッジの問題にはコレクションが含まれますが、
集合X 、集合Y 、およびXとYの間の二項関係Rが与えられると、正確な (一般化された) カバーはX*の要素のサブセットX*になります。ここでR -1 はRの逆数です。
一般に、 Y × X*に限定されたR -1 は関数です。つまり、各要素YはX*の 1 つの要素、つまりYの一意の要素にR -1関係しています。
さらに、 R が完全に左の場合、つまりXの各要素がYの少なくとも 1 つの要素にR関連している場合、 Y × X*に限定されたR -1は全射関数です。 ( Rが完全に残るという一般化問題の条件は、すべてが に設定される標準問題の条件に対応します。
一般化された問題の行列表現では、関係Rは行列で表され、 Xの要素は行列の行で表され、 Yの要素は行列の列で表されます。次に、標準的な問題と同様に、正確な (一般化された) カバーは、各列の選択された行の 1 つに 1 が含まれるような行の選択です。
標準問題は、一般化された問題の特殊なケースです。
例 4
上記の例 3 の行列は、6 要素のセットX = {1, 2, 3, 4, 5, 6} とコレクションY = { A , B , の間のバイナリ「に含まれる」関係を表すように再解釈できます。 C 、 D 、 E 、 F 、 G } の 7 セット:
- A = {1, 2}
- B = {5, 6}
- C = {4, 5}
- D = {1、2、3}
- E = {3, 4}
- F = {4, 5}
- G = {1、3、5、6}
例 3 と同じ行列表現がここにも適用されますが、ラベルが異なります。
もっている B C D E F G 1 1 0 0 1 0 0 1 2 1 0 0 1 0 0 0 3 0 0 0 1 1 0 1 4 0 0 1 0 1 1 0 5 0 1 1 0 0 1 1 6 0 1 0 0 0 0 1
例 3 と同様、解決策の 1 つは、行列の2 行目、 4 行目、および6 行目を選択することです。
もっている B C D E F G 2 1 0 0 1 0 0 0 4 0 0 1 0 1 1 0 6 0 1 0 0 0 0 1
ただし、例 3 とは異なり、ここでの解釈は、解が要素のセットX* = {2, 4, 6} であり、 Yの各セットにはX*の要素が 1 つだけ含まれることを示しています。
- A = {1, 2 }
- B = {5, 6 }
- C = { 4,5 }
- D = { 1、2、3 }
- E = {3, 4 }
- F = { 4,5 }
- G = { 1、3、5、6 }
言い換えれば、解は正確に交差する集合です。実際、正確なカバレッジ問題と正確な交差集合問題は互いに二重の関係にあり、つまり本質的には同じです。
