2回答
近似算法是否与多项式时间近似算法(PTAS)相同？例如，可以证明A(I) <= 2*选择(I)作为顶点覆盖。这是否意味着顶点覆盖有2-多项式时间近似算法或PTAS？
谢谢!
浏览 3提问于2014-04-19得票数 1
回答已采纳
1回答
在我的课堂测验中，我遇到了一个问题，那就是写一个顶点覆盖的非确定性算法。我们和我们的老师讨论了解决方案，他告诉我们，水平的不确定性不应该太高。这应该是明智的好消息。
浏览 8提问于2015-11-24得票数 0
回答已采纳
1回答
我看过一个关于顶点覆盖问题(VC，已知的Np-完全问题)的2-近似算法的问题，但我不知道答案。问题如下:使用“生成树”为顶点覆盖问题找到一个2-近似算法。
浏览 11提问于2011-02-01得票数 4
1回答
我开始学习近似算法，我正在读一本关于这方面的书，但我不理解集合覆盖算法的分析。
有人能解释一下引理2.3吗？它很短，但我不理解它。
浏览 1提问于2012-02-11得票数 0
回答已采纳
1回答
给定一组区间，[x,y] where 0 <= x,y <= 2000如何求出能覆盖的最小点数(即每个区间至少包含一个点集)，所有区间？示例： [2,5] [7,10]
那么答案应该是2(覆盖所有间隔所需的最小点数)，因为点x=3,x=7是一个解决方案。
浏览 2提问于2015-01-03得票数 10
回答已采纳
2回答
我要解决的问题是：请注意，如果直线段的任何部分都不在圆之外，则该直线段将被覆盖。任何指向论文或代码或近似算法的指针都会很棒。
浏览 0提问于2016-11-23得票数 3
1回答
我最感兴趣的是每个实例的开销，以及是否存在与实例数量无关的“固定成本”，例如，在运行300个.NET框架应用程序实例的终端服务环境中，是否只有1个即时编译器实例？如果我得到一个近似算法，那就太好了，例如每个实例10mb + JIT的50mb
浏览 1提问于2010-03-05得票数 3
回答已采纳
我最近正在研究一个问题，我认为它是集合覆盖问题的一个分支。然而，在我的问题中，集合的数量高达2^n，而且我所发现的近似算法似乎只有在集合不太多的情况下才有效。我想知道有没有适合2^n集的算法？
浏览 7提问于2012-06-20得票数 2
回答已采纳
我一直在尝试解决两个不同的问题：2)我想要解决的第二个问题与上面的类似，但我不想描述R的全部，而是只想描述R的子集T，而不描述R的任何其他元素。
浏览 16提问于2017-07-19得票数 0
回答已采纳
2回答
@mhum建议我的问题属于覆盖问题领域。我尝试将我的问题编码为一个最小集覆盖问题，目前我有一个数据集中在以下形式：(1,2) 1(1,2,3) 2(3,4) 2(1,2) 3(1,2,3,4) 4
我们的目标是找到一个涵盖所有数字的良好的集合覆盖
浏览 3提问于2011-10-29得票数 7
回答已采纳
1回答
我想开发一个类似于动画gifs的网络动画系统，比如这一个。我在固定的时间间隔捕捉一系列的截图，然后我想给它们动画。我可以微乎其微地计算从一个帧到另一个帧之间变化的像素，但是我想计算一组矩形，以便将这些矩形在前一帧上进行裁剪，得到新的矩形。在矩形数和“浪费”像素数之间有一种权衡，即存储和复制的像素数在两个帧之间没有变化。有一个很好的算法可以让我在某种形式上控制权衡参数吗？
浏览 0提问于2017-11-06得票数 2
2回答
两个子集应该是不同的，并且不能相互覆盖。在一种特殊情况下，我们能找到K个点最多的子集吗？可以接受近似算法。编辑:这句话看起来不太明白。我的错！一次，圆将覆盖点的子集。目标是列出这样的R半径圆可以覆盖的所有可能的点子集。一个子集不能是其他子集的超集。
浏览 0提问于2015-06-27得票数 0
1回答
在屏幕的顶部有一个蓝色的矩形，它覆盖了一个下拉菜单(三个小点)。我想知道有没有人知道这是什么或者怎么摆脱它。
浏览 5提问于2015-12-03得票数 0
我读了的文章，它建议(第1025页最后一段)有一个多项式时间算法来寻找一个k-tsp问题的最优使用二进制搜索。使用二进制搜索将意味着有一个算法，以检查是否存在一个解决方案与cost<X，该算法用于二进制搜索。我搜索了一下这个算法，唯一能找到的算法是非确定性算法(这非常微不足道)，但很明显，我正在寻找一个确定性算法。如有任何帮助/链接，将不胜感激。我指的是寻找最优解的价值，而不是寻找最优解本身。
浏览 6提问于2011-12-22得票数 1
回答已采纳
0回答
这个问题以前已经问过了，现在的答案是根据结束时间对间隔进行排序。我的问题是，为什么按开始时间排序是错误的？这是我写的代码- int start; }; { } int t; while(t--) int n,c;
cin>>n>&
浏览 5提问于2018-07-15得票数 1
1回答
一个顶点覆盖问题是为一个无向图G= (V，E)寻找一个ψ∈V的集合，使得如果{u，v}∈E，则u∈ψ或v∈ψ或两者都有。给出了这个问题的定义，并证明了它是NP完全的。我不是在寻找可以在较短时间内运行的近似解-据我所知，在Cormen，Leiserson，Rivest和Stein (CLRS)文本的第35章中列出的是一种近似算法。
浏览 4提问于2020-06-20得票数 0
我将问题简化为找到覆盖最大区域所需的最小基地数(及其坐标)。我想知道是否有一个更好的方法比观察所有可能的组合，因为基地的数目可能达到数千。例子:如果攻击半径是10，而我在一个正方形和它的中心有五个基地：(0,0)，(10,0)，(10,10)，(0,10)，(5,5)，那么答案是只需要前四个，因为中心的一个区域已经被其他的区域覆盖了。
浏览 6提问于2014-10-10得票数 0
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
腾讯会议
实时音视频活动推荐
腾讯云开发者
