精华内容
下载资源
问答
  • 2020-09-29 05:34:14

     

    摘要:定义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

    更多相关内容
  • 1.P(polynominal)问题–多项式问题 存在多项式时间算法的问题。 2.NP(Nondeterministic Polynominal)问题–非确定多项式问题 能在多项式时间内验证得出一个正确解的问题。...通俗理解,NP难问题
  • 一、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 完全的 , 该算法一定不是有效算法 ;

    展开全文
  • P问题、NP难问题详解

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

    2020-04-28 23:03:53
    NP难问题求解综述 彭茗菁 2008221104210521 [摘要]: 上世纪70年代开始,诞生了一种许多数学家及电子计算器学家所关心的大问题—NP难问题, “P=NP?”这个问题,作为理论计算机科学的核心问题,其声名早...

    NP难问题求解综述

    彭茗菁

    2008221104210521

    [摘要]: 上世纪70年代开始,诞生了一种许多数学家及电子计算器学家所关心的大问题—NP难问题, “P=NP?”这个问题,作为理论计算机科学的核心问题,其声名早已经超越了这个领域。它是Clay研究所的七个百万美元大奖问题之一,在2006国际数学家大会上,它是某个1小时讲座的主题。

    [关键词]: NP难问题,NP完全问题,计算复杂性,多项式函数

     

    NP难问题,不确定性图灵机在P时间内能解决的问题,是世界七大数学难题之一。 NP问题排在百万美元大奖的首位,足见他的显赫地位和无穷魅力。NP的英文全称是Non-deterministic Polynomial的问题,即多项式复杂程度的非确定性问题。简单的写法是 NP=P?,问题就在这个问号上,到底是NP等于P,还是NP不等于P。

    一、NP难问题和P类问题的介绍

       NP问题属于“计算复杂性”研究的课题。计算复杂性通俗来说就是用计算机求解问题的难易程度。其度量标准:一是计算所需的步数或指令条数(即时间复杂度),二是计算所需的存储单元数量(即空间复杂度)。它不是对一个具体问题去研究它的计算复杂性,而是依据难度去研究各种计算问题之间的联系,按复杂性把问题分成不同的类,即复杂性类。

       如果一个判定性问题的复杂度是该问题的一个实例的规模n的多项式函数,则这种可以在多项式时间内解决的判定性问题属于P类问题。P类问题就是所有复杂度为多项式时间的问题的集合。通俗的称所有复杂度为多项式时间的问题为易解的问题类否则为难解的问题。

    然而有些问题很难找到多项式时间的算法(或许根本不存在),但是如果给了该问题的一个答案,可以在多项式时间内判断这个答案是否正确,这种可以在多项式时间内验证一个解是否正确的问题称为NP问题,亦称为易验证问题类。

       1971年 古克 (Stephen A. Cook) 发表了《The Complexity of Theorem Proving Procedures》才把 P 之外约问题归成了三大类, 即 NP, NP-complete 及 NP-hard。简单地说,存在多项式时间的算法的一类问题,称之为P类问题;而像梵塔问题,推销员旅行问题等问题,至今没有找到多项式时间算法解的一类问题,称之为NP类问题。

    二、几个常见的NP问题

       

    问题1:售货员旅行问题

    NP 问题的代表问题之一是售货员旅行问题 (traveling salesman problem)。有一个售货员要开汽车到 n 个指定的城市去推销货物,他必须经过全部的 n 个城。现在他有一个有此 n 城的地图及各城之间的公路距离,试问他应如何取最短的行程从家中出发再到家中?

         

     

    图1 售货员之地图,A,B,C,… 表城名,数字表两城之间之里数。 

       

    如图1中,A,B,C,…,G 表示 7 个城市,而售货员要从 A 城出发再回到 A 城并访问 B,C,…,G,所有的城,一个可行的方法是

    A->B->C->D->E->F->G->A

       

    加起来的结果路径总长225里。但是否存在一个更短的路径呢?目前的方法接近一个一个的排着试,还没有找到更好可以寻得最短路径的方法。对七个城而言,共有 6!=720 个排法,尚不算难,但若有 20 个城,则排法就有 19! 种。因

                               

                               

    在排列组合里 n! 写起来轻松,但 1.21 x 1017 是一个大得不得了的数字,若每秒钟排一次,要排 3.84 x 109 年(一年约为 3.15 x 107 秒), 即使使用计算器,每秒排一百万次(不容易做到)也得重做三千年才能找到答案。「生也有涯,知也无涯」,想不到区区二十个城,要三十个世纪才能找到答案。

    问题2:背袋问题(甲)

    有物体 n 个,各重 w1,w2,…,wn,今欲将它们分为二袋, 试问如何分法可使两袋之重要最为接近。 (不妨假定 wi 皆为正整数,这并未失去一般性。) 

    问题3:包装问题

    有 n 个各别重量小于 1 公斤的物品及足够可以装 1 公斤东西的盒子,今将物品装于盒子之中,多个物品可装于一盒,但任何一盒不得重于 1 公斤,试求最小的盒子数。 

    问题4:舞伴问题

    今有 n 个男孩子与 n 个女孩子参加舞会,每个男孩与女孩均交给主持一个名单, 写上他(她)中意的舞伴(至少一人,但可以多于一人)。试问主持人在收到名单后,是否可以分成 n 对,使每人均得到他(她)所喜欢的舞伴。 

    问题5:库存问题

    某仓库有 D 个存仓,排成一列,今有 n 批货物,各可占有一个或多个存仓,并已知各批物品存入与提出之日期。试问可否将各货物存入库时不发生存仓不够的困难且同一批货物若需一个以上存仓时,其存仓必须相邻。

      问题6:

    (甲) 给定一 n 位正整数 a,试问其是否为质数? 

    (乙) 给定一 n 位正整数 a,试问是否存在 m,n >1 且 a=mn? 

    问题7:分丛问题

    已知空间 n 个点,并假定各点之间之距离为正整数,又给定两正整数 K 与 B, 问是否可将此 n 点分成小于 K 个不重合的子集,使得在同一子集内之任意二点距离均不大于 B? 

       

    三、目前求解NP难问题的常见方法

    (1) 特殊情形:仔细分析所遇到的NP完全问题,研究具体实例的特殊性,考虑是否必须在最一般的意义来解此问题。也许可利用具体实例的特殊性,在特殊条件下解此问题。许多NP完全问题在特殊情形下可以找到多项式时间算法。例如求图G的最大团问题(典型描述,给定一个图G,要求G的最大团,团是指G的一个完全子团,该子团不包含在任何其他的完全子图当中,最大团指其中包含顶点最多的团)是NP完全问题,而在图G是平面图的情形下,该问题是多项式时间可解的。

    (2) 动态规划和分枝限界方法:对于许多NP完全问题来说,用动态规划和分枝限界方法常可得到较高的解题效率。

    (3) 概率分析:对于许多NP完全问题,其困难实例出现的概率很小,因此对这类NP完全问题常可设计出平均性能很好的算法。

    (4) 近似算法:通常可以设计出解NP完全问题的多项式时间近似算法,以近似解来代替最优解。

           例1

    在第二章的问题3,包装问题中,若采取「能装就装」的办法,即现有的盒子若可以装得下,就不用新盒子,则此法所需用之盒子数 k1 与最可能少的盒子数 k0 满足 。 

    证明

    今令 n 个物品之重为 w1,w2,…,wn 公斤,因每个盒子只可以装1公斤,故 

    另一方面,「能装就装」法不可能有两个以上的盒子同时少于 1/2公斤,故 


    本例得证。 

    这个问题的结果是说,我们大约可以用「能装就装」法做得最好情形的一半好。 经过较复杂的证明,Johnson 在1974年证得,当 n 很大时, 

    (i)

    ,且存在一种情形能产生。 

    (ii)

    也就是用「能装就装」法不会坏到 70% 以上,但可以坏到多用了 70% 的盒子。

    例2

    第二章问题1的售货员旅行问题的一个直观走法是先访问最近那个尚未访问过的城,称为「先访近城」法,以图1为例,其走法为 

    A->B->C->D->E->F->G->A

    Rosenkrantz 等在1977年证明这并不是一个很理想的走法,他们证出若各城间的距离满足三角不等式 7 ,则「先访近城」法所走的总程 D1 与最短路径 D0 之关系为 


    且当 n 很大时,可以有一种情形使得 

    上式中之 [x] 表示大于 x 之最小整数,例如 [5]=5, [2.5]=3。 因 当 n 大时可以很大,故 D1 可与 D0 相差非常之大,但在同一篇论文之中,Rosenkrantz 等证明另一种复杂的「直观」走法可以达到D1 ≤ 2D0之地步。 

    在上面的定理中,三角不等式的条件很重要,若城之距离无此关系存在时,Sahni 与Gonzalez 在1976年证得:若 P≠NP,则不可能存在一个有限的 m,及一个 O(nk) 计算量的走法,能使其全程长 D1 在任何 n 时满足 

    D1 ≤  mD0


    即上式中 m 非等于无限大不可,亦即所有 O(nk) 的做法都不很好。

    (5) 启发式算法:在用别的方法都不能奏效时,也可以采用启发式算法来解NP完全问题。这类方法根据具体问题的启发式搜索策略来求问题的解,在实际使用时可能很有效,但有时很难说清它的道理。

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

       人们在七十年代开始对NP完全问题的研究主要是横向发展,也就是以许多不同的计算模型来分析难解问题的本质。这些新的计算模型包括了平行计算模型、概率计算模型、布尔线路、判断树、平均复杂性、交互证明系统以及程式长度复杂性等等。对这些新的计算模型的研究一方面使我们对难解问题有了更深一层的认识,一方面也产生了一些预想不到的应用。最显著的一个例子就是计算密码学的革命性突破:基于NP问题的公钥密码体系。另一个有名的例子是线性规划的多项式时间解的发现。

       到了八十年代中,对NP完全问题的研究有了纵向的突破,在许多表面看来并不相关的计算模型之间发现了深刻的刻划关系。这些刻划关系不但解决了几个令人困扰多年的未解问题,同时也刺激了其它相关领域的发展。其中之一是对线路复杂性的研究发现了一些问题在某种有限制的线路模型中必有指数下界。这些结果使用了组合数学与概率方法等新的数学工具,并且解决了一个有名的有关多项式分层的未解问题。另一个更重大的结果是以概率可验证明对NP类的刻划。这个结果来自于对交互证明系统这个概念的扩展,并且使用了线性代数与编码理论等数学证明技巧。

       P和NP是理论计算机科学的核心问题。从数学的角度来说,它和其他历史上有名的数学问题一样,给与人们一个智力上重大的挑战。而更为重要的是,在无数与计算有关的的学术领域中,NP完全问题以各种不同形式层出不穷。因此,这并不是一个纯粹的与世独立的智力游戏,而是对计算机科学有全面影响力的问题。 

    计算机与社会科学、自然科学和思维科学等许多学科相互渗透和交叉,形成了许多新的边缘学科和新学科群,正在改变许多传统学科。分子与量子计算机的深入研究和技术难关的攻克,并最终投入运算,必将在政治、经济、军事、文化乃至人类生活的各个方面产生深刻的影响。 

    最近美国南加州大学Adleman博士应用基于DNA分子计算技术的生物实验方法有效地求解了“哈密顿路径问题”——目前计算机无法解决的NP完备问题。生物分子计算机的研制是基于生物分子的信息处理技术,即生物材料的信息处理功能与生物分子的计算技术。 

    能以叠加方式存贮信息的量子计算可生成一些真正的随机数,这是传统计算机无能为力的。数学上已证明量子计算可大大加快因式分解的速度。这一证据也吸引人们将注意力集中在根据量子力学原理制造量子计算机上。 

    计算能力超越图灵机、突破现有的体系结构是计算业界的梦想,不断有报道在DNA计算模型上找到了某NP问题的多项式算法,这应该意味着基于DNA计算模型的P类和NP类的划分会和经典模型有所不同。但是我们仍然希望量子计算能够突破图灵模式,给计算机科学带来一个崭新的世界。

    展开全文
  • P问题、NP问题、NP完全问题和NP难问题

    万次阅读 多人点赞 2019-06-12 14:06:30
    (4)NP难问题(NP-hard问题):  NP-Hard问题是这样一种问题,它满足NPC问题定义的第二条但不一定要满足第一条(就是说,NP-Hard问题要比 NPC问题的范围广,NP-Hard问题没有限定属于NP),即所有的NP问题都能...

     

     

    转载出处。 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问题的时间复杂度更高从而更难以解决。

     

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

    展开全文
  • (4)NP 问题(NP-hard 问题): NP-Hard 问题是这样一种问题,它满足NPC问题定义的第二条但不一定要满足第一条(就是说,NP-Hard 问题要比 NPC 问题的范围广,NP-Hard 问题没有限定属于 NP ),即所有的 NP 问题...
  • 这四类问题可以用时间复杂度进行区分。 函数时间复杂度具有如下规律: O(1)<O(logn)<O(nlogn)<O(n2n^2n2)<O(n3n^3n3)<...NP(Nondeterministic polynominal,非确定性多项式)问题:可以在多
  • 不同于前面所有文章中的各个具体的问题和算法,NP完全性是一个很抽象的大概念,其包括但不仅限于标题中提到的P问题、NP问题、NPC问题和NP难问题。这里我简单谈谈我对书上的内容和一些例子的理解。 P问题 首先来谈谈P...
  • 先行了解相关的几个名词: ...NP难(hard)问题是满足NPC问题的第二个条件,但不一定满足第一个条件,即NP-hard不一定是NP问题。也就是说NP-Hard问题可能无法得到多项式时间的算法。 . . . . 参考资料: ...
  • NP难问题求解综述.pdf

    2022-05-28 00:39:21
    NP难问题求解综述.pdfNP难问题求解综述.pdfNP难问题求解综述.pdfNP难问题求解综述.pdfNP难问题求解综述.pdfNP难问题求解综述.pdfNP难问题求解综述.pdfNP难问题求解综述.pdf
  • NP难问题求解综述.docx

    2022-05-28 00:27:44
    NP难问题求解综述.docxNP难问题求解综述.docxNP难问题求解综述.docxNP难问题求解综述.docxNP难问题求解综述.docxNP难问题求解综述.docxNP难问题求解综述.docxNP难问题求解综述.docx
  • 6、NPH问题: 我们又叫NP难问题,他不是一个NP问题,然后所有的NPC问题都可以在多项式时间内转化为他的话,我们就叫他NPH(hard)问题。 或 整理自:https://blog.csdn.net/wangh0802/article/details/78504754 。...
  • P是在多项式时间可以“解决”的一类问题。...NP难(NP-hard)满足NPC第二条条件,所有NP都可以规约到它,但是它本身并不一定是NP。NP-Hard问题要比 NPC问题的范围广。如TSP问题。(也就是即使有一天发现
  • P、NP、NP完全问题、NP难问题

    千次阅读 2020-09-02 23:18:35
    可以在多项式时间内求解的问题称为易解的,而不能在多项式时间内求解的问题称为解的。 P类问题:多项式类型,是一类能够用(确定性的)算法在多项式的时间内求解的判定问题。 只有判定问题才属于P 不可判定问题:...
  • P类问题是指一类能够用确定性算法在多项式时间内求解 的判定问题。NP类问题是指一类可以用不确定性多项式算法求解的判定问题。
  • NP难问题以及近似算法(基于次模)

    千次阅读 2020-06-27 22:14:32
    主要是对自己领域的多源定位NP问题转换和证明,以及如何设计有次摸性质的...1 NP难问题 2 如何把某个新问题规约到NP难问题,从而证明其难度NP? 3 针对NP难问题的近似算法(贪婪策略,近似比,次模) ...
  • (4)NP难问题(NP-hard问题):  NP-Hard问题是这样一种问题,它满足NPC问题定义的第二条但不一定要满足第一条(就是说,NP-Hard问题要比 NPC问题的范围广,NP-Hard问题没有限定属于NP),即所有的NP问题都能...
  • P问题,NP问题,NP难问题

    千次阅读 2019-03-06 11:06:43
    有一则程序员界的笑话,就是有一哥们去google面试的时候被问到一个问题是:在什么情况下P=NP,然后他的回答是”当N=1的时候”。这是我第一次听说P=NP问题,大概是在临近毕业为找工作而准备的时候。 这几天科技类...
  • 1. P类问题中的P是指什么? P:polynominal,多项式。 所以P类问题就是存在多项式时间...3.NP难问题就显而易见了,无法在多项式时间内被解决的问题,就称之为NP难问题。 NP难问题也是我们在最优化问题中,最不想
  • NP-hard问题:比NP问题都要的问题。 详细说一下这四个问题: P类问题:存在多项式时间算法的问题。(P:polynominal,多项式)。 我们为什么要研究这个P类问题呢?当计算机处理的数据达到100万个的时候,时间复杂度...
  • NP难问题固定参数可逼近算法的进展
  • NP问题 NP-complete问题 NP-hard问题 P问题 存在多项式时间算法的问题。(P:polynominal,多项式)。 NP问题 (NP:Nondeterministic polynominal,非确定性多项式) 能在多项式时间内验证得出一个正确解的问
  • P问题、NP问题、NP完全问题、NP难问题
  • 最近因为要证明np问题,所以找了一系列概念去理解这4个问题。理解的时候看到好多人给出了不同的答案,我下面会借鉴别人的答案来总结出一份对于我自己来说,最容易理解这4个问题的说法。 预备知识了解: 这部分内容...
  • (4)NP难问题(NP-hard问题):NP-Hard问题是这样一种问题,它满足NPC问题定义的第二条但不一定要满足第一条(就是说,NP-Hard问题要比 NPC问题的范围广,NP-Hard问题没有限定属于NP),即所有的NP问题都能约化到...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 42,319
精华内容 16,927
关键字:

np难