3

给定几个集合和一个数字 n：

Here assume n is 5:
a - (0,1,2)
b - (0,1,2,3)
c - (1,3,4,5)
d - (0,1,2,4)
e - (2,3,4,5)
f - (3,5)

现在，如果我们取 just b，c我们会得到从 0 到 5 的整个范围。

我正在考虑一种贪婪的方法，但这似乎不适合这里。

4

3 回答 3

6

这是集合覆盖问题，因此是 NP 完全问题，这意味着您必须考虑所有可能的解决方案并选择最小值。

于 2013-06-09T11:54:16.893 回答
0

BFS 搜索可以轻松解决这个问题。

min = 0

function bfs(i, visited sets)
    if i > m
        n = the number of the visited sets without duplicates
        if n < min
            min = n
        end
        return
    end

    if no set contains i
        return
    end

    for each set that contains i
        bfs(i+1, visited sets + this set)
    end
end

从 i = 0 开始搜索并清空访问集

bfs(0, empty set)

那么min将是最小的集合数。

于 2013-06-09T12:15:17.987 回答
0

如果通过检查所有可能的子集很容易获得，则获得最小集合数的最佳解决方案，但这将采取2^kwhenk是集合的数量。

您可以通过构建图形并运行深度为 1、2、3 的 DFS 来做到这一点……直到获得完全覆盖。

在运行时间和最佳解决方案之间存在权衡。is 将不接受最小设置，而不是运行时间更少的选项

于 2013-06-09T11:50:47.393 回答