algorithm - Set Cover 的蛮力复杂性

Question

我们可以通过形成所有可能的集合组合并验证它是否是最小解来解决集合覆盖问题。现在我们最多可以有 2^n 个这样的集合组合，其中“n”是集合的数量。

所以，这种方法的复杂度应该是O(2^n)。然而，维基百科说“集合覆盖问题的复杂性是 m^n，其中 m 是宇宙的大小，n 是集合中集合的数量”。

有人可以解释 O(m^n) 而不是 O(2^n) 的复杂性吗？

提前致谢。

Answer 1

你几乎是对的；蛮力算法的复杂性是 O(m 2^n) 直到模型相关的对数因子，因为操纵这些集合不是免费的。O(m^n) 可能来自这样的想法，即对于 m 个元素中的每一个，我们选择最多 n 个集合中的一个来覆盖它。我能提供的最慈善的可能解释是，主要来源为集合覆盖的实例声明了 O(m^k) 的界限，其中每个元素最多属于 k 个集合，这是在近似算法的上下文中考虑的一种特殊情况（有一个多项式时间 k 近似）。

Answer 2

对我来说似乎相当简单。

问题可视化：

• 将宇宙想象为一组路径（一组节点）。
• 将集合想象为宇宙中路径的子集。
• 对于 Universe 中的每个节点，至少存在 1 个它所属的路径。

def Set Cover = 包含所有节点所需的最小路径是多少。

蛮力解决方案：

a = find number of unique nodes in universe
b = find all path permutations as list
c = find b elements where number of unique nodes equals a  
d = order c by path count and pick first

找到所有排列不是 O(m^n)，而是 O(n!)，如果宇宙很大，这将是非常低效的。但是，您不需要所有路径排列，您可以只找到大小为 x 的路径排列，其中 x 枚举从 1 到 a。但是我假设你明白了。