精华内容
下载资源
问答
  • 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 城的地图及各城之间的公路距离,试问他应如何取最短的行程从家中出发再到家中?

         

     

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

       

    如图1中,A,B,C,,G 表示 个城市,而售货员要从 城出发再回到 城并访问 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类的刻划。这个结果来自于对交互证明系统这个概念的扩展,并且使用了线性代数与编码理论等数学证明技巧。

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

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

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

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

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

    展开全文
  • 1.P(polynominal)问题–多项式问题 存在多项式时间算法的问题。 2.NP(Nondeterministic Polynominal)问题–非确定多项式问题 能在多项式时间内验证得出一个正确解的问题。...通俗理解,NP难问题
  • P问题、NP问题、NP完全问题、NP难问题

    一、计算复杂性
    复杂度关系:c < log2N < n < n * Log2N < n^2 < n^3 < 2^n < 3^n < n!
    二、P问题(Polynomial Solvable)
    三、NP问题(Non-determinstic Polynomial Solvable)
    五、NP-complete问题
    六、NP-hard问题

    在这里插入图片描述

    展开全文
  • 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

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





    一、NP 完全的定位



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


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

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

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

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

    在这里插入图片描述






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



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


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


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

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

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

    03:03:45





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



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


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

    P<NP\rm P < NP ,

    NP\rm NP 完全 <NP\rm <NP


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

    P\rm P 问题

    NP\rm NP 完全问题

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


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


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

    在这里插入图片描述

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

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

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

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


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

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

    万次阅读 多人点赞 2018-05-24 14:24:38
    在讲P类问题之前先介绍两个个概念:多项式,时间复杂度。(知道这两概念的可以自动跳过这部分)1、多项式:axn-bxn-1+c恩....就是长这个样子的,叫x最高次为n的多项式....咳咳,别嫌我啰嗦。。有些人说不定还真忘了啥...
  • 如题。这里记录:P问题,NP问题,NP完全问题,NP难问题的概念。
  • 算法中的P问题、NP问题、NP完全问题和NP难问题

    万次阅读 多人点赞 2017-11-11 09:42:32
    在讨论算法的时候,常常会说到这个问题的求解是个P类问题,或者是NP难问题等等,于是我特地搜了这方面的资料,自己总结了下,估计研究算法的大家应该都知道,要是我总结的哪里不对,欢迎一起探讨~ 在讲P类...
  • P问题、NP问题、NPC问题、NP难问题的概念P问题、NP问题、NPC问题、NP难问题的概念, 你会经常看到网上出现“这怎么做,这不是NP问题吗”、“这个只有搜了,这已经被证明是NP问题了”之类的话。你要知道,大多数人...
  • P问题、NP难问题详解

    2014-03-18 19:26:11
    P问题、NP难问题详解 总结: 定义:同时满足下面两个条件的问题就是NPC问题。首先,它得是一个NP问题;然后,所有的NP问题都可以约化到它。 证明:先证明它至少是一个NP问题,再证明其中一个已知的NPC问题能约化...
  • NP难问题固定参数可逼近算法的进展
  • 看算法的时候经常会碰到NP问题、NP难问题(NPH)和NP完全问题(NPC)等术语,每次碰到的时候都似懂非懂,这次专门在网上搜了一些资料看,做一下记录,权当加深印象。 NP是指Non-deterministic Polynomial-time,即非...
  • P问题、NP问题、NPC问题、NP难问题的概念 离入职尚有几天时间,闲来无事,将大家常见却又很容易搞糊涂的几个概念进行整理,希望对大家有所帮助。你会经常看到网上出现“这怎么做,这不是NP问题吗”、“这个只有搜了...
  • 不同于前面所有文章中的各个具体的问题和算法,NP完全性是一个很抽象的大概念,其包括但不仅限于标题中提到的P问题、NP问题、NPC问题和NP难问题。这里我简单谈谈我对书上的内容和一些例子的理解。 P问题 首先来谈谈P...
  • 在讨论算法的时候,常常会说到这个问题的求解是个P类问题,或者是NP难问题等等,于是我特地搜了这方面的资料,自己总结了下,估计研究算法的大家应该都知道,要是我总结的哪里不对,欢迎一起探讨~ 在讲P类问题...
  • NP难问题以及近似算法(基于次模)

    千次阅读 2020-06-27 22:14:32
    主要是对自己领域的多源定位NP问题转换和证明,以及如何设计有次摸性质的...1 NP难问题 2 如何把某个新问题规约到NP难问题,从而证明其难度NP? 3 针对NP难问题的近似算法(贪婪策略,近似比,次模) ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 822
精华内容 328
关键字:

np难问题