3

複数のセットのデカルト積を使用して非効率的に解決できる組み合わせ問題があります。具体的には、複数のアイテムと、各アイテムを満たす複数の要素があります。問題は、すべての項目を満たす要素のすべての可能な組み合わせを見つけることです。例えば：

items -> elements
------------------------
1 -> {a,b}     // a and b cover the item 1
2 -> {a,b}     // a and b cover the item 2
3 -> {a,b,c}   // a, b and c cover the item 3
4 -> {a,b,e,f} // a, b, e, f cover the item 4

Alternative representation:
element -> items covered
------------------------
a -> {1,2,3,4}
b -> {1,2,3,4}
c -> {3}
e -> {4}
f -> {4}

目標は、項目 1、2、3、4 をカバーするすべての組み合わせを見つけることです。有効なソリューションは次のとおりです。

{a},{a,b},{a,c},{a,e},{a,f},{a,b,c},{a,b,e},{a,b,f},{a,b,c,e},{a,b,c,f}
{b},{b,c},{b,e},{b,f},{b,c,e},{b,c,f}

順序は重要ではないことに注意してください{a,b} = {b,a} ({a,b} x {c,d} = {c,d} x {a,b})。{a,a,a,a}, {a,a,a,b}...また、は冗長な組み合わせであることに注意してください。

ご覧のとおり、この問題は に似ていますset cover problem。ここで、この例の要素のユニバースはアイテムU={1,2,3,4}であり、U からのサブセットのセットは ですS={ab={1,2,3,4},c={3},ef{4}}。ここで、セット{1,2,3,4}は要素によってカバーされるアイテムのセットでaありb、{3}は要素のセットです。でカバーされc、はエレメントおよび で{4}カバーされるエレメントのセットです。ただし、ここでの目標は、 のすべての要素をカバーするのセットの最小の組み合わせを見つけることではなく、すべての項目をカバーする要素のすべての組み合わせを見つけることです。efSU{a,b,c,e,f}{1,2,3,4}

単純な実装は、1、2、3、および 4 のセット間でデカルト積を実行し、冗長な組み合わせをフィルタリングすることで実行できます。ただし、この方法は非常に非効率的です。次のような状況があるとします。

1 -> {a,b,c,d,e,f,g,h}
2 -> {a,b,c,d,e,f,g,h}
3 -> {a,b,c,d,e,f,g,h}
4 -> {a,b,c,d,e,f,g,h}
5 -> {a,b,c,d,e,f,g,h}
6 -> {a,b,c,d,e,f,g,h,i}

6 つのセット間のデカルト積は8^5*9=294912組み合わせになりますが、実際には組み合わせがはるかに少なく、次のようになります{a,b,c,d,e,f,g} U {a,b,c,d,e,f,g} x {i}。

この問題を解決する別の方法は、すべての要素を列挙し、以前に生成された他の要素と同等の組み合わせをスキップし、繰り返される要素もスキップすることです。これは計算が簡単で、一度に組み合わせを返す反復子として実装できますが、この問題を解決するためのより良い方法があるかどうか、またはこの問題が以前に研究されたかどうかはわかりません。

この問題をどのように解決しますか？

4

2 に答える 2

2

まず、要素のセットがすべての項目を満たさない場合、そのサブセットも満たさないことに注意してください。

次に、セットがすべてのアイテムを満たす場合、そのすべてのスーパーセットも満たすことを認識してください。

今、あなたがしなければならないことは次のとおりです。

S をすべての要素の集合とします。R を空集合とします。

次のことを行う関数 find( s, r ) を定義します。

If r includes s, return r.
If s does not satisfy all items, return r.

Otherwise add s to r.
For every item I in  s,
     let s' be s-I
     let s be f(s', r)

return s.

find(S,R) を呼び出すだけで、答えが得られます。

このメソッドはいくつかの重複したテストを実行しますが、ブランチが特定された場合は常にそのブランチを強制終了します。これにより、要素の大きなセットで多くのプルーニングが発生します。

r が特定の要素セットを含むかどうかのルックアップと、s がすべての項目を満たしているかどうかのチェックは、余分なメモリを犠牲にして非常に高速に実行できます。

于 2013-04-24T16:01:55.957 に答える