腾讯云
开发者社区
文档
建议反馈
控制台
登录/注册
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
搜索
搜索
关闭
发布
精选内容/技术社群/优惠产品,
尽在小程序
立即前往
文章
问答
(9999+)
视频
沙龙
1
回答
找到至少最
大团
大小- 1的次极
大团
是NP-完全的吗?
、
、
、
众所周知,在图中寻找极
大团
是NP-完全
问题
.但我不知道是否有可能在多项式时间内找到图中的子极
大团
。也就是说,考虑到我们不知道是否存在P=NP,是否有一个多项式
算法
会给出一个团的大小是,至少是,最
大团
大小减去1?我猜答案是“不”,因为我知道没有多项式时间
算法
可以给出一个大小正好是的最
大团
大小减去1的团,否则我就会知道这个
算法
在多项式时间内的最
大团
的大小,如果P!=NP的话,这是不可能的。但我不知道如何证明,当我们期望
算法</em
浏览 12
提问于2022-04-30
得票数 0
0
回答
贪心
算法
的复杂性
、
、
、
我做了一个求解最小加权哈密顿电路的
贪心
算法
problem.The
算法
总是选择
最
便宜的边,如果没有办法从当前边集中找到电路,那么该
算法
丢弃最后一个边,然后选择下一个
最
便宜的边。我不确定这个
算法
的复杂性,有人能给我解释一下吗?
浏览 8
提问于2016-12-19
得票数 0
1
回答
旅行推销员-为什么贪婪的
算法
不能保证给出最优解决方案?
、
为什么没有
贪心
算法
可以保证给出旅行推销员
问题
的最优解?有没有这样的例子?
浏览 1
提问于2017-04-03
得票数 0
1
回答
找到完全连接的部件?
、
、
、
但是,图中有一些寻找强连通分量的
算法
(例如Tarjan的
算法
),是否有一种
算法
可以找到这样的“完全连通的分量”?
浏览 4
提问于2016-05-18
得票数 4
1
回答
无向图中求极
大团
的Bron
算法
、
、
我试图理解Bron的
算法
(带旋转),以求无向图中的最
大团
。我有一些
问题
: 选择一个枢轴顶点有什么标准吗?该
算法
不对所有顶点进行旋转检查,以确定其是否形成一个团,而具有旋转的
算法
只检查P \ N(u)中必须包含的顶点,以形成一个最
大团
。这样,如果找到一个非最
大团
,
算法
就可以立即回溯,而不是在永远不会形成最
大团
的顶点上执行不必要的递归。我的理解正确吗?
浏览 6
提问于2021-04-09
得票数 3
回答已采纳
1
回答
如何在Neo4J中找到所有的极
大团
?
、
、
、
我希望找到至少有k个节点的所有极
大团
(认为边是无向的)。有没有cypher查询或neo4j插件可以帮到我?有没有其他方法来解决这个
问题
呢?
浏览 3
提问于2021-06-08
得票数 0
2
回答
Java:如何在尽可能小的表面上绘制图像?
、
、
、
假设我有256张图像,平均大小为70x150 (因此,如果大小可变)。我有一个Graphic-instance (从具有给定大小的BufferedImage创建),我想在上面绘制图像。但我想把它们画在尽可能低的曲面上。所以,不是简单地在网格中,而是在彼此之间真正感到困惑。但是!:它们不能相互重叠。我想,这是值得一问的……马提金+------++------+| img1 || img2 || |+-----------------+ +------+|
浏览 0
提问于2010-12-14
得票数 2
2
回答
查找图中的所有完全子图
、
、
是否有一种已知的
算法
或方法可以在图中找到所有完整的子图?我有一个无向、无权重的图,我需要找到其中每个子图中的每个节点都与子图中的其他节点相连的所有子图。 有没有现成的
算法
来解决这个
问题
呢?
浏览 4
提问于2010-05-10
得票数 22
回答已采纳
1
回答
如何用
贪心
算法
解决0/1背包
问题
而只关注效益?
、
我需要用
贪心
算法
写C++来解决0/1背包
问题
。因为这是一个NP完全
问题
,所以我们只能找到最近的解决方案。
浏览 11
提问于2018-06-08
得票数 -3
2
回答
贪心
算法
解决以下
问题
、
我正在尝试使用贪婪
算法
来解决以下
问题
,这就是我的想法,我们试着让互不相识的人成对,并给他们相同的礼物。但我不确定这是否是贪婪的
算法
。有人能提出一个贪婪的
算法
来解决这个
问题
吗?
浏览 2
提问于2013-04-18
得票数 1
回答已采纳
1
回答
N维上的最小覆盖半径
、
、
、
有没有什么已知的
算法
可以解决这个
问题
?
浏览 2
提问于2016-11-02
得票数 0
1
回答
从给定的二部图中找出所有极大完全二部子图
、
d,e}最大完全二部图是:{C,D}-{c,d}我找到了一个强力
算法
我不知道是某种近似
算法
还是随机化
算法
。
浏览 2
提问于2013-03-29
得票数 6
回答已采纳
1
回答
寻求0-1多维背包的最大容量利用率
、
Stackexchange链接中提供了一个很好的
算法
:。 但是,如果我的目标函数是在背包中装入尽可能多的物品呢?所有的部分都有相同的价值。Stackexchange post ()声称等值的一维背包可以用
贪心
算法
求解。这是真的吗?我认为01背包
问题
是NP难的,因此贪婪
算法
可能不会给出最优解。所以我的
问题
分为两部分: 1)在这种情况下,贪婪
算法
能给出最优解吗? 01等值背包2)如何实现多维贪婪
算法
?vi/wi是一个值除以一个向量...
浏览 1
提问于2016-04-08
得票数 0
2
回答
边缘团覆盖
算法
、
、
、
、
我试图编写一个
算法
来计算输入图(无向和无自循环)的边团覆盖数(覆盖所有边的最小团数)。我的想法是 有谁知道一个更好的方法吗?有标准的
算法
吗?令我惊讶的是,我找不到任何这样的
算法
。我知道这个
问题
是NP难的,所以我不期望有一个快速的解决方案。
浏览 2
提问于2018-03-06
得票数 3
回答已采纳
2
回答
寻找最大双线
我有一个
问题
,我可以将其建模为在二部图中寻找最大二色(完全二部图)。我知道Bron-Kerbosch
算法
用于检测最
大团
,在我看来,应该有一种方法来表示两团
问题
为团
问题
。有没有人有一个解决方案,既可以形成一个集团
问题
,也可以作为直接检测双集团的有效
算法
?
浏览 3
提问于2010-06-18
得票数 5
回答已采纳
2
回答
在加权图C#实现中查找最大权重团
、
、
在C#中有没有在加权图中找到最大权重团的免费实现?
浏览 2
提问于2011-06-03
得票数 1
回答已采纳
1
回答
从矩阵中选择点的
算法
、
、
这似乎是一个简单的
问题
,但我被这个
问题
卡住了。
问题
是我有一个大小为X x Y的矩阵。在(i,j)处可能有一些点。然而,并非所有位置(i,j)都应该具有点(即,存在< XY点)。
浏览 0
提问于2011-11-17
得票数 1
回答已采纳
4
回答
贪婪
算法
的最佳复杂度是什么?
、
、
无关紧要,我说的是贪婪的
算法
。在我感兴趣的具体情况下,我感兴趣的是计算变化。 假设你需要找35美分的零钱。你有1,5,10,25的硬币。
贪心
算法
,编码简单,可以快速、轻松地解决这个
问题
。首先抓取25美分,最高值在35,然后是10美分,以完成总数。这将是最好的情况。当然,在一些糟糕的情况下,这种贪婪
算法
也会有
问题
。我说的是确定这类
问题
的最佳案例复杂性。
浏览 5
提问于2011-10-10
得票数 2
回答已采纳
1
回答
支配集贪婪逼近最坏情况示例
、
、
、
要找到无向图G的最小支配集,可以使用如下
贪心
算法
:从一个空集D开始,直到D是一个支配集,添加一个具有最大未覆盖邻居数的顶点v。该
算法
一般不会找到最优解,它是一个ln(增量)-approximation。(如果增量是G中顶点的最大次数)有人知道一个小例子吗? 提前感谢
浏览 6
提问于2012-06-04
得票数 4
回答已采纳
2
回答
DFS贪婪色数
、
、
、
在我的学校里,我学到了计算任意图的色数是NP-完全的.我理解为什么greddy
算法
不能工作,但是DFS/
贪心
算法
呢?其主要思想是对所有尚未着色的顶点进行DFS,对所有邻居进行最小颜色索引。我想不出一个反例,这个
问题
让我大吃一惊。谢谢你所有的回答。
浏览 3
提问于2016-04-14
得票数 2
回答已采纳
点击加载更多
扫码
添加站长 进交流群
领取专属
10元无门槛券
手把手带您无忧上云
相关
资讯
贪心算法:括号的平衡配对问题
C+趣味问题丨如何利用贪心算法实现搬水果问题?
C+算法主题系列之贪心算法的贪心之术
什么是贪心算法?详述贪心算法的原理?用C语言实现贪心算法。内附完整代码。
python 贪心算法例子
热门
标签
更多标签
云服务器
ICP备案
实时音视频
对象存储
云直播
活动推荐
运营活动
广告
关闭
领券