1回答
要找到无向图G的最小支配集，可以使用如下贪心算法:从一个空集D开始，直到D是一个支配集，添加一个具有最大未覆盖邻居数的顶点v。该算法一般不会找到最优解，它是一个ln(增量)-approximation。(如果增量是G中顶点的最大次数)有人知道一个小例子吗？
提前感谢
浏览 6提问于2012-06-04得票数 4
回答已采纳
最小加权顶点覆盖问题的一个著名的2-近似是由Clarkson提出的：
放大图片创作者:J.“对用于顶点覆盖的贪心算法的修改。”资讯处理通讯16.1 (1983)：23-25。简单易读的算法伪代码可以在中找到，见32.1.2节。根据这篇论文，该算法的运行时复杂度为O(|E|*log|V|)，其中E是边的集合，V是顶点的集合。我不完全确定他们是如何得到这个结果的。排除算法中的一些技术细节，算法看起来像这
浏览 17提问于2016-07-30得票数 0
回答已采纳
在集合覆盖问题中，我们被赋予一个论域U，使得|U|=n和集合S1，……，Sk是U的子集。集合覆盖是来自S1，……的一些集合的集合C，Sk，其并集是整个宇宙U。我正在尝试想出一个算法，它可以找到最小数量的集合覆盖，这样我就可以证明，贪婪的集合覆盖算法有时会找到更多的集合。对每个集合重复此操作。
浏览 5提问于2010-11-26得票数 1
回答已采纳
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回答
有没有人可以提供一个回溯算法来解决“集合覆盖”问题，以找到覆盖宇宙中所有元素的最小集合数量？
贪婪方法几乎总是选择比最佳集合数量更多的集合。
浏览 2提问于2010-10-30得票数 1
1回答
给定一个有限的整数集S {s1,s2,s3...sz}，求出包含S中所有整数的C的最小子集的大小。有没有人能为这个问题提出一个快速算法？
浏览 1提问于2012-08-26得票数 3
回答已采纳
1回答
关于我的集合的详细信息:每个集合都有精确的M元素，并且每个元素都完全属于N集。有好的算法吗？(为我的特例)
谢谢。
浏览 2提问于2011-07-27得票数 0
回答已采纳
每个这样的集合由两个数字定义。例: 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回答
DFS贪婪色数
、、、
在我的学校里，我学到了计算任意图的色数是NP-完全的.我理解为什么greddy算法不能工作，但是DFS/贪心算法呢？其主要思想是对所有尚未着色的顶点进行DFS，对所有邻居进行最小颜色索引。
浏览 3提问于2016-04-14得票数 2
回答已采纳
2回答
我想知道如何处理类似的问题：
你必须在图的节点上放置摄像头，这样整个图都会被覆盖。节点上的摄像机监视其所有紧邻节点和自身。找到覆盖所有节点所需的最小摄像头数量。
浏览 23提问于2019-11-11得票数 1
回答已采纳
2回答
老师六月份有每个人的可用时间，并且希望安排尽可能少的课程来覆盖每个人。我能想到的就是将其建模为一个最小集合覆盖问题，其中每个集合代表一个特定的日期，每个节点代表一个学生。目标是选择最小数量的集合，以便覆盖每个节点。
既然最小集覆盖没有多项式解(而不是近似解)，那么这个问题是否有多项式解？
浏览 4提问于2022-06-17得票数 2
回答已采纳
0回答
贪心算法的复杂性
、、、
我做了一个求解最小加权哈密顿电路的贪心算法problem.The算法总是选择最便宜的边，如果没有办法从当前边集中找到电路，那么该算法丢弃最后一个边，然后选择下一个最便宜的边。我不确定这个算法的复杂性，有人能给我解释一下吗?
浏览 8提问于2016-12-19得票数 0
问题是从数组中找到最小数量的元素，这将导致与原始数组相同的OR。
例如arr[] = {1,2,3,4,6}。或者数组中的所有值的值都是7的。如果我们只考虑元素6,1或它，我们得到7。所以答案是2。
浏览 37提问于2018-06-06得票数 0
我一直在尝试解决两个不同的问题：2)我想要解决的第二个问题与上面的类似，但我不想描述R的全部，而是只想描述R的子集T，而不描述R的任何其他元素。此外，允许的操作包括集合并和集合差以及L中元素的邻域的集合</e
浏览 16提问于2017-07-19得票数 0
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
即时通信 IM
腾讯会议活动推荐
腾讯云开发者
