精华内容
下载资源
问答
  • 1.P(polynominal)问题–多项式问题 存在多项式时间算法的问题。 2.NP(Nondeterministic Polynominal)问题–非确定多项式问题 能在多项式时间内验证得出一个正确解的问题。...通俗理解,NP难问题
  • P问题、NP问题、NP完全问题和NP难问题

    万次阅读 多人点赞 2019-06-12 14:06:30
    在讲P类问题之前先介绍两个个概念:多项式,时间复杂度。(知道这两概念的可以自动跳过这部分) 1、多项式:axn-bxn-1+c 恩....就是长这个样子的,叫x最高次为n的多项式.... 咳咳,别嫌我啰嗦。。有些人说不定还真...

     

     

    转载出处。 https://blog.csdn.net/qq_21768483/article/details/80430590

    在讲P类问题之前先介绍两个个概念:多项式,时间复杂度。(知道这两概念的可以自动跳过这部分)

    1、多项式:axn-bxn-1+c

    恩....就是长这个样子的,叫x最高次为n的多项式....

    咳咳,别嫌我啰嗦。。有些人说不定还真忘了啥是多项式了。。例如第一次看到的鄙人→_→

    2、时间复杂度

    我们知道在计算机算法求解问题当中,经常用时间复杂度和空间复杂度来表示一个算法的运行效率。空间复杂度表示一个算法在计算过程当中要占用的内存空间大小,这里暂不讨论。时间复杂度则表示这个算法运行得到想要的解所需的计算工作量,他探讨的是当输入值接近无穷时,算法所需工作量的变化快慢程度。

    举个例子:冒泡排序。

    在计算机当中,排序问题是最基础的,将输入按照大小或其他规则排好序,有利于后期运用数据进行其他运算。冒泡排序就是其中的一种排序算法。假设手上现在有n个无序的数,利用冒泡排序对其进行排序,

    ①首先比较第1个数和第2个数,如果后者>前者,就对调他们的位置,否则不变

    ②接着比较第2个数和第3个数,如果后者>前者,就对调他们的位置,否则不变

    ③一直向下比较直到第n-1和第n个数比较完,第一轮结束。(这时候最大的数移动到了第n个数的位置)

     

    ④重复前三步,但是只比较到第n-1个数(将第二大的数移动到第n-1个数位置)

    ⑤持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

    举个实例:5,4,3,2,1,对其进行排序,先是比较5跟4变成4,5,3,2,1,第一轮结束后变成43215,可以计算,当对其排序完正好要经过4+3+2+1=10次比较,当然这是最复杂的情况,即完全反序。可以知道对于n个数,至多要经过1+2+...+n-1即(n^2-n)/2次比较才能排好序。这个式子里n的最高次阶是2,可知道当n→∞时,一次性对其比较次数影响很小,所以我们把这个算法的时间复杂度比作:o(n^2)。取其最高次,可以看出,这是一个时间复杂度为多项式的表示方式。

    时间复杂度排序o(1)<o(n)<o(lgn)<o(n^2)<o(n^a)<o(e^n)(a>2,n表示输入的数据个数,o(1)为常数级别)

     

    好了,介绍完上面的概念就可以开始讲关于什么叫P类问题了。以上个例子冒泡排序为例,我们知道了,在排序这个大问题里,是可以找到一种时间复杂度为多项式o(n^2)的算法(如冒泡排序法)来求解排序问题的,所以我们说排序问题是一个有多项式时间算法的问题。

    所以我们称,

    P类问题:存在多项式时间算法的问题。(P:polynominal,多项式)

     

    然后扯个题外话,为什么我们要研究这个?因为计算机处理的输入常常不是那么几十个几千个那么一点点,想象一下,当计算机处理的数据达到100万个的时候,时间复杂度为o(n^2)和o(e^n)的算法,所需的运行次数简直是天壤之别,o(e^n)指数级的可能运行好几天都没法完成任务,所以我们才要研究一个问题是否存在多项式时间算法。而我们也只在乎一个问题是否存在多项式算法,因为一个时间复杂度比多项式算法还要复杂的算法研究起来是没有任何实际意义的。

     

    好了,接下来我们介绍NP,先给定义,

    NP类问题:能在多项式时间内验证得出一个正确解的问题。(NP:Nondeterministic polynominal,非确定性多项式)

    P类问题是NP问题的子集,因为存在多项式时间解法的问题,总能在多项式时间内验证他。

     

    注意定义,这里是验证。NP类问题,我用个人的俗话理解就是,不知道这个问题是不是存在多项式时间内的算法,所以叫non-deterministic非确定性,但是我们可以在多项式时间内验证并得出这个问题的一个正确解。举个例子,

    著名的NP类问题:旅行家推销问题(TSP)。即有一个推销员,要到n个城市推销商品,他要找出一个包含所有n个城市的环路,这个环路路径小于a。我们知道这个问题如果单纯的用枚举法来列举的话会有(n-1)! 种,已经不是多项式时间的算法了,(注:阶乘算法比多项式的复杂)。那怎么办呢?我们可以用猜的,假设我人品好,猜几次就猜中了一条小于长度a的路径,我画画画画,好的,我得到了一条路径小于a的环路,问题解决了,皆大欢喜。可是,我不可能每次都猜的那么准,也许我要猜完所有种呢?所以我们说,这是一个NP类问题。也就是,我们能在多项式的时间内验证并得出问题的正确解,可是我们却不知道该问题是否存在一个多项式时间的算法,每次都能解决他(注意,这里是不知道,不是不存在)。

    所以这就引出了这类讨论的一个千年问题:是否 NP类问题=P类问题?

    即,是否所有能在多项式时间内验证得出正确解的问题,都是具有多项式时间算法的问题呢?

    太让人震惊了,要是解决了这个问题,那岂不是所有的NP问题都可以通过计算机来解决?

     

    圣战的结果是,有的存在,有的不存在。=_=

    在这场圣战中,人们还发现了很多的东东,也就是我们接下来要介绍的NPC问题(啊喂,我不是游戏NPC)和NPH问题。

    (PS :网络上经常有人说,这不是个NP问题吗,其实很多时候他们说的应该是NPC问题,而不是NP问题)

    为了证明这个千古难题,科学家想出了很多办法。其中之一就是问题的约化。所谓问题约化就是,可以用问题B的算法来解决A ,我们就说问题A可以约化成问题B。举个例子,一元一次方程的求解,跟二元一次方程的求解,我们知道,只要能求解二元一次方程,那就可以用二元一次方程的解法来求解一元一次方程,只需要将一元一次方程加上y,并附加一个方程y=0就可以将一元一次方程变形为一个二元一次方程,然后用二元一次方程的解法来求解这个方程。注意,这里二元一次方程的解法会比一元一次的复杂。所以我们说,只需要找到解二元一次方程的规则性解法,那就能用这个规则性解法来求解一元一次方程。从这里也可以看出,约化是具有传递性的,如A约化到B,B约化到C,A就可以约化到C,同时不断约化下去,我们会发现一个很惊人的特性,就是他一定会存在一个最大的问题,而我们只需要解决了这个问题,那其下的所有问题也就解决啦!这就是我们所说的NPC问题的概念!!!

    引到NP问题里就是,对于同一类的所有的NP类问题,若他们都可以在多项式时间内约化成最难的一个NP类问题,(我们直观的认为,被约化成的问题应具有比前一个问题更复杂的时间复杂度)当我们针对这个时间复杂度最高的超级NP问题要是能找到他的多项式时间算法的话,那就等于变向的证明了其下的所有问题都是存在多项式算法的,即NP=P!!!!给出NPC问题定义。

    (3)NPC类问题(Nondeterminism Polynomial complete):存在这样一个NP问题,所有的NP问题都可以约化成它。换句话说,只要解决了这个问题,那么所有的NP问题都解决了。其定义要满足2个条件: 

    首先,它得是一个NP问题;

    然后,所有的NP问题都可以约化到它。

    要证明npc问题的思路就是: 

    先证明它至少是一个NP问题,再证明其中一个已知的NPC问题能约化到它。

    (4)NP难问题(NP-hard问题):

        NP-Hard问题是这样一种问题,它满足NPC问题定义的第二条但不一定要满足第一条(就是说,NP-Hard问题要比 NPC问题的范围广,NP-Hard问题没有限定属于NP),即所有的NP问题都能约化到它,但是他不一定是一个NP问题。

        NP-Hard问题同样难以找到多项式的算法,但它不列入我们的研究范围,因为它不一定是NP问题。即使NPC问题发现了多项式级的算法,NP-Hard问题有可能仍然无法得到多项式级的算法。事实上,由于NP-Hard放宽了限定条件,它将有可能比所有的NPC问题的时间复杂度更高从而更难以解决。

     

    以上四个问题他们之间的关系可以用下图来表示: 
    这里写图片描述

    展开全文
  • NP难问题固定参数可逼近算法的进展
  • NP难问题求解综述

    万次阅读 2020-09-29 05:34:14
    关键词:NP难问题 P类问题 算法 最优化问题 正文: 一.NP难问题及P类问题 为了解释NP难问题及P类问题,先介绍确定性算法和非确定性算法这两个概念,设A是求解问题Π的一个算法,如果在算法的整个执行过程中,每...

     

    摘要:定义NP问题及P类问题,并介绍一些常见的NP问题,以及NP问题的一些求解方法,最后最NP问题求解的发展方向做一些展望。 

    关键词:NP难问题 P类问题 算法 最优化问题

    正文:

    一.NP难问题及P类问题

    为了解释NP难问题及P类问题,先介绍确定性算法和非确定性算法这两个概念,设A是求解问题Π的一个算法,如果在算法的整个执行过程中,每一步只有一个确定的选择,则称算法A是确定性(Determinism)算法。设A是求解问题Π的一个算法,如果算法A以如下猜测并验证的方式工作,就称算法A是非确定性(Nondeterminism)算法:(1)猜测阶段:在这个阶段,对问题的输入实例产生一个任意字符串y,在算法的每一次运行时,串y的值可能不同,因此,猜测以一种非确定的形式工作。(2)验证阶段:在这个阶段,用一个确定性算法验证:① 检查在猜测阶段产生的串y是否是合适的形式,如果不是,则算法停下来并得到no;② 如果串y是合适的形式,则验证它是否是问题的解,如果是,则算法停下来并得到yes,否则算法停下来并得到no。

    什么是NP难问题,如果对于某个判定问题Π,存在一个非负整数k,对于输入规模为n的实例,能够以O(nk)的时间运行一个非确定性算法,得到yes或no的答案,则该判定问题Π是一个 NP 类(Nondeterministic Polynomial)问题

    令Π是一个判定问题,如果对于NP类问题中的每一个问题Π',都有Π'∝pΠ,则称判定问题Π是一个NP难问题

    什么是P类问题,如果对于某个判定问题Π,存在一个非负整数k,对于输入规模为n的实例,能够以O(nk)的时间运行一个确定性算法,得到yes或no的答案,则该判定问题Π是一个 P 类(Polynomial)问题。所有易解问题都是P类问题。

    P类问题和NP类问题的主要差别:P类问题可以用多项式时间的确定性算法来进行判定或求解;NP类问题可以用多项式时间的非确定性算法来进行判定或求解。

     

    二.常见的NP类问题

    上面介绍了什么是NP问题,下面我将介绍我查阅到的一些常见的NP问题,他们同时也是著名的NP问题。

    ①图着色问题 按图中所示方式将16条边着色,那么不管你从哪里出发,按照“蓝红红蓝红红蓝红红”的路线走9步,你最后一定达到黄色顶点。路线着色定理就是说在满足一定条件的有向图中,这样的着色方式一定存在。严格的数学描述如下。我们首先来定义同步着色。G是一个有限有向图并且G的每个顶点的出度都是k。G的一个同步着色满足以下两个条件:1)G的每个顶点有且只有一条出边被染成了1到k之间的某种颜色;2)G的每个顶点都对应一种走法,不管你从哪里出发,按该走法走,最后都结束在该顶点。有向图G存在同步着

      

    色的必要条件是G是强连通而且是非周期的。一个有向图是非周期的是指该图中包含的所有环的长度没有大于1的公约数。路线着色定理这两个条件(强连通和是非周期)也是充分的。也就是说,有向图G存在同步着色当且仅当G是强连通而且是非周期的。

    ②哈密顿回路问题:天文学家哈密顿(William Rowan Hamilton) 提出,在一个有多个城市的地图网络中, 寻找一条从给定的起点到给定的终点沿途恰好经过所有其他城市一次的路径。这个问题和著名的过桥问题的不同之处在于,某些城市之间的旅行不一定是双向的。比如A→B,但B→A是不允许的。换一种说法,对于一个给定的网络,确定起点和终点后,如果存在一条路径,穿过这个网络,我们就说这个网络存在哈密顿路径。哈密顿路径问题在上世纪七十年代初,终于被证明是“NP完备”的。据说具有这样性质的问题,难于找到一个有效的算法。实际上对于某些顶点数不到100的网络,利用现有最好的算法和计算机也需要很长的时间(可能要几百年之久)才能确定其是否存在一条这样的路径。

    ③TSP问题:旅行商问题,即TSP问题(Traveling Salesman Problem)是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路经的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。TSP问题是一个组合优化问题。该问题可以被证明具有NPC计算复杂性。

    上面三个即是非常著名的NP问题,也是比较常见的NP问题。它们的求解算法非常复杂,要寻找到一个最优算法需要花费很长的时间,但正因为这些问题的复杂性,使得它们备受人们的关注。当然NP问题本身也是世界七大数学难题之一。

     

    三.求解NP类问题的常见方法

    对于那些棘手的NP问题,我们也并非束手无策,有一些方法可供我们去探究NP问题。

    ①近似算法:所有已知的解决NP难问题算法都有指数型运行时间。但是,如果我们要找一个“好”解而非最优解,有时候多项式算法是存在的。给定一个最小化问题和一个近似算法,我们按照如下方法评价算法:首先给出最优解的一个下界,然后把算法的运行结果与这个下界进行比较。对于最大化问题,先给出一个上界然后把算法的运行结果与这个上界比较。近似算法比较经典的问题包括:最小顶点覆盖、旅行售货员问题、集合覆盖等。

    ②概率算法:很多算法的每一个计算步骤都是固定的,而概率算法允许算法在执行的过程中随机选择下一个计算步骤。许多情况下,当算法在执行过程中面临一个选择时,随机性选择常比最优选择省时。因此概率算法可在很大程度上降低算法的复杂度。概率算法的一个基本特征是对所求解问题的同一实例用同一概率算法求解两次可能得到完全不同的效果。这两次求解问题所需的时间甚至所得到的结果可能会有相当大的差别。一般情况下,可将概率算法大致分为四类:数值概率算法,蒙特卡罗(Monte Carlo)算法,拉斯维加斯(Las Vegas)算法和舍伍德(Sherwood)算法。

    ③并行计算:并行计算或称平行计算是相对于串行计算来说的。所谓并行计算可分为时间上的并行和空间上的并行。 时间上的并行就是指流水线技术,而空间上的并行则是指用多个处理器并发的执行计算。并行计算(Parallel Computing)是指同时使用多种计算资源解决计算问题的过程。为执行并行计算,计算资源应包括一台配有多处理机(并行处理)的计算机、一个与网络相连的计算机专有编号,或者两者结合使用。并行计算的主要目的是快速解决大型且复杂的计算问题。此外还包括:利用非本地资源,节约成本 ― 使用多个“廉价”计算资源取代大型计算机,同时克服单个计算机上存在的存储器限制。包含以下三个特征:1,将工作分离成离散部分,有助于同时解决;2,随时并及时地执行多个程序指令;,3,

     

     

    多计算资源下解决问题的耗时要少于单个计算资源下的耗时。

    ④智能算法:在工程实践中,经常会接触到一些比较“新颖”的算法或理论,比如模拟退火,遗传算法,禁忌搜索,神经网络等。这些算法或理论都有一些共同的特性(比如模拟自然过程),通称为“智能算法”。智能优化算法要解决的一般是最优化问题。最优化问题可以分为(1)求解一个函数中,使得函数值最小的自变量取值的函数优化问题和(2)在一个解空间里面,寻找最优解,使目标函数值最小的组合优化问题。典型的组合优化问题有:旅行商问题(Traveling Salesman Problem,TSP),加工调度问题(Scheduling Problem),0-1背包问题(Knapsack Problem),以及装箱问题(Bin Packing Problem)等。优化算法有很多,经典算法包括:有线性规划,动态规划等;改进型局部搜索算法包括爬山法,最速下降法等,本文介绍的模拟退火、遗传算法以及禁忌搜索称作指导性搜索法。而神经网络,混沌搜索则属于系统动态演化方法。

     

    四.NP问题求解未来发展方向

    NP问题是世界七大数学难题之一,在名称上就有别于其它六个问题,也是其中唯一一个不是用人名来命名的数学难题。因为它不是某个数学家火花一闪、灵机一动所提出的理论或是猜测,而是一个非常古老的问题,涉及到了最基础的数学理论,并且经过了几百年来无数数学家们持之以恒的努力,直到现在仍然是一个没有得到解决的公开问题。

    NP问题排在世界七大数学难题之首,七个问题都是经过美国克雷数学研究所的科学顾问委员会精心挑选出来的,这些问题的获解上哪怕是获得了些许的进展,就将对数学理论的发展和应用产生极其巨大的推动作用。研究这些“千年大奖问题”已经成为世界数学界的热点,不少国家的数学家正在组织联合攻关,同时它们也是任何一个数学工作者都梦寐以求予以摘取的数学皇冠上的耀眼明珠。可以预期,这些“千年大奖问题”将会改变新世纪数学发展的历史进程。因此NP问题的求解将会不断地被注视着,当然如果有一天它被人求解出来,那么我们身边的许多问题将会被解决。

     

    参考文献:

    [1] 黄文奇 许如初. 《近世计算理论导引:NP难度问题的背景、前景及其求解算法研究》. 科学出版社 2004.  87

    [2] 陈志平 徐宗本. 《计算机数学:计算复杂性理论与NPC、NP难问题的求解》 科学出版社.  2001.  292

    展开全文
  • 在讲P类问题之前先介绍两个个概念:多项式,时间复杂度。(知道这两概念的可以自动跳过这部分) 1. 多项式:axn−bxn−1+cax^n-bx^{n-1}+caxn−bxn−1+c 恩…就是长这个样子的,叫 xxx 最高次为 nnn 的多项式… 咳咳,...

    该文章为转载,更正了原作者的一些笔误

    在讲P类问题之前先介绍两个个概念:多项式,时间复杂度。(知道这两概念的可以自动跳过这部分)

    1. 多项式: a x n − b x n − 1 + c ax^n-bx^{n-1}+c axnbxn1+c

    恩…就是长这个样子的,叫 x x x 最高次为 n n n 的多项式…

    咳咳,别嫌我啰嗦。。有些人说不定还真忘了啥是多项式了。。例如第一次看到的鄙人→_→

    2. 时间复杂度

    我们知道在计算机算法求解问题当中,经常用时间复杂度和空间复杂度来表示一个算法的运行效率。空间复杂度表示一个算法在计算过程当中要占用的内存空间大小,这里暂不讨论。时间复杂度则表示这个算法运行得到想要的解所需的计算工作量,他探讨的是当输入值接近无穷时,算法所需工作量的变化快慢程度。

    举个例子:冒泡排序。

    在计算机当中,排序问题是最基础的,将输入按照大小或其他规则排好序,有利于后期运用数据进行其他运算。冒泡排序就是其中的一种排序算法。假设手上现在有n个无序的数,利用冒泡排序对其进行排序,

    ①首先比较第1个数和第2个数,如果后者>前者,就对调他们的位置,否则不变

    ②接着比较第2个数和第3个数,如果后者>前者,就对调他们的位置,否则不变

    ③一直向下比较直到第n-1和第n个数比较完,第一轮结束。(这时候最大的数移动到了第n个数的位置)

    ④重复前三步,但是只比较到第n-1个数(将第二大的数移动到第n-1个数位置)

    ⑤持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

    举个实例: 5 , 4 , 3 , 2 , 1 5,4,3,2,1 5,4,3,2,1 对其进行排序,先是比较 5 5 5 4 4 4 变成 4 , 5 , 3 , 2 , 1 4,5,3,2,1 4,5,3,2,1 ,第一轮结束后变成 43215 43215 43215,可以计算,当对其排序完正好要经过 4 + 3 + 2 + 1 = 10 4+3+2+1=10 4+3+2+1=10 次比较,当然这是最复杂的情况,即完全反序。可以知道对于 n n n 个数,至多要经过 1 + 2 + . . . + n − 1 1+2+...+n-1 1+2+...+n1 ( n 2 − n ) 2 \frac{(n^2-n)}{2} 2(n2n) 次比较才能排好序。这个式子里 n n n 的最高次阶是 2 2 2 ,可知道当 n → ∞ n\rightarrow \infty n 时,一次性对其比较次数影响很小,所以我们把这个算法的时间复杂度比作: O ( n 2 ) O(n^2) O(n2) 。取其最高次,可以看出,这是一个时间复杂度为多项式的表示方式。

    时间复杂度排序 O ( 1 ) < O ( l g n ) < O ( n ) < O ( n 2 ) < O ( n a ) < O ( e n ) O(1)<O(lgn)<O(n)<O(n^2)<O(n^a)<O(e^n) O(1)<O(lgn)<O(n)<O(n2)<O(na)<O(en) a > 2 a>2 a>2 n n n 表示输入的数据个数, O ( 1 ) O(1) O(1) 为常数级别)

    好了,介绍完上面的概念就可以开始讲关于什么叫 P 类问题了。以上个例子冒泡排序为例,我们知道了,在排序这个大问题里,是可以找到一种时间复杂度为多项式 O ( n 2 ) O(n^2) O(n2) 的算法(如冒泡排序法)来求解排序问题的,所以我们说排序问题是一个有多项式时间算法的问题。

    所以我们称,

    (1)P 类问题:存在多项式时间算法的问题。(P:polynominal,多项式)

    然后扯个题外话,为什么我们要研究这个?因为计算机处理的输入常常不是那么几十个几千个那么一点点,想象一下,当计算机处理的数据达到100万个的时候,时间复杂度为 O ( n 2 ) O(n^2) O(n2) O ( e n ) O(e^n) O(en) 的算法,所需的运行次数简直是天壤之别, O ( e n ) O(e^n) O(en) 指数级的可能运行好几天都没法完成任务,所以我们才要研究一个问题是否存在多项式时间算法。而我们也只在乎一个问题是否存在多项式算法,因为一个时间复杂度比多项式算法还要复杂的算法研究起来是没有任何实际意义的。

    好了,接下来我们介绍 NP,先给定义,

    (2)NP 类问题:能在多项式时间内验证得出一个正确解的问题。(NP:Nondeterministic polynominal,非确定性多项式)

    P 类问题是 NP 问题的子集,因为存在多项式时间解法的问题,总能在多项式时间内验证他。

    注意定义,这里是验证。NP 类问题,我用个人的俗话理解就是,不知道这个问题是不是存在多项式时间内的算法,所以叫non-deterministic非确定性,但是我们可以在多项式时间内验证并得出这个问题的一个正确解。举个例子,

    著名的 NP 类问题:旅行家推销问题(TSP)。即有一个推销员,要到 n n n 个城市推销商品,他要找出一个包含所有 n n n 个城市的环路,这个环路路径小于 a a a 。我们知道这个问题如果单纯的用枚举法来列举的话会有 ( n − 1 ) ! (n-1)! (n1)! 种,已经不是多项式时间的算法了,(注:阶乘算法比多项式的复杂)。那怎么办呢?我们可以用猜的,假设我人品好,猜几次就猜中了一条小于长度 a a a 的路径,我画画画画,好的,我得到了一条路径小于 a a a 的环路,问题解决了,皆大欢喜。可是,我不可能每次都猜的那么准,也许我要猜完所有种呢?所以我们说,这是一个 NP 类问题。也就是,我们能在多项式的时间内验证并得出问题的正确解,可是我们却不知道该问题是否存在一个多项式时间的算法,每次都能解决他(注意,这里是不知道,不是不存在)。

    所以这就引出了这类讨论的一个千年问题:是否 NP 类问题 = P 类问题 ?

    即,是否所有能在多项式时间内验证得出正确解的问题,都是具有多项式时间算法的问题呢?

    太让人震惊了,要是解决了这个问题,那岂不是所有的 NP 问题都可以通过计算机来解决?

    圣战的结果是,有的存在,有的不存在。=_=

    在这场圣战中,人们还发现了很多的东东,也就是我们接下来要介绍的 NPC 问题(啊喂,我不是游戏 NPC ) 和 NPH 问题。

    (PS :网络上经常有人说,这不是个 NP 问题吗,其实很多时候他们说的应该是 NPC 问题,而不是 NP 问题)

    为了证明这个千古难题,科学家想出了很多办法。其中之一就是问题的约化。所谓问题约化就是,可以用问题B的算法来解决A ,我们就说问题 A 可以约化成问题 B。举个例子,一元一次方程的求解,跟二元一次方程的求解,我们知道,只要能求解二元一次方程,那就可以用二元一次方程的解法来求解一元一次方程,只需要将一元一次方程加上 y y y ,并附加一个方程 y = 0 y=0 y=0 就可以将一元一次方程变形为一个二元一次方程,然后用二元一次方程的解法来求解这个方程。注意,这里二元一次方程的解法会比一元一次的复杂。所以我们说,只需要找到解二元一次方程的规则性解法,那就能用这个规则性解法来求解一元一次方程。从这里也可以看出,约化是具有传递性的,如A约化到B,B约化到C,A就可以约化到C,同时不断约化下去,我们会发现一个很惊人的特性,就是他一定会存在一个最大的问题,而我们只需要解决了这个问题,那其下的所有问题也就解决啦!这就是我们所说的 NPC 问题的概念!!!

    引到 NP 问题里就是,对于同一类的所有的 NP 类问题,若他们都可以在多项式时间内约化成最难的一个 NP 类问题,(我们直观的认为,被约化成的问题应具有比前一个问题更复杂的时间复杂度)当我们针对这个时间复杂度最高的超级 NP 问题要是能找到他的多项式时间算法的话,那就等于变向的证明了其下的所有问题都是存在多项式算法的,即 NP = P !!!!给出 NPC 问题定义。

    (3)NPC 类问题(Nondeterminism Polynomial complete):存在这样一个 NP 问题,所有的 NP 问题都可以约化成它。换句话说,只要解决了这个问题,那么所有的 NP 问题都解决了。其定义要满足2个条件:

    首先,它得是一个 NP 问题;

    然后,所有的 NP 问题都可以约化到它。

    要证明 NPC 问题的思路就是:

    先证明它至少是一个 NP 问题,再证明其中一个已知的 NPC 问题能约化到它。

    (4)NP 难问题(NP-hard 问题)

    NP-Hard 问题是这样一种问题,它满足NPC问题定义的第二条但不一定要满足第一条(就是说,NP-Hard 问题要比 NPC 问题的范围广,NP-Hard 问题没有限定属于 NP ),即所有的 NP 问题都能约化到它,但是他不一定是一个 NP 问题。

    NP-Hard 问题同样难以找到多项式的算法,但它不列入我们的研究范围,因为它不一定是 NP 问题。即使 NPC 问题发现了多项式级的算法, NP-Hard 问题有可能仍然无法得到多项式级的算法。事实上,由于 NP-Hard 放宽了限定条件,它将有可能比所有的 NPC 问题的时间复杂度更高从而更难以解决。

    以上四个问题他们之间的关系可以用下图来表示:
    这里写图片描述
    在这里插入图片描述

    展开全文
  • 一、NP 完全的定位、 二、NP 问题 ( P = NP ) 仅做参考 [ 潜在错误 ]、 三、NP 问题 ( P ≠ NP ) 目前公认 [ 潜在正确 ]





    一、NP 完全的定位



    计算理论中三个重要概念 : P \rm P P , N P \rm NP NP , N P \rm NP NP 完全 ;


    P \rm P P , N P \rm NP NP , N P \rm NP NP 完全 , 三者的相互关系如下 :

    目前 P \rm P P N P \rm NP NP 的是否相等不确定 , 只知道 P ≤ N P \rm P \leq NP PNP ;

    如果 P ≠ N P \rm P \not= NP P=NP , 则有 P < N P \rm P < NP P<NP , 三者关系如下图左边所示 ;

    如果 P = N P \rm P = NP P=NP , 则三者关系如下图右边所示 ;

    在这里插入图片描述






    二、NP 难 问题 ( P = NP ) 仅做参考 [ 潜在错误 ]



    该观点目前认为是错误的 , 不过没有严格的证明 ;


    P = N P \rm P = NP P=NP 情况分析 : 如果 P = N P \rm P = NP P=NP , 则有 P = N P = N P \rm P = NP = NP P=NP=NP-完全 ;


    N P \rm NP NP 难问题就是 满足 N P \rm NP NP 完全问题的第二个条件 , 不满足第一个条件的问题 ,

    N P \rm NP NP 中的任何计算问题 , 难易程度 , 都不会超过当前的 计算问题 B \rm B B , 则称 B \rm B B N P \rm NP NP 难 的 ;

    N P \rm NP NP 难 问题包含了 P = N P = N P \rm P = NP = NP P=NP=NP-完全 这三种问题 ;

    03:03:45





    三、NP 难 问题 ( P ≠ NP ) 目前公认 [ 潜在正确 ]



    该观点目前认为是正确的 , 同样也没有严格的证明 ;


    P ≠ N P \rm P \not= NP P=NP 情况分析 : 如果 P ≠ N P \rm P \not= NP P=NP , 则有

    P < N P \rm P < NP P<NP ,

    N P \rm NP NP 完全 < N P \rm <NP <NP


    N P \rm NP NP 问题 中包含了三种计算问题 :

    P \rm P P 问题

    N P \rm NP NP 完全问题

    其它问题 , 既不属于 P \rm P P 问题 , 又不属于 N P \rm NP NP 完全问题 ;


    图同构问题 , 就属于 其它问题 , 既不属于 P \rm P P 问题 , 又不属于 N P \rm NP NP 完全问题 ;


    N P \rm NP NP 难 问题 , 包含了 N P \rm NP NP 完全问题 , 不包含 P \rm P P 问题 和 N P \rm NP NP 中的其它问题 ;

    在这里插入图片描述

    证明 N P \rm NP NP 完全的意义 :

    如果能够证明 计算问题 A \rm A A N P \rm NP NP 完全的 , N P \rm NP NP 完全问题 与 P \rm P P 问题 不相交 ,

    说明 该 计算问题 A \rm A A 一定没有有效算法 , 只有有效算法才会在 P \rm P P 中 ,

    因为 没有任何有效算法在 是 N P \rm NP NP 完全的 ;


    如果 计算问题 是 N P \rm NP NP 完全的 , 该算法一定不是有效算法 ;

    展开全文
  • 不同于前面所有文章中的各个具体的问题和算法,NP完全性是一个很抽象的大概念,其包括但不仅限于标题中提到的P问题、NP问题、NPC问题和NP难问题。这里我简单谈谈我对书上的内容和一些例子的理解。 P问题 首先来谈谈P...
  • P问题、NP难问题详解

    2014-03-18 19:26:11
    P问题、NP难问题详解 总结: 定义:同时满足下面两个条件的问题就是NPC问题。首先,它得是一个NP问题;然后,所有的NP问题都可以约化到它。 证明:先证明它至少是一个NP问题,再证明其中一个已知的NPC问题能约化...
  • NP难问题以及近似算法(基于次模)

    千次阅读 2020-06-27 22:14:32
    主要是对自己领域的多源定位NP问题转换和证明,以及如何设计有次摸性质的...1 NP难问题 2 如何把某个新问题规约到NP难问题,从而证明其难度NP? 3 针对NP难问题的近似算法(贪婪策略,近似比,次模) ...
  • NP问题 NP-complete问题 NP-hard问题 P问题 存在多项式时间算法的问题。(P:polynominal,多项式)。 NP问题 (NP:Nondeterministic polynominal,非确定性多项式) 能在多项式时间内验证得出一个正确解的问
  • P问题,NP问题,NP难问题

    千次阅读 2019-03-06 11:06:43
    有一则程序员界的笑话,就是有一哥们去google面试的时候被问到一个问题是:在什么情况下P=NP,然后他的回答是”当N=1的时候”。这是我第一次听说P=NP问题,大概是在临近毕业为找工作而准备的时候。 这几天科技类...
  • 如题。这里记录:P问题,NP问题,NP完全问题,NP难问题的概念。
  • 最近因为要证明np问题,所以找了一系列概念去理解这4个问题。理解的时候看到好多人给出了不同的答案,我下面会借鉴别人的答案来总结出一份对于我自己来说,最容易理解这4个问题的说法。 预备知识了解: 这部分内容...
  • 算法中的P问题、NP问题、NP完全问题和NP难问题

    万次阅读 多人点赞 2017-11-11 09:42:32
    在讨论算法的时候,常常会说到这个问题的求解是个P类问题,或者是NP难问题等等,于是我特地搜了这方面的资料,自己总结了下,估计研究算法的大家应该都知道,要是我总结的哪里不对,欢迎一起探讨~ 在讲P类...
  • 非&quot;正规&quot;问题 不可解问题:不存在解决算法的问题 例子:停机问题 ...不可能有复杂度O(多项式)问题 ...例子:输出从1到n这n个数的...P | NP P类问题:存在多项式时间算法的问题。 算法程序(...
  • 在讨论算法的时候,常常会说到这个问题的求解是个P类问题,或者是NP难问题等等,于是我特地搜了这方面的资料,自己总结了下,估计研究算法的大家应该都知道,要是我总结的哪里不对,欢迎一起探讨~ 在讲P类...
  • 看算法的时候经常会碰到NP问题、NP难问题(NPH)和NP完全问题(NPC)等术语,每次碰到的时候都似懂非懂,这次专门在网上搜了一些资料看,做一下记录,权当加深印象。 NP是指Non-deterministic Polynomial-time,即非...
  • 对于“NP难问题”的理解

    千次阅读 2017-09-04 17:37:56
    (1)确定性算法(Determinism): 设A是问题Π的一个解决算法,在算法的整个执行过程中,每一步都能得到一个确定的解,这样的算法就是确定性算法。 (2)非确定性算法(Nondeterminism):设A是求解问题Π
  • 在讨论算法的时候,常常会说到这个问题的求解是个P类问题、NP类问题、NPC类问题NP难问题。 在讲P类问题之前先介绍两个概念:多项式,时间复杂度。 多项式:ax^n^+bx^n-1^+c 在计算机算法求解问题当中,经常用...
  • NP难问题与过拟合

    千次阅读 2017-08-01 23:51:55
    以下引用于:什么是P问题NP问题和NPC问题P类问题的概念:如果一个问题可以找到一个能在多项式的时间里解决它的算法,那么这个问题就属于P问题NP问题是指可以在多项式的时间里验证一个解的问题。很显然,Hamilton...
  • 原文出处:...你要知道,大多数人此时所说的NP问题其实都是指的NPC问题。他们没有搞清楚NP问题和NPC问题的概念。NP问题并不是那种“只有搜才行”的问题,NPC问题才是。好,行了,基本上这个误解已
  • 1.实现对整数的求和,没有设计针对小数的求和。 2.在使用界面上可以选择路径,填写要求出的和。 3.数据的格式要求,新建一个文本文档,要求一个数据(必须是整数)一行,将文本文档单独放在一个文件夹下。
  • P问题:该问题存在一个可以在多项式时间内解决该问题的算法。(P:polynominal,多项式) 为什么我们要研究这个?因为计算机处理的输入常常不是那么几十个几千个那么一点点,想象一下,当计算机处理的数据达到100万个...
  • 研究计算资源中最常见的时间(要通过多少步演算才能解决问题)和空间(在解决问题时需要多少存储器) 归约: 是解决不同算法问题的一种手段。比如有两个算法任务A and B,假如任务A比任务B的复杂性低(简记为A≤B)...
  • P问题、NP问题、NPC问题、NP难问题的概念P问题、NP问题、NPC问题、NP难问题的概念, 你会经常看到网上出现“这怎么做,这不是NP问题吗”、“这个只有搜了,这已经被证明是NP问题了”之类的话。你要知道,大多数人...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 36,794
精华内容 14,717
关键字:

np难问题