问题标签 [set-cover]

我编写了这个程序来测试“解决”集合覆盖问题需要多长时间。

这只是一个贪婪的次优解决方案，但仍然需要 147 秒才能运行。然而，我认为这个解决方案应该非常接近最优，所以它应该足以满足我的目的。我怎样才能加快速度呢？

我注释掉了几行，因为它们弊大于利。编辑：计算宇宙实际上不应该是时间的一部分……这可以事先知道。

我有以下情况（对于长度的初步道歉，但我想尽可能描述）：

我收到了一份“食谱”（Ri）列表，必须按照给出的顺序完成，才能完成给定的任务。每个配方都包含完成它所需的部分 (Pj) 列表。一个配方通常需要多达 3 或 4 个部分，但可能需要多达 16 个。示例配方列表可能如下所示：

• R1 = {P1}
• R2 = {P4}
• R3 = {P2，P3，P4}
• R4 = {P1，P4}
• R5 = {P1, P2, P2} //请注意，可能需要超过 1 个给定部分。（这里，P2）
• R6 = {P2，P3}
• R7 = {P3，P3}
• R8 = {P1} //请注意，配方可能会在列表中重复出现。（与 R1 相同）

最长的列表可能包含几百个食谱，但通常包含一些食谱的多次重复，因此消除相同的食谱通常会将列表减少到少于 50 个独特的食谱。

我有一组机器 (Mk)，每台机器都经过预编程（这种情况发生一次，在列表处理开始之前）以生产部分（或全部）可用类型的零件。

履行过程的迭代发生如下：

• 列表中的下一个配方将呈现给机器库。
• 在每台机器上，选择其中一个可用程序来生产此配方所需的零件之一，或者，如果此配方不需要它，则将其设置为“离线”。
• 转动“曲柄”，每台机器（尚未“离线”）吐出一个零件。
• 将曲柄转动一圈产生的零件组合起来就可以完成配方。顺序无关紧要，例如，履行配方{P1，P2，P3}与履行配方{P1，P3，P2}相同。

这些机器即时、并行运行，并且拥有无限的原材料，因此没有资源或时间/调度限制。机器组的大小 k 必须至少等于最长配方中元素的数量，因此与上述配方长度具有大致相同的范围（通常为 3-4，可能最多 16 个）。因此，在上面的示例中，k=3（由 R3 和 R5 的大小决定）似乎是一个合理的选择。

手头的问题是如何对机器进行预编程，以便银行能够完成给定列表中的所有食谱。机器库共享一个公共内存池，因此我正在寻找一种算法，该算法可以生成一种编程配置，以消除（完全或尽可能多地）机器之间的冗余，从而最大限度地减少总内存负载量。机器库大小 k 是灵活的，即，如果将机器数量增加到超过给定列表中最长配方的长度会为列表产生更优化的解决方案（但保持 16 的硬限制），那很好。

目前，我认为这是一个单成本问题，即每个程序需要相同数量的内存，尽管我希望将来可以灵活地添加每个程序的权重。在上面的示例中，考虑到所有配方，P1 最多出现一次，P2 最多出现两次（在 R5 中），P3 最多出现两次（在 R7 中），P4 最多出现一次，所以我理想地希望实现与此匹配的配置 - 只有一台机器配置为生产 P1，两台机器配置为生产 P2，两台机器配置为生产 P3，一台机器配置为生产 P4。对于上述示例，使用机器组大小 k=3 的一种可能的最小配置是：

• M1 被编程为产生 P1 或 P3
• M2 被编程为产生 P2 或 P3
• M3 被编程为产生 P2 或 P4

由于这里没有作业车间类型的约束，我的直觉告诉我这应该简化为一个集合覆盖问题——就像在设计数字系统中发现的最小单一集合覆盖问题一样。但我似乎无法将我对这些算法的（诚然有限的）知识适应这种情况。有人可以确认或否认这种方法的可行性，并且无论哪种情况，都可以向我指出一些有用的算法吗？我正在寻找可以集成到现有代码块中的东西，而不是像 Berkeley's Espresso 这样预先打包的东西。

谢谢！

给定一个包含元素 U = {1, 2, 3,...,n} 的全域和该全域中的多个集合 {S1, S2,...,Sm}，我们可以创建的最小集合是什么覆盖 m 个集合中的每个集合中的至少一个元素？

例如，给定以下元素 U = {1,2,3,4} 和集合 S = {{4,3,1},{3,1},{4}}，以下集合将涵盖至少一个每个集合中的元素：{1,4} 或 {3,4}，因此此处所需的最小集合为 2。

关于如何扩大规模以解决 m=100 或 m=1000 集的问题的任何想法？或者对如何用 R 或 C++ 编写代码的想法？

上面的样本数据，使用 R's library(sets)。

干杯

我有一个集合 I ={P1, P2, ..., Pm} 和 I 的 n 个有限子集，用 R1,R2,...,Rn 表示，如下所示：

R1 = {P1, P2}

R2 = {P2, P4}

R3 = {P2，P3，P4}

R4 = {P1，P2，P4}

……

其中 Pi 表示一个整数。

对于每个 Ri，我想计算其所有元素的乘积。我的目标是通过在 Ri (i=1,2,...,n) 之间共享一些公共部分来尽可能少地使用乘法和除法。

例如，如果我可以先计算 P2*P4，那么这个结果可以用于计算 R3 和 R4 的所有元素的乘积。

请注意，也允许除法。例如，我可以先计算 A=P1*P2*P3*P4，然后使用 A/P1 计算 R3 的所有元素的乘积，然后使用 A/P3 计算 R4。

如果我想使用最小乘法和除法来计算 I 的每个子集的所有产品，这是一个集合覆盖问题吗？NP完全？顺便说一句，您能否给出一个整数线性程序公式来描述它，就像这里一样。

任何建议将不胜感激！

社区编辑：附加假设：

• 允许除法，与乘法相同的成本
• 给定集合中没有重复的元素。例如R5 = {P1, P1, P1, P2}不允许

我最近正在研究一个我认为是集合封面问题的分支的问题。但是，我的问题中的集合数高达 2^n。而且我发现的近似算法似乎只有在没有太多集合的情况下才有效。我想知道是否存在适合 2^n 组的算法？

谢谢你的回答！！！

我正在尝试使用贪心算法实现集合覆盖问题的解决方案。

经典的贪心逼近算法是

我有两个部分的问题：

一种。反向执行算法是否是有效算法，即

湾。问题的本质是很容易得到 C 并且冗余集的数量有限（<5） - 在这种情况下，这个去除算法会表现得更好吗？

我有最常用的单词列表，这些单词来自 Google 公开的 ngram 数据。

我有：

6800 频繁 2 克 4800 频繁 3 克 2500 频繁 4 克 1100 频繁 5 克

一个示例 2 ngram 将类似于：

《狗》《一本书》《三把椅子》等

一个示例 5 ngram 类似于：“从前有”“从前有”“这是一个黑暗的和”等等。

我还有一个包含 2000 个常用词的列表。

1）我想从我的各种列表中找出最少数量的 ngram 组合包含频繁单词列表中最多的单词。

例如，如果我发现 200 个 2 克、40 个 3 克、50 个 4 克和 20 个 5 克使用了 1800 个常用词，那将是成功的。我把这些比率做了起来，但我想找到少于 500 个使用大部分单词的组合。

2）我还想从列表中找到包含最多单词的各种 ngram 组合的最少数量。

例如，如果我能找到 500 个使用超过 2000 个不同单词的 ngram，那就太好了。

我遇到的问题是我不知道该怎么做。我认为 hadoop 和 mapreduce 的方向是正确的......但任何帮助将不胜感激！

我想解决以下类型的最小集覆盖问题。所有列表仅包含 1 和 0。

我说如果您可以通过准确插入符号 来制作列表，则列表A涵盖了列表。BBAx

考虑所有 2^n 个长度为 1 和 0 的列表n和 set x = n/3。2n/3我会计算一组涵盖所有内容 的最小长度列表。

这是我开始的一种天真的方法。对于每个可能的长度列表，2n/3我创建了一组可以使用此函数（由 DSM 编写）从中创建的所有列表。

n = 6然后，我使用以下示例创建集合集。

我想从联合为allset = set(product([0,1], repeat=n)).

在这种情况下，set(all_fill([1,1,1,1],2)), set(all_fill([0,0,0,0],2)), set(all_fill([1,1,0,0],2)), set(all_fill([0,0,1,1],2))会做。

我的目标是解决问题n = 12。如果有帮助的话，我很乐意使用外部库，我希望在n最坏的情况下时间会成倍增长。

例如，已知集合覆盖决策问题是一个 NP 完全问题。这个问题的输入是一个全域 U、一个 U 的子集族 S 和一个整数 k()。

我感到困惑的一件事是，如果我们让 k=1，那么显然可以通过简单地检查 S 中的每个元素来及时解决问题 |S|。更一般地说，当 k 是常数时，问题可以在 |S| 的多项式时间内求解。这样，只有当 k 也随着 |S| 增加时，时间复杂度才会呈指数级增长，例如 |S|/2、|S|/3...

所以这是我的问题：

1. 我目前的理解是，NP完全问题的时间复杂度测量是根据最坏情况来测量的。谁能告诉我理解是否正确？

2. 我看到有人证明了另一个问题是 NP 难的，他证明输入的集合覆盖决策问题<U,S,|U|/3>可以简化为该问题。我只是想知道为什么他只证明了<U,S,|U|/3>，而不是<U,S,ARBITRARY k>？？这样的证明可靠吗？

非常感谢！

我有一个通用集和集数 S。我需要从 S 中找到最大集数，以便在任何选定的两个集之间没有共同元素。

我的方法---我将 S 中的每个集合视为一个节点，如果两个集合之间有任何共同元素，那么这两个集合之间就会有一条边。如果构造的图是二分的，这种方法可以正常工作。我有如果构造的图不是二分的，则难以解决。

PS-选择集不一定要覆盖全集的所有元素。它应该返回不相邻的最大集合数。

谢谢