问题标签 [set-cover]

找到最小集合覆盖的最省时和正确的算法是什么？我不需要代码本身。我想要一个关于它是如何工作的解释或伪代码。
例如，我们有

最小设置封面为 S3 U S4 U S5。提前致谢！

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

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

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

提前致谢。

假设我们有一个集合 U = {x1, x2, x3} 和一个集合 S = {{x1},{x1, x2},{x1, x3},{x1,x1,x3}}。这纯粹是一个例子，问题是针对一般问题的。这看起来就像一个常规的集合覆盖问题，这就是为什么我认为将其简化为一个真正的集合覆盖问题是可行的。扭曲之处在于 U 中的元素需要被“挑选”z 次，其中 z 对于每个 x1、x2、x3.... 等都是不同的。

S 中的任何子集只能一次提取它们内部的元素。给定一个数字“k”，是否有可能在 S 中形成一个子集的集合，使得

1. U 中的每个元素都包括在内。
2. 每个元素都包含 z 次，其中所有 x 的 z 都不同。

如果我能以这样的方式制定 Set Cover 问题，那就太好了，但我卡在这部分。

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。

举个例子：

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

这个问题与贪心集覆盖问题并不完全相同，但它们的想法相同。

给定一个 Pandas 数据框 df1，其中一列 df['s'] 由一组 df2 键组成：

上面的数据框 df2 可以包含重复的键。我们选择最后一个。例如，为上面的键“3”选择值“1.0”。

我想找到 df['s'] 的前六行，它们可以最大地对其相应键的值求和，并根据它们的值贡献对新数据帧的行进行排序。最快的方法是什么？

对于上面给定的数据集，结果数据框的前两行应该是

上面的第二个不是set([16])，因为set([1,16])中已经包含了“16”，从set([16])中添加的值为零。

按集合中键的对应值的总和排序。

更新：

为了简化这个问题，让我们考虑 df2 仅包含唯一键。并且可以根据安德鲁的技巧轻松修复。

我有一组字符串

[ abcd, efgh, abefg]

如何找到覆盖所有字符的最小字符串数（abcdefgh）

答案是abcdand efgh。但是找到这个答案的算法是什么？

假设宇宙是U，子族是S={s11,s12,...s1a,s21,...,s2b,...,sn1,...snz}，每个元素都是U的子集. 现在我想选择 S 中最小数量的元素来覆盖整个宇宙，但请注意，如果选择 s11，则不会考虑 {s12,...s1a}，这与 {s11, 中的所有元素相同， s12,...s1a,s21,...,s2b,...,sn1,...snz}。我知道这完全是一个集合覆盖问题，但我现在不确定我的约束是否满足。是否还是套套问题？谢谢您的帮助。

我正在使用 Matlab 编写代码，在该代码中，我需要找到覆盖参考列表所有元素所需的最少数量列表（在某些给定列表中）。

例如，假设我的参考列表是

我有一组给定的列表，如下所示：

覆盖中每个元素所需的最少列表数量X是2(B和C)，但是，如果我最初只搜索覆盖最多元素 ( A) 的列表，然后尝试找到将覆盖其余元素的其他列表，我会最终至少使用3列表。编写可以搜索为此所需的最少列表数量的代码的最佳方法是什么（它会给我一个Band的输出C）？任何帮助都将不胜感激......即使只是关于如何最好地解决这个问题的概念解释（不是实际代码）也将是一个巨大的帮助！

我有一个行李清单。
如果允许 N 个选择，我如何选择可以最大化我的集合的 N 个袋子？
例如

如果 N = 2 我想知道...

最大化我的集合...

我正在尝试将其强制拟合为梯度下降格式，但我无法为此创建成本函数。这是一个正确/合理的方法吗？

解决这个问题的最佳方法是什么？

注意：
假设选择列表足够大，以至于不可能计算出所有可能的选择组合。
假设局部最优解是可以接受的。

@sascha - 布景小贴士非常有帮助！

我在编写自己的脚本时采取了捷径，并从以下位置修改了一个：https ://cs.stackexchange.com/questions/16142/how-to-implement-greedy-set-cover-in-a-way-that-它在线性时间运行

印刷...

我缺少的部分是......例如，如果我只能选择 3 个，我如何最大化集合覆盖率？

我正在尝试解决或实现 R 中的集合覆盖问题的近似值。给定这样的数据框。

列中元素的唯一数量n是：

我想计算sets覆盖 n （宇宙）中所有唯一元素的较小数量的集合（列）。在此示例中，有两个集合：s1 {1, 2, 3} 和 s4 {4, 5}。我在维基百科和互联网上读过它，我知道可以应用贪心算法来找到近似值。我也检查了这个链接，他们在其中提到了解决此类问题的两个包，LPsolve并且Rsymphony，但我什至不知道如何开始。在我的现实生活示例中，我有 40,000 多个集合，每个集合包含 1,000 到 10,000 个元素以及 80,000 个非生物或独特元素。

任何有关如何开始或继续的帮助或指导将不胜感激。

数据