精华内容
下载资源
问答
  • 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完全问题,动态规划

    千次阅读 2018-11-14 22:55:56
    NP完全问题 没办法迅速找到最优解的问题,叫做np完全问题 np完全问题可以用贪婪算法求解 涉及到集合覆盖的问题一般是np完全问题 背包问题可以用动态规划来求解 ...

    NP完全问题

    没办法迅速找到最优解的问题,叫做np完全问题
    np完全问题可以用贪婪算法求解
    涉及到集合覆盖的问题一般是np完全问题
    背包问题可以用动态规划来求解

    展开全文
  • NP,NPC,NPH,NPC问题

    千次阅读 2013-10-27 11:51:41
    一、相关概念  ...NP: 不能在多项式时间内解决或不确定能不能在多项式时间内解决,但能在多项式时间验证的问题  NPC: NP完全问题, 1)这类问题中任何一个问题至今未找到多项式时间算法; 2)如果这类

    图和部分内容转自http://www.cnblogs.com/jpcflyer/archive/2012/04/15/2450622.html

    一、相关概念  

    P: 能在多项式时间内解决的问题  

    NP: 不能在多项式时间内解决或不确定能不能在多项式时间内解决,但能在多项式时间验证的问题  

    NPC: NP完全问题,

    1)这类问题中任何一个问题至今未找到多项式时间算法;

    2)如果这类问题中的一个问题存在多项式时间算法,那么这类问题都有多项式时间算法;

    这一类问题中的每一个问题称为NP完全问题,这个问题的集合简记为NPC。所有NP问题在多项式时间内都能约化(Reducibility)到它的NP问题,即解决了此NPC问题,所有NP问题也都得到解决。  

    还可以细分为两类:1)虽然没有找到多项式时间算法,但存在一个算法,它的复杂度关于实例规模和实例的所有参数中绝对值最大数是成多项式关系的,这样的算法称为问题的一个伪多项式时间算法。

    2)除去1)的问题更难,被称为强NPC问题

    NP hard:NP难问题,所有NP问题在多项式时间内都能约化(Reducibility)到它的问题(不一定是NP问题)。


    二、四者联系

    展开全文
  • 证明一个问题NP-Hard问题

    千次阅读 2019-11-19 20:18:37
    证明一个问题NP-Hard问题 证明问题A是NP-Hard问题可以分为两步: 1)对问题A给定一个限制条件,得到问题B; 2)证明问题B是NPC问题

    证明一个问题是NP-Hard问题
    证明问题A是NP-Hard问题可以分为两步:
    1)对问题A给定一个限制条件,得到问题B;
    2)证明问题B是NPC问题。

    展开全文
  • NP问题

    2017-08-25 11:27:04
    而非多项式问题NP问题又有NP, NP hard和NP complete之分, 这两个概念经常会被人误解,一个直观的理解 NP complete问题NP hard问题就是错误的。 正确的理解,首先要知道什么是可计算的问题。 所谓可计算的...
  • NP完全问题(NP-C问题),是世界七大数学难题之一。 1.NP完全问题 人们发现,所有的完全多项式非确定性问题,都可以转换为一类叫做满足性问题的逻辑运算问题。 既然这类问题的所有可能答案,都可以在多项式时间内...
  • NP-hard问题概念理解

    万次阅读 2019-01-20 22:16:59
    在阅读“三维装箱”问题的论文时,接触到NP-hard problem的概念。该博文记录与其相关的一些概念理解。 时间复杂度:指当问题规模扩大后,程序需要的时间的增长程度,而不是表示一个程序运行需要花的时间。 多项式级...
  • NP难题

    千次阅读 2009-10-17 22:21:00
    NP: Non-deterministic Polynomial的问题,也即是多项式复杂程度的非确定性问题。NPC(NP完全理论): NP完全理论并不打算找到所谓的NP难题(也就是当前计算科学家还无法解决的问题)的算法,仅着眼证明这一类...
  • 算法中的NP问题

    千次阅读 2015-09-09 09:24:55
    多项式时间:在计算复杂度理论中,指的是一个问题的计算时间m(n)不大于问题大小n的多项式倍数。通俗点来说,多项式时间就是指时间复杂度是个多项式,或者说,就是这个程序运行的时间随着数据规模n变化的函数为f(n),...
  • 曾经虐了数学家几十年的NP问题现在终于能拿来利用了,数学家很开心,与此同时,无数个NP问题浮出水面,其中最经典的就是质因数分解问题,质因数分解的时间复杂度是一个指数,通常是O(e^n),指数是数学里的魔鬼,随着...
  • 多项式时间 P问题 NP问题

    千次阅读 2018-04-12 14:06:35
    如果x的判定问题强NP-完全的,则称x是强NP-的。 (二) 作者:uraj 链接:https://www.zhihu.com/question/27039635/answer/35040172 来源:知乎 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请...
  • NP困难问题的理解

    万次阅读 2011-03-24 21:51:00
    刚看了一点NP问题以及NP困难问题的定义,看的有点头晕。用自己的话说起来就是这样:NP问题的全称是:Non deterministic Ploynomial问题,即非确定性多项式问题。 多项式时间(Polynomial time)在计算复杂度理论中...
  • 图4.1 P、NP、NPC、NP-hard问题关系图 END 编 辑 | 王文星 责 编 | 黄章鱼 能力越,责任越大。实事求是,严谨细致。 ——where2go 团队 微信号:算法与编程之美 长按识别二维码关注我们! 温馨提示:点击...
  • 1、优化问题可转换为判定问题, 关注同样的结构指标 (1)优化问题:关注特殊结构,优化结构指标 (2)判定问题:不关注指标的最大/小值,关注阙值k 是否存在一个结构,指标与k满足某关系 (3)优化难于判定:...
  • 作者 | 夏梓耀 杏仁后端工程师,励志成为计算机艺术家本文的英文标题是:Linearizability Checking: FightingWith The NP...
  • 机器学习-支持向量机

    千次阅读 2019-11-28 16:04:44
    在二分类的例子中,SVM不仅仅找到一个决策边界将两种样本区分开,而且要保证决策边界距离两种样本的分布区域足够远,这样,当新的测试样本出现时不至于分类错误,模型泛化能力变。 上述为SVM作为最大间距分类...
  • NP问题NP-hard的关系

    千次阅读 2017-09-19 14:59:45
    P和NP指两种复杂类。 一个问题L属于复杂类P,指能够在多项式时间内找到问题LL的解。...NP-hardness:问题LL具有NP-hardness是指,对于任何NP问题,都可以归约到问题LL上,即问题LL有着比NP问题的困难性。所以
  • 图灵机和NP难度问题

    万次阅读 2011-11-19 19:57:14
    这学期选了NP难度这门课,挺感兴趣。但是在和同学讨论问题的...关于NP方面的知识涉及到很多哲学和数学的内容,有非常多的定理,很理解,这里只介绍一些基本概念。下面就从最最基本的图灵机开始说起。 1 图灵机 图
  • 约化NPC问题定义证明思路NPC意义NP难问题(NP-hard问题)解决N=NP问题的意义展望参考资料 什么是P和NP问题 背景 20世界科学家在研究如何用巨大的复古电脑解决世界上所有的问题时,第一版被使用的程式通常都会特别慢...
  • NP完全性理论与近似算法 一、图灵机 根据有限状态控制器的当前状态及每个读写头读到的带符号,图灵机的一个计算步可实现下面3个操作之一或全部。 (1)改变有限状态控制器中的状态。 (2)清除当前读写头下的...
  • NP-Hard问题--世界七大数学难题之首

    千次阅读 2020-03-04 21:01:05
    上《算法设计与分析》课程上课提到NP-Hard问题,以下是一些简单的科普。 P问题NP(Non-deterministic Polynomial )问题 所有能用多项式时间算法计算得到结果的问题,称为多项式问题,也就是P,所有绝对不可能用...
  • P、NP、NPC和NP-Hard相关概念的图形和解释

    千次阅读 多人点赞 2019-01-12 22:34:48
    P、NP、NPC和NP-Hard相关概念的图形和解释 ... 一、相关概念   &...能在多项式时间内解决的问题  NP: 不能在多项式时间内解决或不确定能不能在多项式时间内解决,但能在多项式时间...
  • 可能与不可能的边界:P/NP问题趣史

    千次阅读 2017-07-18 00:25:02
    作者:Lance Fortnow ...人们给这些问题起了一个有些奇怪的名字:P/NP问题。 P/NP是克雷数学研究所公布的7个千禧年数学难题之一,该研究所为求解这道难题设立了百万美元的奖金。不过,P/NP问题的意义远不止
  • 【知识图谱】知识图谱的基础概念与构建流程

    千次阅读 多人点赞 2019-11-09 18:46:49
    本体是结构化知识库的概念模板,通过本体库而形成的知识库不仅层次结构较,并且冗余程度较小。 3.2 知识图谱的体系架构 图2 知识图谱的技术架构 知识图谱的体系架构是其指构建模式结构,如图2所示。...
  • 等到差不多十一点半的时候,被叫到面试房间门口等待,前面还有两位同学在排队,都是投系统开发的,好像没怎么碰到投我投的创新岗的同学,聊了一会发现又是代码能力比我多了的大神,索性抱起头伸懒腰坐着佛系等候了...
  • P,NP,NPC,NP-hard问题

    2016-02-25 14:14:39
     (文中所指的“、易”是指计算复杂度的相对大小):  P问题  P问题(Polynomial Problem,多项式问题),P... NP问题(Non-Deterministic Polynomial Problem, 非确定多项式问题),是指可以在多项式时间里被...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 10,780
精华内容 4,312
热门标签
关键字:

强np难问题