NP、NP-Complete和NP-Hard有什么不同之处? 我知道网上有很多资源。我想读一下你的解释,因为它们可能与其他地方的不同,或者有一些我不知道的东西。
我正在编写一些测验游戏,并需要电脑在玩家无法解决问题时解决1个问题。 已知数据: 可供使用的6个数字列表,例如4、8、6、2、15、50。 目标值,在0<value<1000的范围内,例如590。 可以使用的运算符为除法、加法、乘法和减法。 可以使用括号。 生成数学表达式,使其结果等...
有许多优化问题已知是NP难的,例如旅行商问题,MAX-SAT问题或者寻找图的最小色数。针对这种问题,我对以下问题的复杂性很感兴趣: 给定一个NP难的优化问题和一个候选解S,S是否是该问题的最优解? 直觉上,这个问题可能是co-NP难的,因为可以通过猜测更好的解并将其作为证人来轻易地...
旅行推销员优化问题(TSP-OPT)是一个NP难问题,而旅行推销员问题(TSP)则是NP完全问题。然而,由于如果能在多项式时间内解决TSP问题,那么也能解决TSP-OPT问题,因此TSP-OPT可以被约化为TSP(1)。我原以为在A可以被约化为B的情况下,B必须和甚至比A更难。但是从下面的参考...
因式分解:给定整数N,找到两个小于N的正整数a和b(1 < a, b < N),使得它们的乘积等于N。如果这样的a和b不存在,那么N是一个质数。 我知道判断质数可以用P算法,但为什么不能用这种方法做因式分解呢? 这是我的算法:For each a = 1 ... sqrt(N) ...
我有几个数字数组(每个数组的元素只能取0或1),如下: v1: 1; 0; 0; 1; 1; v2: 0; 1; 0; 0; 1; v3: 1; 1; 0; 1; 0; v4: 1; 0; 0; 1; 0; v5: 1; 1; 0; 1; 1; v6: 1; 1; 0; 1; 1...
我在期中考试中遇到了一个问题。有人能解释一下答案吗? 问题A:给定一个完全加权图G,找到一条带有最小权重的哈密顿回路。 问题B:给定一个完全加权图G和实数R,G是否有一条带有最大权重为R的哈密顿回路? 假设有一台机器可以解决问题B。如果每次给出G和实数R来解决问题A,我们最多可以调用多少...
我知道到目前为止还没有解决P=NP问题,但是有人能告诉我一些关于以下内容的信息吗?目前最有前途的数学/计算机科学方法是什么,可以帮助解决这个问题吗?或者现在甚至没有这样的方法被认为是潜在有用的吗?是否有任何(免费的)汇编关于这个主题,在那里我可以找到所有/大部分研究在这个领域完成?
我很难理解什么是非确定性多项式时间问题和NP完全问题。我了解什么是多项式时间可解问题,并在维基百科上看到了关于NP问题的介绍。阅读后,我尝试考虑一些示例问题。据我所知,对于无向图中的深度优先搜索而言,由于每个决策都可以被非确定地做出(即如果我做错了一个决定,我可以尝试一些其他选择),因此它是N...
我不相信存在一种算法,可以在二分图中找到最大独立顶点集,除了通过暴力方法找到所有可能的独立集合中的最大值。 我想知道如何编写伪代码来查找所有可能的顶点集。 假设有一个具有4个蓝色顶点和4个红色顶点的二分图。目前,我会使用以下方法: Start with an arbitrary blue...