-3

The following gives a practical example:

Let's say for m = 4:

// the sets for reuniting
Set1 = { 5 , 1 , 2 }
Set2 = { 2 , 6 , 3 }
Set3 = { 7 , 8 , 4 }
Set4 = { 4 , 9 , 10}

// the set I need to form
Set m+1: Set5 = { 1 , 2 , 3 , 4 }

I have to find a set of indexes e.g. A = { 1, 2, 3 } so that U (Seti) includes Set5, where i is part of A. The cardinal of A must be minimal.

4

2 回答 2

2

如果我正确理解了你的问题,

这是集合覆盖问题,这是 NP 难题。

因此,没有一种算法既是最优的是贪婪的。检查显示贪婪次优方法的文章。

于 2011-12-19T10:21:04.160 回答
0

如果我正确理解了这个问题,这里的伪代码会返回涵盖 set5 的集合的索引:

setTmp = set5
A = {}
foreach i:
  if (seti intersect setTmp) is not empty then
    setTmp = setTmp  \ setI
    A.add(i)
return A

请注意,这是一种贪婪的方法,并不能保证 A 是最小的

于 2011-12-19T10:13:54.027 回答