algorithm - 最小集覆盖算法 : Finding Size of Optimal Cover

Question

Set-Cover 问题包括以下内容:

Given:

1. A set of Items U.

2. A set of Sets S each of which contain items from U.

找到集合 C 的集合使得:

1. C is a subset of S.
2. The sets in C contains all items in U. (at least once).

可选地，可以找到最小 C，即|C|越小越好。

Wiki Link to Set Cover Problem

我知道 SCP 是 NP-Complete，而 MSCP(或最优 SCP)是 NP-Hard，可以使用多种技术中的一种来找到它(贪心算法、遗传算法、人工神经网络)。

但是，我想问一下求 C(即 |C|)的大小是否也是 NP-Hard。

举个例子:

Given the following S:
[2 4 6], [1 3 5], [3 2 1], [5 4 6], [2 3 5]

And U being: 
1 2 3 4 5 6

A possible Set-Cover (C) is:
[2 4 6], [1 3 5], [2 3 5]

However, the Optimal Set-Cover (C) is:
[3 2 1], [5 4 6]

Thus |C|, the size of the Optimal Set-Cover is 2.

我要找|C|没有解决问题。这是 NP-Hard 吗？如果没有，如何找到它？

Answer 1

如果你能在 P 时间内找到最小覆盖的大小，那么你也能在 P 时间内找到最小覆盖。

对于 S 中的每个 X，找到 U - X 的最小覆盖的大小。如果它比 U 的最小覆盖的大小小一个，那么你知道有一个包含 X 的最小覆盖(注意:最小覆盖为U - X 从不包含集合 X)。重复直到找到最小覆盖范围。

注意封面的大小最多为|U|，每次迭代需要|S|要考虑 X，所以如果您有 P 时间的方法来找到最小覆盖的大小，那么整个过程就是 P 时间。