在集合覆盖问题中，我们被赋予一个论域U，使得|U|=n和集合S1，……，Sk是U的子集。集合覆盖是来自S1，……的一些集合的集合C，Sk，其并集是整个宇宙U。我正在尝试想出一个算法，它可以找到最小数量的集合覆盖，这样我就可以证明，贪婪的集合覆盖算法有时会找到更多的集合。对每个集合重复此操作。
浏览 5提问于2010-11-26得票数 1
回答已采纳
2回答
有没有人可以提供一个回溯算法来解决“集合覆盖”问题，以找到覆盖宇宙中所有元素的最小集合数量？
贪婪方法几乎总是选择比最佳集合数量更多的集合。
浏览 2提问于2010-10-30得票数 1
1回答
关于我的集合的详细信息:每个集合都有精确的M元素，并且每个元素都完全属于N集。有好的算法吗？(为我的特例)
谢谢。
浏览 2提问于2011-07-27得票数 0
回答已采纳
1回答
是一个问题，您必须找到覆盖每个元素所需的最小集合数量。S[2] = array(2, 5) S[4] = array(1, 2, 3) 问题是找到覆盖X的每个元素的S的最小集合数量。因此，很明显，在我们的例子中，最小集合覆盖将是S[4]和S[5]，因为它们覆盖了所有元素。有人知道如何在C++中实现这段代码吗？请注意，这
浏览 10提问于2015-01-05得票数 1
每个这样的集合由两个数字定义。例: 2,5表示包含2,3,4,5的集合。我们必须打印最小编号。为了覆盖所有N个集合而选择的数字的数量。答:不是。如果集合包含在集合中，则称为覆盖集合。例如:给定集合2,5，3,4，10,100。我们可以选择例如{3,10}，这样我们就覆盖了所有3个集合。因此，答案是2。
我找不到适用于N<=5000的算法。
浏览 6提问于2014-12-08得票数 2
2回答
我正在开发一个应用程序，对于这个应用程序，我希望取M中所有可能的k-元素组合的集合C( ||M|| = m)，并用M的子集N_i的k-组合的集合覆盖C，其中||N_i|| =n<m- N_i∀
因此有(m选择k)个组合要覆盖，每个包含n个元素的集合Q_i将包含(n选择k)个组合。我想要的是一个算法，它可以构造集合Qi，使得Q最小化(即尽可能接近(m choose k) / (n choose k) )。例如，如果m=100，k=3和n=
浏览 1提问于2012-05-31得票数 1
回答已采纳
2回答
我想知道如何处理类似的问题：
你必须在图的节点上放置摄像头，这样整个图都会被覆盖。节点上的摄像机监视其所有紧邻节点和自身。找到覆盖所有节点所需的最小摄像头数量。
浏览 23提问于2019-11-11得票数 1
回答已采纳
2回答
老师六月份有每个人的可用时间，并且希望安排尽可能少的课程来覆盖每个人。我能想到的就是将其建模为一个最小集合覆盖问题，其中每个集合代表一个特定的日期，每个节点代表一个学生。目标是选择最小数量的集合，以便覆盖每个节点。
既然最小集覆盖没有多项式解(而不是近似解)，那么这个问题是否有多项式解？
浏览 4提问于2022-06-17得票数 2
回答已采纳
我一直在尝试解决两个不同的问题：2)我想要解决的第二个问题与上面的类似，但我不想描述R的全部，而是只想描述R的子集T，而不描述R的任何其他元素。此外，允许的操作包括集合并和集合差以及L中元素的邻域的集合</e
浏览 16提问于2017-07-19得票数 0
回答已采纳
1回答
我不确定在这里寻求关于算法的帮助是否合适，但是谁能给我一些指导，或者告诉我在哪里可以找到这样的指导？非常感谢!问题是这样的:给定固定数量的圆，我需要一个算法来找到这些圆的位置和半径的最佳集合来覆盖给定的形状，因此误差区域(给定形状之外的圆的部分+这些圆未覆盖的形状的部分)是最小的？圆圈可以重叠。
浏览 18提问于2013-05-29得票数 1
4回答
完全断开二部图的连接
、、、、
任务是最小化要删除的节点数量。图中的每个节点最多有4条边。
通过完全断开一个图，我的意思是不应该通过链接连接两个节点。基本上是一个空的边集。
浏览 1提问于2012-08-07得票数 4
回答已采纳
3回答
1 1 1 1 11 1 1 1 1 1 10 0 0 1 1 1 0我希望找到与x和y轴平行的矩形集，它至少覆盖每个1一次，而不是覆盖一个具有最小基数(最小矩形数量)的0。在上面的示例中，这将是矩形((0, 3), (6, 5))和((3, 0), (5, 8)) (表示法以(topleft, bottomright)形式表示)--最小的解决方案是使用两个矩形。我之前的尝试是找出最大面积仅覆盖1的
浏览 2提问于2012-07-17得票数 4
1回答
我在试着找最小加权顶点覆盖。例如，如果我有一个大小为10的顶点覆盖，但每个节点的权重为10，则总覆盖的权重为100。但是如果我有一个大小为99的顶点覆盖，每个节点的权重为1，那么我会选择这个覆盖而不是前一个。我认为这是NP完全的，所以没有有效的算法，但我认为即使是详尽的搜索对我来说也是可行的，因为节点的数量将相对较少。我想要做到这一点的唯一方法是生成集合的幂集合，然后测试每个单独的集合，看看它是否是1)有效的顶点<e
浏览 2提问于2012-08-21得票数 2
回答已采纳
1回答
我正在努力寻找一种算法，它将找到资源的最优使用。List_1有3引脚，可以放置在point_a或point_cList_4有2引脚，可以放置在point_a
我正在试图找到最小数量的点，我可以使用它来满足所有4列表。
浏览 3提问于2019-11-12得票数 1
回答已采纳
1回答
要找到无向图G的最小支配集，可以使用如下贪心算法:从一个空集D开始，直到D是一个支配集，添加一个具有最大未覆盖邻居数的顶点v。该算法一般不会找到最优解，它是一个ln(增量)-approximation。(如果增量是G中顶点的最大次数)有人知道一个小例子吗？
提前感谢
浏览 6提问于2012-06-04得票数 4
回答已采纳
1回答
我想我正在寻找一种算法，它可以在二分图中找到“最小”的“选择”。每个顶点有一个相关的(整数)成本来选择它。我只能找到将所选集合中的顶点数目最小化的算法，而不是代价。我以前以为我需要一个“匹配”，但实际上我只需要覆盖每个边的顶点子集.顶点1, 2 ,3在A中，有1。顶点4在B中，有2。我想出了一种不同的措辞：“给定一个二分图，其中每个顶点都有一个相关的代价，找到一个最小代价顶点的子集，这样每个边都
浏览 0提问于2013-04-06得票数 1
回答已采纳
1回答
不同的最小可能覆盖的数目是多少？
、、、、
不同最小覆盖可能的are___________的数目？
2) AC->G，D->E，D->G，BC->D，CG->D，CD->B(#)，CE->A实际上，视
浏览 3提问于2020-01-06得票数 0
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
即时通信 IM
实时音视频活动推荐
腾讯云开发者
