5回答
NP-完全的定义是
那么，如果NP中的所有其他问题都转化为NP -完全问题，那么这不也意味着所有NP问题也都是NP-完全问题吗？换句话说，如果我们有一个NP问题，那么通过(2)这个问题可以转化为NP-完全问题。因此，NP
浏览 16提问于2011-09-09得票数 5
回答已采纳
我有以下算法问题： 如果我有一个图G=(V，E)，G是否有一个恰好有k个叶子的生成树？叶子是在生成树中只有一个邻居的顶点。另外，我不是在寻找最小的生成树，而是一个生成树。总而言之，解决算法将接受一个图G和一个数字k作为输入，并根据G是否有k个叶子的生成树返回true或false 示例:对于此图： ? 现在我非常确定这个问题是np-complete的，所以我需
浏览 69提问于2020-12-03得票数 0
回答已采纳
编写了一种算法来查找具有最大叶子数的生成树。编写了一种算法来找到具有最小节点数的生成树。
我还未能就以下问题提出解决办法。
浏览 3提问于2020-03-20得票数 0
5回答
我想嵌入3个NP-完全问题(其中2个是NP-完全的，其中一个是我自己的想法)。我看到了"“，并从理论上得到了重新解释嵌入问题的想法：
我的想法是，更多的物品意味着更多的袋子重量。更多的袋子重量会使小偷的速度成倍下降。所以小偷的另一个目标应该是尽快完成抢劫。在这个时候，我不确定我的想法实际上是NP-完全的。也许，“引力”不仅仅是一个NP-完全问题</
浏览 12提问于2009-02-12得票数 3
2回答
据我所知，要证明一个问题是NP完全的，有两个步骤：
给定一组整数S，是否可以分离元素的子集S'，这样S&#
浏览 1提问于2013-12-12得票数 2
回答已采纳
1回答
给了我一个问题，那就是在学校的k个教室里安排n个班，这是一个决策问题，因为我们想问我们是否可以在这些k个房间里安排这些n个班，这样就不会超过给定的时间限制t(以某种预定方式上课的总时间不应该超过t)。我知道首先证明了这个问题的每一个解都可以在多项式时间内得到验证，但是当涉及到将一些已知的NP完全问题转化为教室调度问题时，我不知道我应该选择哪个NP-完全问题。我正在考虑使用旅行推销员问题来减少，但我不知道如何将
浏览 1提问于2016-12-03得票数 1
回答已采纳
1回答
构造置换图
、、
我读过关于置换图是如何使许多NP-完全问题更容易解决的。例如，最大团问题、树宽问题等。但是，我无法理解从给定图G(V，E)生成置换图的过程。我们该怎么做呢？
浏览 3提问于2012-03-05得票数 3
1回答
假设我对计算生成树有三种限制：2.1。如果可能，显示满足此criteria.Both的所有子树
有什么解决这个问题的好算法不会让我发疯吗？我将不得不使用相当大的输入(1000+节点)来运行它，所以它的复杂性也不会太高。
浏览 0提问于2010-07-27得票数 3
1回答
我看过一个关于顶点覆盖问题(VC，已知的Np-完全问题)的2-近似算法的问题，但我不知道答案。问题如下:使用“生成树”为顶点覆盖问题找到一个2-近似算法。对于VC，已经提出了许多贪婪的方法，但是使用“生成树”的特殊算法是具有挑战性的。有什么想法吗？
浏览 11提问于2011-02-01得票数 4
我想(虽然没有证明)这个问题是NP-完全的。你认为如何？你如何将一个著名的NP-完全问题转化为这个问题？
浏览 4提问于2011-12-08得票数 1
回答已采纳
2回答
我遇到了NP-完全问题，我不知道什么时候问题是NP-完全的。有没有捷径来知道一个给定的问题是否是NP-完全的，这样我就不会浪费时间去思考一个快速的算法？
浏览 6提问于2022-07-21得票数 0
回答已采纳
1回答
提示:哈密顿路径问题是:给定一个具有n个顶点的无向图，确定是否有一条(无圈的)n-1边完全访问每个顶点一次的路径。你可以利用哈密顿路径问题是NP-完全这一事实。在图的所有生成树中，用尽可能最少的叶子数计算一棵树.
在图的所有生成树中，用最小可能的最大度计算一棵树。(回想一下，顶点的程度是入射边的数量。)注意，哈密顿路径是图的生成树，只有两个叶节点，图的任何生成树</em
浏览 0提问于2019-01-08得票数 0
2回答
我应该证明以下问题是NP-完全的。提示说，您应该将子集和问题简化为这个问题。
任何关于使用另一个NP-完全问题的想法都会受到赞赏。
浏览 2提问于2015-06-01得票数 5
回答已采纳
我试着在著名的游戏流程中找到解决问题的方法。
在谷歌搜索后，我发现这是一个NP完全问题。一个好的解决方案将使用启发式和削减。我怎样才能很容易地发现NP完全问题？当这种情况发生在NP-完全时，最好快速识别它，然后继续下一个问题。
浏览 2提问于2013-11-25得票数 1
回答已采纳
1回答
我有一个朋友，他向我提出了这个问题：(我不知道这是否是他的家庭作业，反正我不问代码什么的)，从算法上讲，一个人如何在中得到最大的数字，同时又避免他们的组合(考虑到组合的数量，以及每个组合中数字的数量)。首先，这是一个动态规划问题吗？我很困惑。你有什么想法？
浏览 1提问于2015-04-29得票数 1
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
云直播
对象存储
实时音视频活动推荐
腾讯云开发者
