最小集覆盖算法:寻找最优覆盖的大小

Question

套盖问题包括以下几个方面：

给予：

1. 一组物品。
2. 一组集合S，其中每个集合都包含来自U.

找到C集集，以便：

1. C是S的一个子集。
2. C中的集合包含U中的所有项(至少一次)。

可以选择地，可以找到最小 C，也就是，在这里，c_x是尽可能小的。

Wiki链接设置封面问题

据我所知，SCP是NP-完全的，MSCP (或最优SCP)是NP-硬的，可以使用多种技术之一(贪婪算法、遗传算法、人工神经网络)。

然而，我想问的是，找出C的大小(即C_c)是否也是NP-难。

举一个例子：

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难吗？如果没有，怎么才能找到这个呢？

Answer 1

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

对于S中的每一个X，求出U-X的最小覆盖的大小。如果它比U的最小覆盖小一个，那么你就知道有一个包含X的最小覆盖(注:U-X的最小覆盖从来不包括集合X)。重复，直到你找到最低限度的掩护。

请注意，封面的大小最多是x，每一次迭代都需要考虑，所以整个过程是P-时间，如果您有一种P-时间的方法来找到最小覆盖的大小。