np-complete相关内容

求任意图的最大权独立集的启发式算法

MWIS(最大权重独立集)是一个NP-完全问题，因此如果P！=NP，我们无法在足够好的时间复杂度内找到解决方案。 我正在寻找一种算法，可以在一个良好的时间复杂性内在任意图形中找到MWIS的近似值。我当前正在处理一个具有128个节点和3051条边的连通图。 我找到了this paper，但它似乎只适用于具有唯一MWIS的二部图。 如果有人能帮我一些参考，或者更好的工作算法的伪代码， ..

发布时间：2022-07-16 22:22:57 algorithm graph graph-algorithm linear-programming np-complete 其他开发

有界度生成树中的 np 完备性

我理解为什么有界度生成树被认为是度数为 2 的 NP Complete(它是哈密顿路径问题的一个实例)，但我不明白为什么这适用于度数 > 2.如果有人可以请解释一下为什么这是度数 > 2 的 NP Complete 问题，这将是最有帮助的 解决方案 嗯，我觉得你可以从bounded by 2的实例，简化为General k的实例. 直观地，我们将连接到原始图的每个节点上新的 k-2 ..

发布时间：2021-12-24 14:52:57 graph tree np-complete 其他开发

从大小为 n 的列表中找出哪些数字和另一个数字相加的算法

我有一个十进制数(我们称之为目标)和一个其他十进制数的数组(我们称之为数组元素)，我需要找到所有的组合来自元素的总和为目标的数字. 我更喜欢 C# (.Net 2.0) 中的解决方案，但无论如何最好的算法可能会获胜. 您的方法签名可能类似于: public decimal[][] Solve(decimal目标，decimal[]元素) 解决方案 有趣的答案.感谢您对维基百科的指 ..

发布时间：2021-12-06 20:09:36 c# algorithm math np-complete C#/.NET

在图形中查找最少的彩色路径

我要解决的问题是: 给出一个图形G =(V，E)，以使每个 edge 都用10种颜色之一着色，并用两个顶点s，t着色. 我需要找到一种算法，该算法可以产生从s到t的(最短)路径，并且所涉及的颜色最少. 我的想法是将图形重复10次: 第一个重复项将仅包含一种颜色的边缘 第二个将只包括两种颜色的边缘...等等. 另外，我将一个外部节点:s'连接到每个重复项中的每个" ..

发布时间：2021-04-02 20:48:24 algorithm shortest-path breadth-first-search np-complete 其他开发

通过将一个集合划分为两个子集，找出可以形成的最大和

变形 给出一组数字S. 求最大和 Sum(A 1 )= Sum(A 2 ) 其中，A 1 ⊂ S和A 2 ⊂ S和A 1 ⋂A 2 =∅ Sum(X)是集合X中所有元素的总和. 方法 蛮力 最简单的方法是: print maximumSum(0,0,0)def maximumSum(index，sum1，sum2):ans = 0如果sum1 == sum2:a ..

发布时间：2021-04-02 20:28:49 algorithm dynamic-programming np-complete subset-sum 其他开发

NP问题是否也完整?

NP完全的定义是 如果问题是NP完全问题 它属于NP类 NP中的所有其他问题都会通过多项式转化为它 因此，如果NP中的所有其他问题都转变为NP完全问题，那是否还不意味着所有NP问题也都是NP完全问题?如果两者相同，对它们进行分类有什么意义呢? 换句话说，如果我们有一个NP问题，那么通过(2)，这个问题可以转化为一个N​​P完全问题.因此，NP问题现在是NP完全的，并且NP ..

发布时间：2020-07-08 08:40:34 computer-science complexity-theory np-complete np 其他开发

阵列搜索NP完成

给定一个大小为n的未排序数组，很显然，查找数组中是否存在元素需要O(n)时间. 如果我们让m = log n，则需要O(2 ^ m)时间. 请注意，如果对数组进行排序，则二进制搜索实际上需要O(m)时间(多项式)，但是二进制搜索不能应用于未排序的数组. 是否有可能证明在数组中找到一个元素(是或否)的问题就m而言是NP完备的.我应该减少什么问题以及如何减少? 任何想法都会受到 ..

发布时间：2020-07-01 20:28:41 time-complexity complexity-theory binary-search np-complete np 其他开发

某些NP完全问题又如何成为NP-Hard?

我正在尝试以一种直观的方式将听到的内容围绕在P，NP，NP-Complete和NP-Hard上，这样我就不必记住它们的定义了. 在下面的图像中(左手场景，P！= NP)，NP-Complete和NP-Hard之间存在重叠区域.这是否意味着NP-Complete和NP-Hard都存在一些问题?根据此特定答案，我发现这是矛盾的:上面链接中的表格显示，可以在多项式时间内验证NP-Complete问 ..

发布时间：2020-07-01 20:28:37 complexity-theory computer-science np-complete np-hard 其他开发

sudoku np如何完整?

数独如何成为np完全问题?根据Wiki的规定，要归类为np完全问题，必须满足2个条件 问题必须在np np中的所有其他问题都必须可简化为多项式时间内的给定问题 第二个条件如何满足?你能给个例子吗?例如，我看不出数独问题和旅行推销员问题或背包问题之间的相关性 (请原谅我在移动设备上键入此问题时的格式不正确) 解决方案 该结果首先在本硕士论文中以减少 NP完全问题拉丁方 ..

发布时间：2020-07-01 20:28:33 sudoku np-complete 其他开发

关于独立集问题的NP完全性的问题

我以为，当证明一个问题P是NP-Complete时，我们应该将一个已知的NPC问题简化为P.但是，在研究独立集问题的解决方案时，似乎并没有这样做. 要证明独立集是NP完全的，可取一个图形G，找到其逆G'，然后计算CLIQUE(G').但是，这是另一回事:遇到一个问题P，我不知道它是否是NPC，然后将其简化为已知的NPC问题. 这里是解决方案的示例. 我在这里想念什么?这不是错吗， ..

发布时间：2020-07-01 20:28:31 complexity-theory time-complexity np-complete 其他开发

将列表分为两个等份算法

相关问题: 划分列表的算法将数字分为2个相等的总和列表 将列表分为两部分他们的总和彼此最接近 让我们假设我有一个列表，其中完全包含2k元素.现在，我愿意将其分为两个部分，每个部分的长度为k，同时尝试使这些部分的总和尽可能相等. 快速示例: [3, 4, 4, 1, 2, 1]可能会拆分为[1, 4, 3] and [1, 2, 4]，并且总和差将为1 现在-如果零件可以具 ..

发布时间：2020-07-01 20:28:27 algorithm np-complete computation-theory partition-problem data-partitioning 其他开发

使用模拟退火进行图形着色

我正在尝试使用模拟退火解决图形着色问题的算法.在线上有通用算法，但是当我看它时，我不明白如何在此问题上应用该算法.图中的每个节点必须与其临近点具有不同的颜色. 如何为此使用模拟退火算法. 这个问题中的“温度"，“时间表"是什么? 请帮助我理解这一点.谢谢 解决方案 图形的正确着色是将颜色分配给图形的顶点，以便没有两个相邻的顶点具有相同的颜色. 要解决此问题，假设您有一个具有 ..

发布时间：2020-07-01 20:28:23 java np-complete simulated-annealing graph-coloring Java开发

带有重叠物体的垃圾箱包装

我有一些具有不同容量的垃圾箱和一些具有指定大小的物体.目标是将这些对象包装在垃圾箱中.到目前为止，它类似于垃圾箱包装问题.但是，不同之处在于，每个对象之间都存在部分重叠.因此，虽然对象1和2的大小分别为s1和s2，但是当我将它们放在同一容器中时，填充空间小于s1 + s2.假设我知道每个对象对都有这个重叠值，那么是否也有类似的近似算法，例如用于此问题的原始装箱算法? 解决方案 答案是使用一 ..

发布时间：2020-07-01 20:28:21 combinatorics np-complete approximation bin-packing 其他开发

是否所有调度问题都是NP-Hard?

我知道那里存在一些调度问题，这些问题是NP难的/NP完整的...但是，这些问题都没有以表明这种情况也是NP的方式陈述. 如果您有一组限制在 startAfter ， startBy 和 duration 的任务都试图使用单个资源 ... ...您可以解决时间表或确定没有详尽搜索无法解决的时间表吗? 如果答案是“对不起朋友，但这是NP完全的" ，什么是最好的启发式方法?有什么方法可以减少 ..

发布时间：2020-07-01 20:28:17 recursion scheduling heuristics np-complete resource-scheduling 其他开发

什么是"P = NP?"，为什么它是一个如此著名的问题?

在计算机科学中，P = NP是否可能是最著名的问题.这是什么意思?为什么这么有趣? 哦，为了获得额外的荣誉，请张贴有关该陈述的真实性或虚假性的证明. :) 解决方案 P表示多项式时间. NP代表不确定的多项式时间. 定义: 多项式时间意味着算法的复杂度为O(n ^ k)，其中n是数据的大小(例如，要排序的列表中元素的数量) ，并且k是一个常数. 复杂度是根据需要执行 ..

发布时间：2020-07-01 20:28:15 computer-science theory complexity-theory np-complete p-np 其他开发

NP-完整VS NP-硬

我试图了解NP-Complete和NP-Hard之间的区别。 以下是我的理解 一个NP-Hard问题是不能在多项式时间内求解，但可以在多项式时间内验证。 NP完全问题是NP中的一个问题，也是NP-Hard。 以上定义正确吗？如果是这样，那问题不是在NP中而是在NP-Hard中。它们难道不比NP完全问题难，比如只能在指数时间内解决和验证它们吗？ 解决方案 一个 NP ..

发布时间：2020-06-03 20:48:56 algorithm computer-science np-complete np np-hard 其他开发

最小的加链求幂

我知道它已经被证明是NP完全的，没关系。我目前正在用分支定界法解决这个问题，我将初始上限设置为乘以常规二进制平方/乘算法的乘数，它的确给出了正确的答案，但我对运行不满意时间（200左右的数字可能需要几秒钟）。这是一个NP完全问题，我不希望有任何壮观的事情。但是通常有一些技巧可以控制实际时间。 在实践中是否有更快的方法？如果是这样，它们是什么？ 解决方案 这看起来像Knuth第2卷的半 ..

发布时间：2020-06-03 20:40:59 algorithm np-complete exponentiation 其他开发

阶乘时间算法和P / NP

很容易看到n！ N幂的增长速度几乎比几乎任何东西都慢（例如100 ^ N），因此，如果一个问题被认为是NP完全的并且一个问题发生在n上！一种近似解决方案的算法，有人会做史努比舞。 关于这种情况，我有两个问题： 将n！算法被认为是多项式时间的解决方案？阶乘肯定不是一个幂的名词。 如果找到n！解决方案意味着我们有一个相当快的算法，因为n！增长速度快于2 ^ N，那么这是否意味着某些NP完 ..

发布时间：2020-06-03 20:30:42 algorithm np-complete 其他开发

有关优化和决策版本的装箱

我正在为考试而学习，我们遇到了一系列练习问题.这是我正在努力解决的问题，希望有人可以帮助您阐明解决此问题的正确方法: 这是我最初要解决的问题: 决策版本: 为了使用决策版本找到最佳解决方案，我将尝试使用各种K，直到得到肯定的答案.假设优化的解决方案是7，我会尝试: k=1, no k=2, no k=3, no k=4, no k=5, no k=6, no k=7, yes. ..

发布时间：2020-05-21 21:26:43 algorithm optimization np-complete np bin-packing 其他开发

布尔公式编码

我想知道对 这样的布尔公式进行编码需要多少位 @(x1,x2,x3,x4) = (x1 OR x2 OR NOT(x3) OR x4) AND ((NOT)x2 OR x3) AND (x1 OR (NOT)x4) @是SAT的一个实例.我认为这是4位，因为可能的组合总数为2(power4).那是对的吗?我应该计算OR，NOT和AND来计算编码所需的位数吗?我搜索了很多，但找不到任何东 ..

发布时间：2020-05-06 11:20:18 math np-complete np np-hard satisfiability 其他开发