旅行商问题中的NP-难与NP-完全混淆
旅行商优化问题(TSP-OPT)是一个NP-Hard问题，而旅行商搜索(TSP)是NP-完全问题。然而，TSP-OPT可以归结为TSP，因为如果TSP可以在多项式时间内求解，那么TSP-OPT(1)也可以。我认为要将A简化为B，B必须和A一样难，如果不比A更难的话。正如我在下面的参考文献中看到的，TSP-OPT可以简化为TSP。TSP-OPT应该比TSP更难。我很困惑... 参考文献：(1)
..
np相关内容
具有固定子集大小的和子集
和子集问题指出: 给定一组整数，是否存在总和为零的非空子集? 这个问题一般是NP完全的.我很好奇是否知道这种轻微变体的复杂性: 给定一组整数，是否有一个大小为 k 的子集，其总和为零? 例如，如果k = 1，您可以进行二分查找以在O(log n)中找到答案.如果 k = 2，那么您可以将其简化为 O(n log n)(例如，请参阅 从数组中查找总和等于给定数字的一对元素).
..
给定无向图G =(V，E)，确定G是否为完整图
我很确定这个问题是P而不是NP，但是我很难提出多项式绑定算法来解决它. 解决方案 您可以: 检查图中的边数是否为 n(n-1)/2 . 检查每个顶点是否连接到精确的 n-1 个不同的顶点. 这将以多项式的 O(V²)运行. 希望有帮助.
..
生成方程式，其结果值最接近要求的方程式，出现速度问题
我正在编写一些测验游戏，如果玩家未能解决该测验，则需要计算机解决该测验中的1个游戏. 提供数据: 要使用的6个数字的列表，例如4、8、6、2、15、50. 目标值，其中0
..
如何为该匹配问题构造np约简?
我有一个匹配的问题，我认为这很困难: 我们需要为一组n个人安排晚餐，其中一些是彼此的朋友，有些则不是.我们需要让每个人都坐在一张桌子旁，但他们绝不能与自己不是朋友的人坐在一起.有* k *个表K = r1 + r2 +··+ rk = n.**输入**输入的格式设置为第一行k，然后跟随一行k个数字，其中每个数字代表一个表格及其容量.然后是n行人，在那里我们可以看到人i的友谊.所有的友谊都是相互的
..
Tile Trial NP-hard复杂性
在《最终幻想XIII-3》游戏中，玩家遇到了几个难题.引入的第一个难题叫做 Tile Trial ，它为玩家提供了一个网格砖，其中一些砖块上有水晶.目标是取回所有晶体并到达出口，同时在每个瓷砖上踩不超过一次. http://arxiv.org/pdf/1203.1633v1.pdf 的作者指出这个问题是NP-Hard问题，因为可以将特定情况简化为哈密顿循环.我发现这是一个幼稚的假设，因为他开
..
实施启发式回溯搜索?
我对搜索算法和回溯编程非常感兴趣.目前，我已经实现了算法X(请参见我的其他文章:确定无冲突集吗?)来解决确切的覆盖问题.效果很好，但我现在有兴趣通过更基本的回溯方式解决此问题.我只是不知道如何做到这一点.问题描述与以前相同: 假设您有一堆集合，而每个集合都有几个子集. Set1 = {(香蕉，菠萝，橙子，(苹果，羽衣甘蓝，黄瓜)，(洋葱，大蒜)}} Set2 = {(香蕉，黄瓜，
..
证明暂停问题对NP不利吗?
在此问题的答案中NP，NP-hard和NP-complete的定义，Jason声称 停顿问题是经典的NP难题.这是给定程序P和输入I会停止的问题吗?这是一个决策问题，但不是NP问题.显然，任何NP完全问题都可以简化为这个问题. 虽然我同意暂停问题在直观上比NP中的任何问题都要“困难"得多，但老实说，我无法提出形式上的数学证据来证明暂停问题是NP难题.特别是，我似乎找不到从NP中每个问题
..
基于NP验证者的定义
我是一名计算机科学专业的学生，在理解基于验证者的NP问题定义时遇到了一些问题. 定义说，如果可以在给定的“证书"的情况下，通过确定性的图腾机在政治时间内验证问题，那么NP中就存在问题. 但是，如果证书正是有问题的解决方案，那会发生什么呢?这只是一点点，而且明显地受输入大小的限制，并且显然可以在常量时间(即政策时间)内进行验证. 因此，每个决策问题都将属于NP. 我在哪里
..
NP问题是否也完整?
NP完全的定义是 如果问题是NP完全问题 它属于NP类 NP中的所有其他问题都会通过多项式转化为它 因此，如果NP中的所有其他问题都转变为NP完全问题，那是否还不意味着所有NP问题也都是NP完全问题?如果两者相同，对它们进行分类有什么意义呢? 换句话说，如果我们有一个NP问题，那么通过(2)，这个问题可以转化为一个NP完全问题.因此，NP问题现在是NP完全的，并且NP
..
阵列搜索NP完成
给定一个大小为n的未排序数组，很显然，查找数组中是否存在元素需要O(n)时间. 如果我们让m = log n，则需要O(2 ^ m)时间. 请注意，如果对数组进行排序，则二进制搜索实际上需要O(m)时间(多项式)，但是二进制搜索不能应用于未排序的数组. 是否有可能证明在数组中找到一个元素(是或否)的问题就m而言是NP完备的.我应该减少什么问题以及如何减少? 任何想法都会受到
..
在python中将FFT绘制为一组正弦波?
我在演示中看到有人这样做，但是我很难重现他的能力.这是他的演讲的幻灯片: 非常酷.他使用FFT分解了一个数据集，然后绘制了FFT指定的适当正弦波. 因此，为了重新创建他所做的工作，我创建了一系列与两个正弦波组合相对应的点: import matplotlib.pyplot as plt import numpy as np %matplotlib inline x = np.a
..
图中所有可能的路径
给定一个图 G（V，E），一个源顶点 s 和目标顶点 d ，问题是要找到所有可能的从 s 到 d 的路径，其中 G 可能包含循环和循环。我想获得所有简单的路径，不允许循环。 这个问题的复杂性是什么？ 解决方案 此问题是NP难题，因为其输出的输入可能成指数大小。 找到之间的最长路径两点已经是NP难点了（减少了哈密顿路径问题），所以找到所有这些点也是一样。 通过查看图中两个顶
..
如何优化具有这些约束的任务分配给座席？
我的硕士论文中有一个作业问题，我正在寻找解决这个问题的一般方向。 因此，这里有一个清单代理，以及任务列表，任务数量大于代理数量。 代理提交他们可以/想要执行的任务的优先顺序列表。 。列表的长度固定为比任务总数小得多的数量。 必须为每个座席分配一个任务。一旦分配了任务，则无法将其分配给其他座席。 目标是找到一个分配，以使分配的任务的平均优先级/优先级最低。此外，如果这是一个完
..
给定一组人，其中每对都有一个值，我如何找到总值最小的配对配置？
与分配问题非常相似，不同之处在于它具有完整的无向图而不是二元图图。 最笨拙，最暴力的解决方案是这样的： 获取所有可能的配对配置... groups = people.combination（2）.to_a.combination（people .size / 2）.to_a ...拒绝多次包含同一个人的所有配置。 groups.reject！ {| group | g
..
图形的3色（多项式时间）？
我们可以在多项式时间内为图形着色3种颜色吗？我读到用2 颜色为图形着色很容易，但是用3种不同颜色（没有两个顶点具有 相同颜色）为图形着色是np困难的。我想知道是否有一个魔术盒对'A 图在多项式时间内是3色的？表示'是'。如果它说'是'，它将如何在 $中解决它。 b $ b多项式时间？有任何想法吗 ？ 解决方案 向您的图形添加3个新顶点，称为红色/绿色/蓝色，每个顶点都与其他
..
给定整数和阈值T的集合，将集合划分为总和> = T的尽可能多的组。
给出一个整数和阈值T的集合，将该集合尽可能多地划分为和，它们的总和> = T。 其余整数（其总和 约束： 列表的长度
..
NP-完整VS NP-硬
我试图了解NP-Complete和NP-Hard之间的区别。 以下是我的理解 一个NP-Hard问题是不能在多项式时间内求解，但可以在多项式时间内验证。 NP完全问题是NP中的一个问题，也是NP-Hard。 以上定义正确吗？如果是这样，那问题不是在NP中而是在NP-Hard中。它们难道不比NP完全问题难，比如只能在指数时间内解决和验证它们吗？ 解决方案 一个 NP
..
np.where在多个变量上
我有一个数据框，其中包含: customer_id [1,2,3,4,5,6,7,8,9,10] feature1 [0,0,1,1,0,0,1,1,0,0] feature2 [1,0,1,0,1,0,1,0,1,0] feature3 [0,0,1,0,0,0,1,0,0,0] 使用此方法，我想创建一个新变量(例如new_var)，以说当特征1为1时，则new_var = 1，如果f
..
矩阵未对齐错误消息
我有以下收益数据框 ret Out[3]: Symbol FX OGDC PIB WTI Date 2010-03-02 0.000443 0.006928 0.000000 0.012375 2010-03-03 -0.000690
..