问题标签 [set-cover]

集合覆盖算法往往只提供一种解决方案来找到要覆盖的最小数量的集合。如何去寻找所有这些解决方案？

我有一组节点，每个节点包含 0 个或多个点。节点之间存在重复点，但每个节点可能包含该节点唯一的点。

例如：

• 节点 A
  • 第 1 点
  • 第 2 点
  • 第 3 点
• 节点 B
• 节点 C
  • 第 1 点
  • 第 4 点
• 节点 D
  • 第 2 点

等等

是否有一种算法或方法可以找到包含最多点数的最少节点数，直至特定限制？

在上面的例子中，如果我需要 4 个唯一点，我会得到节点 A 和节点 C，或节点 A 和节点 D。

目前，我正在通过按点数（即节点 A、节点 C、节点 D）对节点列表进行降序排序并丢弃没有点的节点（节点 B）来解决此问题。然后，我将遍历该节点列表，计算唯一点（并记录查看的节点），直到达到定义的唯一点阈值。因此，在上面的示例中，我的结果将是节点 A 和节点 C。

对于它的价值，我在 Javascript 中执行此操作，但我认为我的问题更多是“如何解决问题”而不是与特定语言相关。道歉，如果这是不正确的地方张贴。

美好的一天，我想为Set Cover Problem实现一个 T-SQL 查询，但找不到任何关于如何在 SQL 中执行此操作的提示。

就我而言，我的表只有两列（IDnumber和Mut），我想找到IDNumber每个Mut. 我真的很想每人获得三个IDnumbers，Mut但我想我最好从一个开始，因为这可能更容易。

因此，您可以从数据透视表中看到最小值IDnumbers为 3、5、7 和 12。

人们将如何实施该算法？在我看来，我可以找到所有的组合 (2^6)，然后确定哪些组合具有所有 Muts。具有最少 ID 编号的集合是最小集合。

这种蛮力可能会奏效，但效率会非常低。我的真实案例并不庞大，我有 43 个独特的Muts（不是示例中的 9 个）和 ~2000 IDnumbers，但我认为这需要一些时间来运行，因为 2^2000 非常大......

谢谢！

我在 python 中调用 itertools（见下文）。在此代码中，snp_dic是一个具有整数键和集合作为值的字典。这里的目标是找到键的最小列表，其值的并集是集合并集的组合，相当于set_union. （这相当于为那些感兴趣的人解决流行的 NP-hard 图论问题集的全局最优解）！下面的算法有效，但这里的目标是优化。

我看到的最明显的优化与 itertools 有关。假设长度为 r，在 snp_dic 中存在 r 个集合的组合，其 union = set_union。基本概率表明，如果这种组合存在并且随机均匀地分布在组合的某处，则预计平均而言只需迭代这些组合即可找到该集合覆盖组合。然而，Itertools 将返回所有可能的组合，通过在每次迭代中检查来检查 set_unions 所花费的时间是预期时间的两倍。

一个合乎逻辑的解决方案似乎只是在本地实现 itertools.combinations() 。基于 python 文档中 itertools.combinations() 的“等效”python 实现，但是时间大约慢了两倍，因为 itertools.combinations 调用 C 级实现而不是 python-native 实现。

那么问题（最后）是，我怎样才能一个一个地流式传输 itertools.combinations() 的结果，以便我可以检查集合联合，因此它仍然在与 itertools.combinations 的 python 实现几乎相同的时间运行()。在一个答案中，如果您可以包括计时新方法的结果以证明它在与 python-native 实现相似的时间运行，我将不胜感激。任何其他优化也表示赞赏。

在下面的封面实例中。贪心算法会选择多少组？所有套装的成本为 1。

谁能给我解释一下。这个问题的解决方案是什么。

那么贪心算法将如何适用于第二个实例。

它在实例中选择了多少组。

我期待使用遗传算法解决Set Cover 问题。我一直在到处寻找一些好的测试实例，但没有任何大的成功。

我正在寻找以下形式的一些实例：集合 U = {1,2,...,n} 及其子集 S={{1,2}, {4}, {3 ,4,5}}，其中 S 的并集是 U。

当然这是一个小例子，因为我想找到一些更大的例子。

那么，是否有人对此类实例的良好来源有任何想法，或者可能对生成它们的方式有任何想法？

稍后编辑：所以我看到问题已被搁置。那我不好，我会添加更多细节。

首先，我搜索了一些测试实例来解决设置覆盖问题。我期望找到的是一些像我上面描述的例子。运气不好，我发现了类似的东西。我必须说，链接中没有太多细节可以让我了解这些情况。

所以我开始思考一种生成它们的方法。伪编码解决方案：

虽然我不确定是否 union(subsets) = G，所以我的疑虑就在哪里，所以这就是为什么我需要一些已经生成的测试实例。

银行有自动取款机。对于特定的一周，百万现金的使用情况如下。

• 5- 星期一
• 4- 星期二
• 1- 星期三
• 15-星期四
• 6-星期五
• 2-星期六
• 4-周日

银行聘请存款公司每周存款 5、3 或 1 轮。

存款公司在收取存款时向银行提供以下套餐，

• 每月 4 轮存款的成本 - 21135

• 每月 12 轮存款的成本 - 32000

• 每月 20 轮存款的成本 - 41975

订单保持为周一、周二、周三、周四、周五、周六、周日。在对值进行分类时，不应违反此顺序。

例子

• 5轮

[(5+4),1, 15, 6, (2+4)]

[(5+4), 1, (15+6)=20+1, 2, 4]

可以有许多其他不破坏顺序的组合。

• 3轮

[(5+4+1), 15, (6+2+4)]

[(5+4), (1+15), (6+2+4)]

可以有许多其他不破坏顺序的组合。

• 1轮

[(5+4+1+15+6+2+4)]

此外，银行必须在一天结束时承担剩余金额的 0.019% 的持有成本。

例子

考虑以下第一周的现金使用情况。（以百万计）

周一- 13

周二 - 5

周三- 4

周四- 4

周五至 2

周六 - 11

太阳- 1

5轮

第一周 现金存款订单 - 13, (5+4), 4, (2+11), 1

假设在一个月的所有 4 周内进行 5 轮存款，(5*4 = 20)

总存款成本 = 41975

1- 13 存款， 13 撤回， 0 剩余， 0 持有成本

2- (5+4) 存入，5 取出，4 剩余，4*0.00019 持有成本

3- 0存款，4取款，0剩余，0持有成本

4- 4 存款， 4 撤回， 0 剩余， 0 持有成本

5- (2+11) 存入，2 取出，11 剩余，11*0.00019 持有成本

6- 0 存款， 11 撤回， 0 剩余， 0 持有成本

7- 1 存款， 1 撤回， 0 剩余， 0 持有成本

第 1 周的总持有成本 = 4*0.00019 + 11*0.00019 = 0.00285 万 = 2850

同样，考虑到每个特定的星期，我需要找到该月的总持有成本。

3轮

第1周现金存款订单 - 13, (5+4+4), (2+11+1)=(1+1+12)

编辑 - 假设选择每月 12 轮套餐，因此每周 3 轮（3*4 =12）

总存款成本 = 32000

1 - 13 存款，13 撤回，0 剩余，0 持有成本

2- (5+4+4) 存入，5 取出，(4+4) 剩余，(4+4)*0.00019 持有成本

3- 0存款，4取款，4剩余，4*0.00019持有成本

4- 0存款，4取款，0剩余，0持有成本

5- (2+11+1) 存入，2 取出，(11+1) 剩余，(11+1)*0.00019 持有成本

6- 0存款，11取款，1剩余，1*0.00019持有成本

7- 0存款，1取款，0剩余，0持有成本

第一周总持有成本 = (4+4)*0.00019 + 4*0.00019 + (11+1)*0.00019 + 1*0.00019 = 0.00475 万 = 4750

同样，我需要考虑每周计算当月的总持有成本。

编辑 - 假设选择了 41975 包。那么这意味着每月存入 20 轮现金。这意味着每周 5 轮。如果32000包被挑，那么每月12轮。这意味着每周 3 轮。如果选择21135包，则表示每月4轮，即每周1轮。特定月份的四个星期没有 5,3,1 的混合组合。只有所有的四个星期都是在 1、3 或 5 轮中完成的。我们必须考虑持有成本和包装成本来选择最佳包装。

5轮不违反顺序的良好组合，可以优于所有3轮解决方案和1轮解决方案。同样适用于 3 轮解决方案。否则 1 轮解决方案可能优于所有 5 轮和 3 轮解决方案。

当存款轮数增加时，持有成本降低，但存款成本增加。当轮数减少时，存款成本会降低，但持有成本会增加。所以我需要找到每个月每个星期的存款顺序和每月的存款套餐，这样可以在总持有成本和总存款成本之间做出很好的权衡，消耗最少的时间。

对该方法的任何见解都将非常有帮助。

我需要一些帮助来解决以下问题：

显示集合覆盖问题的输入示例，该类中显示的贪心算法不提供 2 近似值。

贪心算法：

X - 有限集

F - X 的子集族，使得并集给出 X

C - 覆盖 X 的所需最小尺寸集。

给定一个包含元素的集合列表：

L以及需要涵盖的元素列表：[x, y, z, ...]

从 L 中找到最小的集合列表，其并集包含列表中的所有元素L。

这个问题是否与 Set-Cover 相同（暗示它是 NP-Complete）？或者我是否缺少一些使它易于处理的东西？

假设可以确定元素 x 是否存在于恒定时间内的集合中。

下面的程序（改编自http://www.hakank.org/minizinc/set_covering4b.mzn）是集合覆盖问题的解决方案（问题末尾提供的示例数据）。这运行正确。

但是，如果我替换a上面的定义：

array[ALTERNATIVES] of var set of 1..num_objects: a;

这两行在我看来是等价的：

...突然我收到以下错误：

MiniZinc：类型错误：type-in​​st 必须是 par 集，但是是 `var set of int'

这让我很困惑。我什至改变了什么？在每种情况下a都是一组整数集。在每种情况下，类型实例都是 a var set of int，但第二个会引发错误，而第一个不会出于某种原因？

---

这里有一些数据可以放在 .mzn 代码文件的底部，以生成一个独立的、可运行的示例：