0

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

鉴于：

  1. 一组项目 U。

  2. 一组集合 S，每个集合都包含来自 U 的项目。

求集合 C 使得：

  1. C 是 S 的子集。
  2. C 中的集合包含 U 中的所有项目（至少一次）。

或者，可以找到最小C，即 |C| 尽可能小。

设置封面问题的 Wiki 链接

我知道 SCP 是 NP-Complete 并且 MSCP（或 Optimal 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 吗？如果没有，如何才能找到这个？

4

1 回答 1

2

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

对于 S 中的每个 X，求 U - X 的最小覆盖的大小。如果它比 U 的最小覆盖的大小小一，那么你知道存在包含 X 的最小覆盖（注意：U - X 的最小覆盖从不包括集合 X)。重复，直到你找到一个最小的封面。

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

于 2015-04-19T05:54:40.767 回答