腾讯云
开发者社区
文档
建议反馈
控制台
登录/注册
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
搜索
搜索
关闭
发布
精选内容/技术社群/优惠产品,
尽在小程序
立即前往
文章
问答
(9999+)
视频
沙龙
2
回答
理解多项式TIme逼近格式
、
近似算法
是否与多项式时间
近似算法
(PTAS)相同?例如,可以证明A(I) <= 2*选择(I)作为顶点
覆盖
。这是否意味着顶点
覆盖
有2-多项式时间
近似算法
或PTAS? 谢谢!注意:斜体字
的
文本是我在发布问题后所做
的
编辑。
浏览 3
提问于2014-04-19
得票数 1
回答已采纳
1
回答
顶点
覆盖
的
非确定性算法
、
、
在我
的
课堂测验中,我遇到了一个问题,那就是写一个顶点
覆盖
的
非确定性算法。我们和我们
的
老师讨论了解决方案,他告诉我们,水平
的
不确定性不应该太高。这应该是明智
的
好消息。我很困惑,我应该问什么问题,对不确定
的
计算机?
浏览 8
提问于2015-11-24
得票数 0
回答已采纳
1
回答
基于“生成树”
的
顶点
覆盖
问题
的
2-
近似算法
、
、
、
我看过一个关于顶点
覆盖
问题(VC,已知
的
Np-完全问题)
的
2-
近似算法
的
问题,但我不知道答案。问题如下:使用“生成树”为顶点
覆盖
问题找到一个2-
近似算法
。对于VC,已经提出了许多贪婪
的
方法,但是使用“生成树”
的
特殊算法是具有挑战性
的
。有什么想法吗?
浏览 11
提问于2011-02-01
得票数 4
1
回答
顶点
覆盖
的
逼近算法
、
、
、
、
如果P不等于NP,那么是否可以证明在最优顶点
覆盖
的
k中没有
近似算法
,其中k是一个固定常数?
浏览 2
提问于2017-04-07
得票数 1
回答已采纳
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
回答
.NET框架-每个应用程序
的
开销
、
、
有没有人有关于使用.NET Framework2.0/3.0/3.5开销
的
具体信息?我
最
感兴趣
的
是每个实例
的
开销,以及是否存在与实例数量无关
的
“固定成本”,例如,在运行300个.NET框架应用程序实例
的
终端服务环境中,是否只有1个即时编译器实例?如果我得到一个
近似算法
,那就太好了,例如每个实例10mb + JIT
的
50mb
浏览 1
提问于2010-03-05
得票数 3
回答已采纳
1
回答
当有太多
的
集合,比如2^n集合时,集合
覆盖
中有没有
近似算法
?
、
我最近正在研究一个问题,我认为它是集合
覆盖
问题
的
一个分支。然而,在我
的
问题中,集合
的
数量高达2^n,而且我所发现
的
近似算法
似乎只有在集合不太多
的
情况下才有效。我想知道有没有适合2^n集
的
算法?感谢您
的
回复!
浏览 7
提问于2012-06-20
得票数 2
回答已采纳
1
回答
Set Cover -几个不同
的
版本
我一直在处理一个具有两组顶点L和R以及一个边集E
的
二部图。我一直在尝试解决两个不同
的
问题: 1)简单集
覆盖
问题(即找到L中最小
的
顶点基数子集,使得该子集
的
邻域包含所有R)。据我所知,这个问题被称为命中集问题,等同于集合
覆盖
问题,并且存在一些
近似算法
。我想知道你会推荐哪种
近似算法
,我在网上找到了几种不同
的
算法。2)我想要解决
的
第二个问题与上面的类似,但我不想描述R
的
全部,而是只想描述R
的</e
浏览 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
回答
寻找
覆盖
所有段
的
最
小点
数
、
、
、
、
,具有整数坐标的an-1,bn-1},求出点
的
最小数目m,使每个段至少包含一个点。也就是说,找到一组最小大小
的
整数X,这样对于任何段ai,bi都有一个点x∈x,使得ai≤x≤bi。输入格式:输入
的
第一行包含段数n。以下n行中
的
每一行都包含两个整数ai和bi (用空格分隔),它们定义了第一段端点
的
坐标。 输出格式:输出第一行点
的
最小数目m和第二行m点
的
整数坐标(用空格分隔)。如果有许多这样
的
点集,您可以输出任何集合。(不难看出,总是存在一组最小大小<em
浏览 11
提问于2022-04-18
得票数 3
回答已采纳
1
回答
计算
覆盖
像素差
的
矩形集?
、
、
我想开发一个类似于动画gifs
的
网络动画系统,比如这一个。我在固定
的
时间间隔捕捉一系列
的
截图,然后我想给它们动画。我可以微乎其微地计算从一个帧到另一个帧之间变化
的
像素,但是我想计算一组矩形,以便将这些矩形在前一帧上进行裁剪,得到新
的
矩形。在矩形数和“浪费”像素数之间有一种权衡,即存储和复制
的
像素数在两个帧之间没有变化。有一个很好
的
算法可以让我在某种形式上控制权衡参数吗?
浏览 0
提问于2017-11-06
得票数 2
1
回答
整数线性规划与线性规划
的
界原理
、
、
目前,我正在学习
近似算法
。当我通过LP学习顶点
覆盖
时,我遇到了一个叫做边界原则
的
原则。它是这样
的
:用于LP松弛
的
最大ILP≤最大值用于LP松弛
的
ILP≥MIN 我不明白为什么
浏览 6
提问于2013-11-12
得票数 0
回答已采纳
1
回答
Android -屏幕顶部未显示
、
、
、
当我在模拟器/我
的
设备上运行我
的
应用程序时,我遇到了一点问题。
浏览 5
提问于2015-12-03
得票数 0
2
回答
列出被给定半径
的
圆包围
的
所有点集
、
、
我
的
问题是:给定一个平面上
的
N个点和一个数字R,列出/枚举所有点
的
子集,其中每个子集中
的
点被半径为R
的
圆所包围。两个子集应该是不同
的
,并且不能相互
覆盖
。谢谢,因此,我重申我
的
问题如下:给定N个点和一个具有固定半径R
的
圆,使用该圆
浏览 0
提问于2015-06-27
得票数 0
0
回答
查找
覆盖
整个区间集
的
最
小点
数
、
、
这个问题以前已经问过了,现在
的
答案是根据结束时间对间隔进行排序。我
的
问题是,为什么按开始时间排序是错误
的
?这是我写
的
代码- int start; }; s=i[j]; } }} 如果我更改我<e
浏览 5
提问于2018-07-15
得票数 1
2
回答
有算法在多项式时间内求k-tsp (旅行商)
的
最优值吗?
、
、
我读了
的
文章,它建议(第1025页最后一段)有一个多项式时间算法来寻找一个k-tsp问题
的
最优使用二进制搜索。我搜索了一下这个算法,唯一能找到
的
算法是非确定性算法(这非常微不足道),但很明显,我正在寻找一个确定性算法。如有任何帮助/链接,将不胜感激。编辑 我指的是寻找最优解
的
价值,而不是寻找最优解本身。
浏览 6
提问于2011-12-22
得票数 1
回答已采纳
2
回答
搜索
覆盖
区域最
小点
数
的
算法(战争游戏)
、
我有一个我
的
基地,B(x,y),我可以发送攻击敌人
的
名单(他们在我自己
的
基地之间有基地)。每个基地B都可以在一个R范围内攻击(所有基地
的
半径相同)。我怎么能找到我
的
基地能够攻击尽可能多
的
敌人基地,但使用我
的
基地
的
最小数量? 我将问题简化为找到
覆盖
最大区域所需
的
最小基地数(及其坐标)。我想知道是否有一个更好
的
方法比观察所有可能
的
组合,因为基地
的
数目可能达到数千。例子
浏览 6
提问于2014-10-10
得票数 0
回答已采纳
1
回答
最小顶点
覆盖
问题的确定性解- NP完全是好
的
、
、
、
、
一个顶点
覆盖
问题是为一个无向图G= (V,E)寻找一个ψ∈V
的
集合,使得如果{u,v}∈E,则u∈ψ或v∈ψ或两者都有。给出了这个问题
的
定义,并证明了它是NP完全
的
。有没有确定性
的
算法可以解决这个问题?指数运行时间是可以接受
的
,但是有没有更好的确定性算法呢?并且只有一种方法。我不是在寻找可以在较短时间内运行
的
近似解-据我所知,在Cormen,Leiserson,Rivest和Stein (CLRS)文本
的
第35章中列出
的
是一种
浏览 4
提问于2020-06-20
得票数 0
点击加载更多
扫码
添加站长 进交流群
领取专属
10元无门槛券
手把手带您无忧上云
相关
资讯
全球“最支持”华为的国家!依靠华为“全境覆盖”5G,世界的榜样
这是我见过最方便的丁字账系统了,函数公式覆盖,自动生成报表
最年长大熊猫37岁!长三角铁路“刷脸进站”覆盖的地区和范围扩充至40个城市65个火车站!
传奇世界复古版本:游戏中那些鸡肋的功能以及机制
LED灯杆屏商显市场鼎力革新,促LED显示屏整体稳定发展
热门
标签
更多标签
云服务器
ICP备案
实时音视频
云直播
对象存储
活动推荐
运营活动
广告
关闭
领券