algorithm - Fastest way to find out the least nr of m given sets reunited include a separate m+1 set

Question

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.

Answer 1

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

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

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

Answer 2

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

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

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