算法：寻找包含整个域的最小集合数量

Question

给定一些集合和一个数字 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)

现在，如果我们只考虑b和c，那么我们可以得到从0到5的整个范围。

我曾尝试一种贪心方法，但貌似不适用于这里。

- Peter

Answer 1

这是覆盖问题，属于NP完全问题，意味着你必须考虑每个可能的解决方案并选择最小值。

- Koterpillar

Answer 2

一个广度优先搜索可以轻松解决这个问题。

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将是集合中的最小数。

- Tao Peng

---

你能考虑一下这个问题的复杂性吗？有什么更好的解决方法吗？ - Peter

我认为复杂度是O(N^m)，其中N是集合的数量。 - Tao Peng

每个函数可能会进行N次递归调用；构建答案可能需要N个集合，因此复杂度为O(N^N)。 - Koterpillar

@ring0 我只是想说它不比第一个答案更好。 - Peter

Answer 3

获取最小集合的最佳解决方案是通过检查所有可能的子集来获得，但当 k 是集合数量时，这将需要 2^k 的时间。

您可以通过构建图并运行深度优先搜索（DFS），直到获得完全覆盖来完成它。

在运行时间和最优解之间存在权衡。如果运行时间较短，则会接受不是最小集合的选项。

- Mzf

---

“K^2”是错误的，可能需要更多的集合来覆盖整个集合。 - Koterpillar