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}S={ab={1,2,3,4},c={3},ef{4}}{1,2,3,4}ab{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}

六组之间的笛卡尔积将产生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 回答
1

如果你这样做了怎么办：

1 -> {a,b}
2 -> {b,c}
3 -> {a,b,c}
4 -> {a,e,f}

=>

a -> [1,3,4]
b -> [1,2,3]
c -> [2,3]
e -> [4]
f -> [4]

然后枚举左侧提供（至少）[1,2,3,4]的组合

For each item in the set of all-satisfying sets, enumerate combinations 
with other items.

All-Satisfying-Sets: {{a,b},{b,e},{b,f}}
Combinations within All-Satisfiying-Sets: {{a,b,e},{a,b,f},{b,e,f},{a,b,e,f}}
Others: {c}
Combinations with Others: {{a,b,c},{b,e,c},{b,f,c}
                          ,{a,b,e,c},{a,b,f,c},{b,e,f,c},{a,b,e,f,c}}

或者你可以在 Haskell 中这样做：

import Data.List (union, subsequences, sort)

example1 = [(["a"],[1,2,3,4])
           ,(["b"],[1,2,3,4])
           ,(["c"],[3])
           ,(["e"],[4])
           ,(["f"],[4])]

example2 = [(["a"],[1,2,3,4,5,6])
           ,(["b"],[1,2,3,4,5,6])
           ,(["c"],[1,2,3,4,5,6])
           ,(["e"],[1,2,3,4,5,6])
           ,(["f"],[1,2,3,4,5,6])
           ,(["g"],[1,2,3,4,5,6])
           ,(["h"],[1,2,3,4,5,6])
           ,(["i"],[6])]

combs items list = 
  let unify (a,b) (a',b') = (sort (a ++ a'), sort (union b b')) 
  in map fst
     . filter ((==items) . snd) 
     . map (foldr unify ([],[])) 
     . subsequences 
     $ list


OUTPUT:

*Main> combs [1..4] example1
[["a"],["b"],["a","b"],["a","c"],["b","c"],["a","b","c"],["a","e"],["b","e"],
["a","b","e"],["a","c","e"],["b","c","e"],["a","b","c","e"],["a","f"],["b","f"], 
["a","b","f"],["a","c","f"],["b","c","f"],["a","b","c","f"],["a","e","f"],
["b","e","f"],["a","b","e","f"],["a","c","e","f"],["b","c","e","f"],
["a","b","c","e","f"]]
于 2013-04-24T16:48:04.000 回答