精华内容
下载资源
问答
  • 定义1:一个复杂问题如果能在多项式时间内解决,那么它便被称为P问题,这意味着计算机可以在有限时间内完成计算; 定义2:可以在以多项式表达的时间内求出确切解的问题,也就是说它的计算复杂度是一个多项式。我们...

    P问题

    定义1:一个复杂问题如果能在多项式时间内解决,那么它便被称为P问题,这意味着计算机可以在有限时间内完成计算;

    定义2可以在以多项式表达的时间内求出确切解的问题,也就是说它的计算复杂度是一个多项式。我们通常用的O(n),O(logn),On2)等等类似的都是这类问题。

     

    NP问题:

    定义1np指非确定性多项式时间(nondeterministic polynomial,一个复杂问题不能确定在多项式时间内解决,假如NP问题能找到算法使其在多项式时间内解决,也就是证得了P=NP

    定义2英文是non-deterministicpolynomial,是多项式时间可以验证的问题。最初是在非确定图灵机上,如果一个问题存在一个解,那么就先猜它,一定可以在多项式时间内猜到这个解。(关键是就是不判定这个问题到底有没有解)

     

    NP-hard问题:

    是指从算法角度比NP还难的问题,指的是所有的NP问题可以通过某个多项式时间的函数规约到这类问题。就是说如果L’是NP的,且L'《pL,p是多项式表达式,那么L就是NP-hard问题。NP-hard问题不一定是NP问题,因为总有一些NP-hard问题无法在多项式时间判断一个解是否可行。

     

    NP-complete问题:

    是NP问题中最难的问题。因为NP也包含P呀,所以NP问题中有的简单,在多项式时间内就可以确定,有的相对难,只能验证。所以要区分对待一下,就把那些最难的挑出来,就是NP-complete问题了。

     

     NP-complete问题是NP-hard问题的一个子集。要证明某个问题是NP-complete问题,可以先证明它是NP的,再证明它是NP-hard

     

    NP问题更难的则是NP完全NP-hard,如围棋便是一个NP-hard问题

     

    p=NP 目前还没有被证实。也就是还不知道PNP的关系,但是可以确定的是P属于NP

    —————————————————————————————————————————————————————————————————————————————————

    定义:

    为了研究问题的复杂性,我们必须将问题抽象,为了简化问题,我们只考虑一类简单的问题,判定性问题,即提出一个问题,只需要回答yes或者 no的问题。任何一般的最优化问题都可以转化为一系列判定性问题,比如求图中从A到B的最短路径,可以转化成:从A到B是否有长度为1的路径?从A到B是否有长度为2的路径?。。。从A到B是否有长度为k的路径?如果问到了k的时候回答了yes,则停止发问,我们可以说从A到B的最短路径就是k。如果一个判定性问题的复杂度是该问题的一个实例的规模n多项式函数,则我们说这种可以在多项式时间内解决的判定性问题属于P类问题。P类问题就是所有复杂度多项式时间的问题的集合。然而有些问题很难找到多项式时间的算法(或许根本不存在),比如找出无向图中的哈米尔顿回路问题,但是我们发现如果给了我们该问题的一个答案,我们可以在多项式时间内判断这个答案是否正确。比如说对于哈米尔顿回路问题,给一个任意的回路,我们很容易判断他是否是哈米尔顿回路(只要看是不是所有的顶点都在回路中就可以了)。这种可以在多项式时间内验证一个解是否正确的问题称为NP问题。显然,所有的P类问题都是属于NP问题的,但是现在的问题是,P是否等于NP?这个问题至今还未解决。这就是P对NP问题。

     —————————————————————————————————————————————————————————————————————————————

    NPC问题:

    注意,NP问题不一定都是难解的问题,比如简单的数组排序问题是P类问题,但是P属于NP,所以也是 NP问题,你能说他很难解么?刚才说了,现在还不知道是否有P=NP或者P<>NP,但是后来人们发现还有一系列的特殊NP问题,这类问题的特殊性质使得很多人相信P<>NP,只不过现在还无法证明。这类特殊的NP问题就是NP完全问题(NPC问题,C代表complete)。 NPC问题存在着一个令人惊讶的性质,即如果一个NPC问题存在多项式时间的算法,则所有的NP问题都可以在多项式时间内求解,即P=NP成立!!这是因为,每一个NPC问题可以在多项式时间内转化成任何一个NP问题。比如前面说的哈米尔顿回路问题就是一个NPC问题。NPC问题的历史并不久,cook在 1971年找到了第一个NPC问题,此后人们又陆续发现很多NPC问题,现在可能已经有3000多个了。所以,我们一般认为NPC问题是难解的问题,因为他不太可能存在一个多项式时间的算法(如果存在则所有的NP问题都存在多项式时间算法,这太不可思议了,但是也不是不可能)。类似哈米尔顿回路/路径问题,货郎担问题,集团问题,最小边覆盖问题(注意和路径覆盖的区别),等等很多问题都是NPC问题,所以都是难解的问题。
    要解决P = NP问题,NP完全的概念非常有用。不严格的讲,NP完全问题是NP类中“最难”的问题,也就是说它们是最可能不属于P类的。这是因为任何NP中的问题可以在多项式时间内变换成为任何特定NP完全问题的一个特例。例如,旅行推销员问题的判定问题版本是NP完全的。所以NP中的任何问题的任何特例可以在多项式时间内机械地转换成旅行商问题的一个特例。 所以若旅行商问题被证明为在P内,则P = NP!旅行商问题是很多这样的NP完全的问题之一。若任何一个NP完全的问题在P内,则可以推出P = NP。不幸的是,很多重要的问题被证明为NP完全,但没有一个有已知快速的算法。[1] 
     


    参考:

    1:http://baike.baidu.com/link?url=dQ50BvB-tG82PnoMVPGjvxRJNZjeUNVeKArwFS3U5ZGmKRmZVMkp1l4KBvEZX8jwbrmqGBBnaDKUSEXHCQErNq

    2http://blog.sina.com.cn/s/blog_497d70cd0100kduk.html

     

     

    展开全文
  •  P中包含的是能在多项式时间内解决的问题,此类问题的时间复杂度不超过O(),期中n为问题输入规模,k为常数。 2、NP问题  NP中包含的是能在多项式时间内验证某个解是否正确的问题。  比如:(1)所有的P问题都...

    1、P问题

        P中包含的是能在多项式时间内解决的问题,此类问题的时间复杂度不超过O(),期中n为问题输入规模,k为常数。

    2、NP问题

        NP中包含的是能在多项式时间内验证某个解是否正确的问题。

        比如:(1)所有的P问题都是NP问题,因为我们总能在多项式时间内验证给定的某个解是否正确。

                   (2)对于某些不属于P问题的问题,如3-CNF可满足性问题,给出一组变量的赋值序列,我们很容易在多项式时间内验证其布尔表达式的值是否为真。

    3、NPC问题

       一个问题是 NPC问题必须满足:

       (1)这个问题是NP问题;(2)所有NP问题都可以归约成它。

    4、NP-Hard问题

        NP-Hard问题必须满足3中的(2),不一定满足(1)。


    四者的关系可以表示如下图:(这里认为P!=NP)




    展开全文
  • 有一些问题,我们无法用传统的方法,也就是程序化的方法解决的问题可以被称为NP问题。就好象管理学中的非常规决策一样,很难找到一个特定的程序(算法)来解决问题。 There are many tasks for which we may apply ...

    http://ahray.blog.com.cn/archives/2006/1218361.shtml
    什么是NP问题?

    有一些问题,我们无法用传统的方法,也就是程序化的方法解决的问题可以被称为NP问题。就好象管理学中的非常规决策一样,很难找到一个特定的程序(算法)来解决问题。

    There are many tasks for which we may apply fast (polynomial) algorithms. There are also some problems that cannot be solved algorithmically.

    There are many important problems in which it is very difficult to find a solution, but once we have it, it is easy to check the solution. This fact led to NP-complete problems. NP stands for nondeterministic polynomial and it means that it is possible to "guess" the solution (by some nondeterministic algorithm) and then check it.
    我收集的一些资料:
    SuperXP:售货商(旅行商问题):http://diml.ia.ac.cn/dec/web/files/npproblems/94g3.ppt
    徐连诚:算法设计与分析http://diml.ia.ac.cn/dec/web/files/npproblems/200509.ppt
    issac_chang:计算复杂度与难解性:NP Theoryhttp://diml.ia.ac.cn/dec/web/files/npproblems/ch9.ppt
    xuyun:Intro to ALGhttp://diml.ia.ac.cn/dec/web/files/npproblems/ch34.pdf
    Staal Vinterbo: Optimization and Complexity Subject: Optimization and Complexityhttp://diml.ia.ac.cn/dec/web/files/npproblems/lecture15.pdf
    sun:NP理论介绍http://diml.ia.ac.cn/dec/web/files/npproblems/np.ppt
    Lane A. Hemaspaandra:SIGACT News Complexity Theory Column 36http://diml.ia.ac.cn/dec/web/files/npproblems/poll.pdf

    转载于:https://www.cnblogs.com/zjulion/archive/2008/03/03/1089324.html

    展开全文
  • 关于在第二篇的遗传算法中,我是针对杂交出来的多个染色体进行选择的,其实我经常想,伟大的大自然,选择了优秀的基因,当然,他会让每个基因都会经过选择,不合适的毫不留情的剔除,说点本次文章以外的东西,我们...
     
    

    关于在第二篇的遗传算法中,我是针对杂交出来的多个染色体进行选择的,其实我经常想,伟大的大自然,选择了优秀的基因,当然,他会让每个基因都会经过选择,不合适的毫不留情的剔除,说点本次文章以外的东西,我们人类很伟大,我们都这么觉得,我们发明了很多东西,有着先进的医学,用来治疗各种病人,其实,这就是人为干预的自然选择,就好比,我们现在都是大脑发达,四肢却毫无力道,甚至见了一条狗我们都得给狗让道。

    幻想在远古时代,我们的祖先拿着木棍,石块来追逐凶猛的野生动物,那个时候是大自然选择了我们祖先,凡是体内杂交到了不良的基因,你会在茫茫的大地上捕猎中丧失自己的性命,毫不留情的,但是大自然却忽略了我们的团结协作,从而是一些捕猎不到食物的人也能够生存,但是,他们生存下去就是携带这不良的基因,或许是应该被淘汰的基因,随着繁衍下去,自己的基因也会繁衍下去,这对于人类究竟是退步还是进步?

    就拿中国来说,我们人口众多,但是为什么国力不强盛?按照概率来算,我们中国人很多人也继承了优良的基因,为什么我们就没有一个拿得出手的东西(除了人口),是环境没有让他表达吧!我们知道,生物的性状是有两方面决定的,一个是基因,一个是环境!

    那么对于我们这个优化,我们也从两方面入手,对于基因我们有一个模板,就是给出的那个完全图,我们的染色体都是杂交这个模板,我们这点无法改变,我们就重点放在了我们的环境中。

    我们在第二篇中是说到了一个选择到这个基因的概率,这个是1/2(1/N!),这个分母是N!,我们知道,这个不是P内的时间,是属于NP的,那我们舍弃这个,我们将只是选择一个染色体,就是说,我们不停地杂交一个染色体,知道它符合我们的条件,这样,我们就舍弃了一个限制条件,改变了我们的环境,当然,还有一个怎么不选择到这个边的概率,这个其实是约等于2的N次方除以N的N次方,关于这个式子的证明是不是NP,我会给出证明过程的,但是我还要翻翻数学书!这样我们改变我们的选择条件,去除了一个NP的式子!

    好了,今天优化到这里!

    展开全文
  • 时间复杂度并不是表示一个程序解决问题需要花多少时间,而是当问题规模扩大后,程序需要的时间长度增长得有多快。 复杂度可以分为两种级别:一种是O(1),O(log(n)),O(n^a)等,我们把它叫做多项式级的复杂度,因为它...
  • 在查询原因后,发现好像是numpy版本的问题,把numpy版本降低到1.16以下就可以解决,但是这种方法感觉很麻烦,于是尝试在原来读取的基础上加入allow_pickle=True,变为test1 = np.load('test1.npz', allow_pickle=...
  • 关于P问题、NP问题、NPC问题 首先简单说明一下时间复杂度。时间复杂度并不是表示一个程序解决问题需要花多少时间,而是当问题规模扩大后,程序需要的时间长度增长得有多快。也就是说,对于高速处理...
  • 如果一个判定性问题的复杂度是该问题的一个实例的规模n的多项式函数,则我们说这种可以在多项式时间内解决的判定性问题属于P类问题。P类问题就是所有复杂度为多项式时间的问题集合。 NP是一个判定问题类,这些...
  • 本篇文章纯粹为了记录遇到问题以及解决问题。苦于没人指引,加上网上资料少不知从何搜起,断断续续三天才弄明白,走了一些弯路。希望可以给看到这篇文章的小伙伴一点点帮助,少踩坑。 写在前面,最近碰到个问题,...
  • 看了网上很多关于这个错误的解决办法,最后管用的是一下这个 : 如果在第4步没有性能这个选项,就想我电脑这样。就选择高级-》设置-》高级 -》更改-》然后执行上述第6步骤,最后重启电脑,就可以了。现在我的可以...
  • 关于王垠对P=NP?问题的个人看法

    千次阅读 2013-05-14 22:27:46
    在牛人王垠的博客里看到一篇文章,谈了他对P=NP?...窃以为可以这样总结他的观点:1....由于NP是指的非确定图灵机在多项式时间内可以解决的问题,而非确定图灵机在实践中是不存在的,所以解决了这个问题根本没有
  • NP 问题

    2017-04-08 14:50:00
    NP问题 一、什么是NP问题? 在搞清楚NP之前,必须弄清楚P问题,P问题就是在多项式时间内可解的...那么NP就是,虽然在多项式时间内不能解决,但是能够在多项式时间内验证一个解。所以,很自然人们就想 NP和P到底...
  • 发生这种错误大概率是因为hstack(a,b)中的a和b存在sparse情况,为了解决此类问题,我们可以将np.hstack(a, b)换成np.column_stack(a, b)。
  • 报错: 源码: import numpy as np ...关于delimiter的解释: delimiter决定了np.loadtext时分隔每个元素的标志,像我的txt文本每个元素之间存在的是普通空格,而不是\tab 制表符,所以在使用np.loadtext时加
  • NP问题

    2015-05-24 16:37:39
    科学计算方法解决不了的,就只能靠科学猜想。现实世界中,任何关于不确定性预见的计算能力,都源自于对数学迷宫的理解。】  NP完全问题,是世界七大数学难题之一。 NP的英文全称是Non-deterministic ...
  • 二、解决办法: 步骤一:搜索 np_tdieplat.dll 这个程序集,发现这个程序集的引用居然是个迅雷文件 图如下:         步骤二、打开你的IE浏览器,在工具里面找到Internet选项,点击它。...
  • 本文实例讲述了python关于矩阵重复赋值覆盖问题的解决方法。分享给大家供大家参考,具体如下: import itertools import numpy as np comb = list(itertools.combinations(list(range(regions)), 2)) bands_info = ...
  • 证明np问题

    2014-01-07 13:14:48
    计算理论导引中 关于证明一个问题是否是np问题: 以clique问题subset_sum为例: 每一句的开始都是非确定地选择G中k个节点的子集c和非确定的选择S中的一个数的子集合。 当时看到的时候一直在想,这样选择是否...
  • Deploy of deployment "np-1.0-SNAPSHOT.war" was rolled back with failure message JBAS014750: Operation handler failed to complete jdk,jboss都部署成功,最后在运行jboss报错。以上是截取部分内容,解决...
  • 关于泰迪杯使用pandas无法读取数据的解决方案 \qquad当我们拿到泰迪杯的数据时,如果我们直接用pandas读取则会出现下面的情况,无法顺利的读取出数据。 import pandas as pd import numpy as np df = pd.read_csv(r...
  • 本文实例讲述了python关于矩阵重复赋值覆盖问题的解决方法。分享给大家供大家参考,具体如下:import itertoolsimport numpy as npcomb = list(itertools.combinations(list(range(regions)), 2))bands_info = []...
  • 本文实例讲述了python关于矩阵重复赋值覆盖问题的解决方法。分享给大家供大家参考,具体如下:import itertoolsimport numpy as npcomb = list(itertools.combinations(list(range(regions)), 2))bands_info = []...
  • 注意:关于math.exp()不能对矩阵直接进行操作,这里要使用np.exp(),即可解决问题。      
  • 处理前 处理后 代码 def NoData_kill(in_path, out_path): im_proj, im_geotrans, im_width, im_... mask = np.isnan(im_data) c, w, h = mask.shape mask_list = [] for i in range(c): if mask[i].__conta
  • npm install出错的解决办法 很多小伙伴可能跟我一样是个小白,还不知道怎么启动vue,然后就照着README一阵乱搞,然后npm install的时候就报了以下的错误,网上的解决办法也看不懂,我自己的解决办法来了 ...np...
  • 本文实例讲述了python关于矩阵重复赋值覆盖问题的解决方法。分享给大家供大家参考,具体如下:import itertoolsimport numpy as npcomb = list(itertools.combinations(list(range(regions)), 2))bands_info = []...
  • 将参数分开使用字典传参给优化器, 这样可以将weight 和 bias 参数分隔开 import torch ...import numpy as np ## build model class net(nn.Module): def __init__(self): super().__init__() self....

空空如也

空空如也

1 2 3 4 5 ... 12
收藏数 224
精华内容 89
关键字:

关于解决np