精华内容
下载资源
问答
  • P问题、NP问题、NP完全问题和NP难问题
    万次阅读 多人点赞
    2019-06-12 14:06:30

     

     

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

     

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

    更多相关内容
  • Python3X np.load.txt

    2019-08-18 01:20:24
    python解决np.load异常问题,适用于Python3X import numpy as np # save np.load np_load_old = np.load # modify the default parameters of np.load np.load = lambda *a,**k: np_load_old(*a, allow_pickle=True...
  • 1. 贪婪算法 1.1 算法思路 ...使用贪心算法的解决思路如下: 选出结束最早的课,它是上的第一堂课。 此时选择美术课 接下来选择第一堂课结束后才开始的课。同样,你选择结束最早的课,这将是要第...

    1. 贪婪算法

    1.1 算法思路

    贪婪算法的思想很简单:每步都采取最优的做法,以教室调度为例进行说明该算法步骤。

    假设有以下课表,希望将尽可能多的课程安排在同一个教室:

    在这里插入图片描述

    由于不同课的开始与结束时间存在冲突,所以不可能把所有课放在一个教室上。使用贪心算法的解决思路如下:

    1. 选出结束最早的课,它是上的第一堂课。 此时选择美术课
    2. 接下来选择第一堂课结束后才开始的课。同样,你选择结束最早的课,这将是要第二堂课。此时选择数学课。
    3. 重复步骤二,此步得到音乐课

    于是使用贪婪算法得到的结果就是:美术-》数学-》音乐。

    1.2 例外情况

    贪婪算法并不适合所有的场景,例如背包问题。背包问题描述如下:

    1. 假设一个背包可以放35磅重的东西,你试图通过该背包尽可能装入总价值最高的商品
    2. 商品的列表如下:
    • 音响:3000美元,30磅
    • 电脑:2000美元,20磅
    • 吉他:1500美元,15磅

    按照贪婪算法,每步都选择最优方案的话,则第一步将会选择音响,此时总价值为3000美元,背包还剩5磅的空间,然后其他的物品超过了5磅,所以也不能再进行选择。

    如果选择电脑+音响的话,总价值为3500美元,重量刚好符合要求。

    总结:当你只需找到一 个能够大致解决问题的算法,此时贪婪算法正好可派上用场,因为它们实现起来很容易,得到的结果又与正确结果相当接近。

    2. NP完全问题

    对于一些需要较大计算量才能解决的问题可理解为NP完全问题,为了可以更好的理解这个概念,以集合覆盖问题以及旅行商问题对该问题进行说明

    2.1 集合覆盖问题(组合问题)

    假设你办了个广播节目,要让全美50个州的听众都收听得到。为此,你需要决定在哪些广播台播出(全组合问题)。在每个广播台播出都需要支付费用,因此你力图在尽可能少的广播台播出。广播电视台的清单如下:
    在这里插入图片描述

    每个广播台可能覆盖多个区域,不同广播台的区域可能重叠,如何找出覆盖全美50个州的最小广播台集合呢?听起来很容易,但其实非常难。具体方法如下。

    1. 列出每个可能的广播台集合,该问题等价于有n个广播台,则存在多少种组合的可能,组合的推导公式为:
      在这里插入图片描述
    2. 从步骤一得列表中选择出可以覆盖50个州得最小集合。

    当有100个站点时,就有2的100次方个组合的可能,对于目前的计算机性能而言,该集合的数量将会成为一个计算难题。

    2.2 旅行商问题(排列问题)

    如果有N个城市需要遍历,期初可以选择的城市有N个,下一步可选择的城市为N-1个,下下步可选择的城市为N-2个…。该问题可转化为数学中的全排列问题,既有N个城市时,有N!种可能。

    该问题与集合覆盖问题类似,当N很大时,计算结果需要花费较大的计算资源。

    2.3 定义

    NP完全问题有以下几个显著的特点:

    • 元素较少时算法的运行速度非常快,但随着元素数量的增加,速度会变得非常慢。
    • 涉及“全排列”与“全组合”的问题通常是NP完全问题。
    • 不能将问题分成小问题,必须考虑各种可能的情况。这可能是NP完全问题。
    • 如果问题可转换为集合覆盖问题或旅行商问题,那它肯定是NP完全问题。

    2.4 NP完全问题的解决方案

    可以使用近似算法来解决解决该问题,该问题说明请看下节。

    3. 近似算法

    近似算法(approximation algorithm)是指由于获得精确解需要的时间太长时,可使用近
    似算法。判断近似算法优劣的标准如下:

    • 速度有多快;
    • 得到的近似解与最优解的接近程度。

    贪婪算法是近似算法的一个代表,它不仅简单,而且通常运行速度也很快。

    展开全文
  • NP=P,一种解决方案

    千次阅读 2019-12-18 18:07:07
    NP?=P 千禧难题 这里是介绍P与NP问题的. 因为笔者懒,自己搜索去吧. 前一段时间想研究一些有意义的事情,然后发现了千禧难题第一的居然是跟计算机相关的PvsNP问题,立马引起了我的兴趣. 既然跟行业相关而且是...

    NP?=P 千禧难题

    这里是介绍P与NP问题的. 因为笔者懒,自己搜索去吧.

    前一段时间想研究一些有意义的事情,然后发现了千禧难题第一的居然是跟计算机相关的PvsNP问题,立马引起了我的兴趣.
    既然跟行业相关而且是算法相关的,那么久研究一下吧,就算不能做出结果来,对于思维的锻炼也是有用的.

    然后翻墙查找了很多资料,发现了卡普的二十一個NP-完全問題.
    作为程序员,对于其中的可以编程的问题很感兴趣,大学时候概率论学的不错,其中包含排列组合,然后尝试了其中的精准覆盖问题,发现一些程序员已经解决了这个问题,主要方法是矩阵和DLX(Dancing links X算法).
    在看到这类问题已经有解决方案后,开始尝试解决其中的NPC问题: SAT问题.

    然后发现SAT问题可以规约到3-sat问题 . 已经有人做了部分工作了.
    就开始尝试自己动手写一个算法. 大概的思路是通过倒排的方式,确定部分元素的解.
    然后再通过带入的方式,将全部的问题求解掉.
    然后,翻了很多的书,做了很多的准备工作,准备做优化的时候,发现了下面这个BLOG.
    姜咏江老师的在2015年的时候,已经发现了一个方法,可以解决3-sat问题.而且时间复杂度为多项式时间.
    在科学网的介绍上

    工作情况:
    航天二院研究生部,终生特聘教师
    研究领域:
    信息科学->计算机科学->计算机体系结构

    好吧.
    程序员遇到程序员的老师了.而且发现,他的方法是可行的.并且比我的思路要走的远.已经能够在多项式时间内判定有无解,有无唯一解等等.

    姜咏江老师的方法
    传送门在这里
    这个网站居然要注册,登录才能看到一些博文,为了广大的程序员朋友们,看到具体的论述流程.
    我在这里将全文贴出来姜老师的论述过程.


    我是分割线


    前言:本文投给《中国科技论文在线》后说我已经在科学网上发表了。前在博客中发表的不够正规专业,因此将正规一些的再用> 博文发表一次,供数学计算机专业的人士讨论。

    3-SAT分段子句消去法

    姜咏江

    摘要:本文给出了3-SAT分段消去子句的求解算法。证明了可以在多项式时间求出3-SAT的解。从而证实斯提芬.库克定义下的NP-complete问题就是一个P类问题。

    关键词:NP-complete;P/NP问题;子句消去法

    中图分类号:O158

    The 3-SAT Algorithm by Sections

    JiangYongjiang

    Abstract: In this paper,I gave the remove clausemethed to get answer of the 3-SAT proplem. This is a polynomial time algorithm.It is proved the problem of NP-complete is a P class problem.

    Key words: NP-complete;P/NP problem; The clause remove method

    1. 引言

    P/NP问题曾于2000年被美国克雷数学所定为世界头号难题[1],更有甚者说其挑战了人类智慧。所谓P/NP问题的定义是这样给出的:

    复杂度类P包含所有那些可以由一个确定型图灵机在多项式表达的时间内解决的问题;类NP由所有其肯定解可以在给定正确信息的多项式时间内验证的决定问题组成,或者等效的说,那些解可以在非确定图灵机上在多项式时间内找出的问题的集合。

    实际上这个定义有很多歧义。这涉及到人们对确定型图灵机、非确定型图灵机、多项式时间、问题、决定问题、肯定解、给定正确信息、验证等一系列概念的统一认识,因而很难形成统一的见解。

    1971年斯提芬.库克 (Stephen A. Cook) 发表了《The Complexity of Theorem Proving Procedures》[2]才把P之外的问题归结为三大类,即 NP、NPC及 NPH。库克的分类得到了学术界的认可。库克给出的P、NP、NPC、NPH问题的定义如下:

    可以在多项式时间内求出解的问题,叫P问题(Polynomial problem)。

    可以在多项式的时间里验证一个解的问题,叫NP问题(Non-deterministic polynomial)。

    如果所有的NP问题都存在多项式时间算法使其能够归约为某一NP问题,则称该NP问题为NPC问题(NP-complete)。

    如果所有的NP问题都存在多项式时间算法使其归约到某问题,则称该问题为NPH问题(NP-hard)。

    所谓的多项式时间算法,就是一种函数求解过程。显然,求解方法也是一种验证方法,因而有P类问题属于NP类问题。如果NP类问题也属于P类问题,那么就有P=NP了。学术界已经证明了所有的NPC之间都有多项式时间算法实现转化。由NPC的定义不难看出,只要找到一个NPC问题的多项式时间算法,也就等于找到了所有NP问题的多项式时间算法,于是也就证明了NP=P。

    1. 典型的NPC问题

    长时间以来,人们将寻找NPC类问题的多项式时间算法作为了解决P=NP问题的关键途径。一些典型的NP类问题[3](见图1所示)早已经被一些数学家证明是NPC问题了。例如,由3个逻辑变量组成的合取范式3-CNF-SAT(简称为3-SAT)满足问题、子集和问题SUBSET-SUM、旅行商问题TSP、哈密顿回路问题HAM-CYCLE等,这些都是NPC问题寻找多项式时间算法研究的热门问题。

    图1  典型NPC问题及相关
    图1 典型NPC问题及相关
    Fig. 1 NPC Problems

    1. 3-SAT与子句消去法

    本文给出的分段子句消去法是解决如何在多项式时间求出3-SAT满足解的方法。

    3.1 3-SAT定义

    所谓的3-CNF就是多个由3个逻辑变量或其非组成的多项式间形成的与运算表达式。一般这种逻辑表达式被称为合取范式(CNF),多项式逻辑因子称为子句。

    将逻辑变量x的非运算用x’表示,集合A={x1,x2,…,xn}, A’={x1’,x2’,…,xn’},3-CNF定义如下:

    3-CNF=定义

    其中m是子句的数量,xij∈A∪A’.

    求3-CNF=1解的问题一般叫3-SAT.

    3.2 子句消去法与反子句

    由逻辑代数知,逻辑多项式的任何一项值为1,则多项式的值为1。因而欲使3-CNF=1,只要每个子句的值为1就行。

    定义1:设定子句中逻辑项值为1,并消去该项值为1的所有子句的方法,称为子句消去法。

    定义2:将子句中的项用非运算表示得到的子句叫原子句的反子句。
    定义3:子句中包含变量x与x’,则称此子句为恒一子句。

    由于恒一子句的逻辑值总是1,不影响子句消去法,所以本文后面提到的3-CNF、3-SAT、 k-CNF或合取范式等一律不包含恒一子句。

    1. 3-CNF表格式和关联段

    分段子句消去法要用到3-CNF的表格表达方式。

    4.1 3-CNF的表格式

    将逻辑变量x用1表示,x’用0表示,建立的3-CNF表格式如图2所示。子句以3位二进制数的形式占表中一行,并且规定变量相同的子句行相邻。
    在这里插入图片描述
    图2 3-CNF值格式
    Fig. 2 The form of 3-CNF

    定义4:变量相同的子句放到一起叫子句块。
    定义5:能够使子句块中全部子句消去的变量值叫块解。

    4.2 关联段

    定义6:由相同变量联接的子句块组称为关联段。

    依据定义,图2中有5个子句块的关联段。

    定义7:能使关联段中所有子句值为1的段中变量值,称为段解。
    定义8:子句块间有一个共同变量的叫一元关联。子句间有2个共同变量的叫二元关联。
    定义9:子句块间没有共同变量的子句块,称为独立段。

    显然,3-CNF有三个共同变量的子句就是子句块。

    1. 子句消去法相关定理

      为了说明子句消去法对k≥3合取范式k-CNF=1求解的有效性,我们以更一般的情况来论述本节一些内容。

    5.1 k-CNF的定理

    定理1:所有变量值都设定之后,仍然有剩余子句存在,则设定的n位数不是k-CNF=1的解,否则是解。

    证明:因为依子句消去法,消去的子句值是1,直到所有变量值设定后剩下的子句值一定是0。这些值为0的子句是合取范式的因子,必使k-CNF=0。

    定理2:子句块中若有互反子句存在,则二值都不是块解。

    证明:依据子句消去法,以子句的值为1消去的所有子句中不包括其反子句,因此总有其反子句不能被消去,则互反子句值都不是块解。

    推论1:k-CNF中子句的反子句值不是块解。
    推论2:k-CNF子句块解不超过2k-1个。
    推论3:若 k-CNF中有2k个子句的子句块存在,则k-CNF=1无解。
    定理3:从一个子句块出发确定的k-CNF=1解,也可以从另一子句块出发确定这个解。

    证明:假设由子句块A确定的解a不是由子句块B确定的解,那么因a中必含有B的一个子句值,于是可以从这个值出发,按照a的值扩充来求解,仍然是这个合取范式的一个解。于是可知,从A做起始块或B做起始块可以得到相同的解。

    由此定理可知,选择任何子句块做为起始块求解,效果一样。

    定理4:n个变量的k-CNF子句块最多有Cnk个。

    证明:显然k阶子句的变量是从n个变量中取出k个构成的集合,每个变量取值0或1就构成了子句块。依据排列组合知识,知定理成立。

    5.2 3-CNF的定理和性质

    定理5:子句块或关联段无解,则3-CNF=1无解。

    证明:因为子句块解与关联段解都是3-CNF=1解的组成部分,其无解,3-CNF=1自然无解。

    将独立的子句块也看成一个关联段,那么有下面定理6。

    定理6:3-CNF=1的求解可以分别对各关联段求解。

    证明:由3-CNF的表格式可知关联段是不重合的,并且将各关联段的解按照变量顺序组合就是3-CNF=1的解,所以可以分开求解。

    定义10:子句消去过程中剩余子句块间有相同变量,则称这些子句块为动态块,消去此动态块的变量值叫动态块解。
    定理7:动态块无解,则关联段无解。

    证明:因为动态块变量是关联段解的组成部分,所以动态块无解,其所在关联段就无解。

    定理8:确定了一个变量值的动态块其余变量的所有可能值都存在,则此次段选值不是段解。

    证明:如表1所示,如果固定了左侧3列中一个变量的值,那么剩余2个变量的值可能为右侧的2列值。如果右面2列4行值都存在,则表明无论设定剩余2个变量取任何值,都不能够将动态块的子句消除干净,因此知此次选值不是段解。

    表1 一个变量值确定其它变量值
    Tab. 1 Situation of fixed onevariable
    表1

    推论4:动态块确定一个变量值后其余2变量有3组值,则有惟一动态块解;两组或一组值,则有多个动态块解。
    推论5:子句块中变量有4子句同值,取其它值可无解。
    定理9:连续多值可选的关联段最终可确定段解。

    证明:3-CNF求解中只有一个变量值确定的动态块可以产生多解。若设定关联变量值后的剩余动态块仍然有多值可设,则可连续查找关联块,直至无解、有惟一解或有关联段的结束动态块出现。如果最终出现关联子句块无解,则关联段无解。如果出现子句块块有唯一解,可反方向设定关联变量值去确定前面每个多值动态块的解;如果多解情况最终关联的是未曾设定解的子句块,可以把子句块解设定,然后反方向去确定多解的动态子句块,最终会连成一个关联段,得到关联段的解或无解。

    1. 3-SAT分段消去算法

      运用子句消去法,可以按照关联段设定变量值,消去子句,逐步对3-CNF=1求解。

    6.1 关联段子句消去法

    运用子句消去法,可以按照关联段设定变量值,消去相关子句,逐步对3-CNF=1求解。对没有8个子句的子句块组成的数值表3-CNF,进行如下步骤的操作可以求出满足解。

    (1)将所有子句块中一个变量有4个相同值的变量设定其值,消去相应子句;

    (2)对形成表2右侧3种类型子句的动态块和只需设定一个变量值的动态块求出唯一解,并消去相应子句;

    (3)设定所有多解的剩余子句块的解,优先处理可能形成无解的情况。

    如果前面都是唯一解的情况,遇到了无法回避的表3的无解情况,那么3-SAT无解。

    依据子句消去法,若所有的关联段都有解,那么3-CNF=1就有解。其解为各关联段解的组合。

    6.2 关联段子句消去法实例

    图3给出了用分段子句消去法求3-CNF=1的例子。

    首先,本例的子句块x1x2x3选x3=0;子句块x3x4x5选x5=0;子句块x4x5x6选x6=0(见图3(1))。

    其次,消去相应子句后,有x5x6x8动态块必需确定x8=0(图3(2))

    最后,消去相应子句后,剩下了有多解的关联段(图3(3)),可以设定x1=0、x2=1将全部剩余子句消去。此3-CNF=1有解010000***。
    图3
    图3 3-CNF=1求解过程
    Fig. 3 procedue of the remove clauses

    6.3 分段子句消去法的多项式时间复杂度

    分段子句消去法,将3-CNF的子句分成了相互关联的段,并以段解来组成3-CNF=1的解。由于关联段是不重复的,所以3-CNF的关联段最多有[n/3]个,此时最多有一至两个子句块之间关联,其余子句块都是独立的。

    由于3-CNF的每个关联段都可以一次求段解操作,因而用分段子句消去法求出3-CNF=1的解或判定无解,最多需要进行[n/3]段消去子句的过程。从这一点来说,用分段子句消去法求3-CNF=1的解是一个O(n)时间复杂度的算法。

    其实,3-CNF=1是否有解,主要取决于子句数m和子句分配的结构,亦即子句之间关联的程度。3-CNF关联段子句越多,3-CNF=1的解就越少,反之解的数量会很多。当所有子句块只有一个子句并且都是独立块时,3-CNF=1会有最多的解。

    1. 结论

      3-SAT求满足解的分段子句消去法是一个多项式时间复杂度的算法。本算法证明了典型的NP-complete问题之一3-SAT是一个P类问题。依据学术界公认的观点,分段子句消去法可以说明P=NP。

    [参考文献] (References)

    [1]https://en.wikipedia.org/wiki/P_versus_NP_problem
    [2] Steven Cook. The complexity of theorem proving procedures. In Proc. ThirdAnnual ACM Symposium on the Theory of Computing, pages 151-158,1971.

    [3] Thomas H. Cormen Charles E. LeisersonRonald L. Rivest Clufford Stein. Introduction to Algorithms,Third Edition,pages1082-1104,2009.
    [4] Gilles Brassard and Paul Bratley. Fundamentals of Algorithmics. PrenticeHall,1996.

    附加一个例题:100个变量的3sat求解.xls

    2015年11月22日补充修改


    我是分割线


    个人感慨

    好了,终于把姜老师的全文都搬运过来了,姜老师的其他博客中还有关于哈密顿回路的研究.
    但是因为姜老师目前不是正统的数学研究者,转变为了"民科",导致其论文不能发表,因此目前国际上的PvsNP问题还是无解的.
    姜老师证明了,这种方法的时间复杂度,最多不超过O(n^4). 即可以在多项式时间内完成: P=NP.

    这两天准备把这个想法转变为程序,然后发现一些问题,可能还有待考虑.
    先给自己打个预防针吧.

    又回来改文章了,这个方法试验了一下,只有在已知条件特别多的情况下,才比较容易使用
    如果知道的条件特别少,这个方法就有点类似于回溯法.
    看来不那么好找到直接解了. 再研究一段时间吧

    最后想了想 这个还是不放这里了, 感觉还是有问题 是按照局部优化的思路来做的.现实中,这些排序就要做很多的工作.

    展开全文
  • NP系列问题详解

    千次阅读 2020-12-06 23:57:28
    什么是NP问题?这个是我之前比较纠结的一个问题,一直没有搞清楚它的来龙去脉。直到看了《数学之美》附录中的介绍才清楚。要清楚地了解这个问题,得从怎么衡量计算量这个问题开始。现在基本每个学习计算机相关学科的...

    ​时间复杂度

    什么是NP问题?这个是我之前比较纠结的一个问题,一直没有搞清楚它的来龙去脉。直到看了《数学之美》附录中的介绍才清楚。要清楚地了解这个问题,得从怎么衡量计算量这个问题开始。现在基本每个学习计算机相关学科的同学都知道,衡量一个算法的计算量是用时间复杂度。现在看起来理所当然的事情,在计算机科学发展初期却是个大问题,因为没有衡量算法的标准,不同算法无法比较优劣。自从有了时间复杂度后,算法优劣可以很方便地衡量,也就鼓励学者们找出更多更好的算法,好的算法也可以得到最有效的利用。提出时间复杂度的学者也因此获得了诺贝尔奖。

     

    P问题

    自从用时间复杂度来衡量计算量后,学者们开始对现有的问题分类。有一类问题是能在多项式的时间内找到解的,这类问题学者们就把它叫作多项式问题,即P问题。P是多项式的英文单词polynomial的第一个字母。什么是多项式?我们来看一下维基百科上的定义:多项式是代数学中的基础概念,是由称为不定元的变量和称为系数的常数通过有限次加减法、乘法以及自然数幂次的乘方运算得到的代数表达式。例如X^2 - 3X + 4就是一个多项式。5^X + X 就不是一个多项式,因为有非自然数的幂次的乘方运算(5的X次方)。比如快速排序算法的时间复杂度是N*logN,属于多项式问题。

     

    NP问题

    现在区分出一类问题属于多项式问题,即P问题,那剩余的其它就是目前还不能在多项式的时间内找到解的问题, 这类问题统称为非多项式问题。非多项式问题需要的计算量非常大, 现有的计算能力不能有效地解决这些问题。于是很多学者就开始研究这些问题, 看能不能在多项式的时间内找到解。随着他们研究深入, 他们发现非多项式问题中有一类问题比较特殊,虽然这类问题还不确定能不能在多项式的时间内找到解,但是这类问题可以在多项式的时间内验证一个解是否正确。即,虽然不能在多项式时间内找到解,但可以在多项式时间内验证一个解是不是正确。这类问题就是NP问题(Non-deterministic Polynomial)。

     

    NPC问题

    学者们发现NP问题后又继续研究,然后他们发现一类特殊的NP问题。特殊在什么地方呢? 特殊在所有NP问题都可以在多项式时间内归约到它。他们称这类问题为NP-Complete问题,即NPC问题。NPC问题满足两个条件:首先它是NP问题,然后所有NP问题都能在多项式时间内归约到它。也就是说,如果能在多项式时间内找到一个NPC问题的解,也就相当于能在多项式时间内找到所有NP问题的解。从上可知,NPC问题也是NP问题中最难的问题。

     

    NP-Hard问题

    学者们还发现一类问题,所有NP问题都可以归约到它,但它不一定是NP问题,也就是说它们甚至不能在多项式时间内验证一个解是否正确。学者们把这类比NPC更难的问题,甚至不属于NP问题的这一类问题称为NP-Hard问题。

     

    P问题,NP问题,NPC问题以及NP-Hard问题的关系

    如下图所示,图的纵坐标是复杂度,越往上,复杂度越高。


     

     

    目前来说,P是否等价于NP,即能不能在多项式的时间内找到NP问题的解还没有定论。P是否等价于NP这个问题也是计算机科学界最经典,争论最多的问题之一。虽然目前主流认为P是NP的子集,但因为还没办法完全验证这一点,因此不能盖棺定论。据说清华大学的姚期智老师也在研究和探索P与NP的关系,在该问题的最前沿的研究也是各执一词,有兴趣的同学可以从通过下边链接查看姚期智老师的主页和历史上针对P是否等于NP的研究结论。

     

    姚期智老师的主页:http://iiis.tsinghua.edu.cn/yao/

    历史上针对P是否等于NP的研究结论:http://www.win.tue.nl/~gwoegi/P-versus-NP.htm

     

    了解P,NP, NPC, NP-Hard问题分类的意义

    当你思考怎么解决一个问题时发现你思考了很久,挠破了头皮也没想到高效办法的时候,你可以看看你思考的问题是不是属于NP问题。如果是属于NP问题或可以归约到NP问题,那你就应该重新认识这个问题的难度了,因为世界上最聪明的人都还没找到高效解决它的办法,所以你想不出来也就正常了。

     

    更多最新文章,请扫描下边二维码,关注公众号:学习者说

    公众号二维码

     

     

    展开全文
  • DM9051NP SPI接口以太网模块是联杰国际(DAVICOM)为了方便嵌入式ARM、MCU单片机系统进行以太网通信而开发出的解决方案。
  • 这篇文章中我来简单谈谈NP完全性。不同于前面所有文章中的各个具体的问题...P问题指的是能在多项式时间内解决的问题。这里的P是Polynomial(即多项式)的缩写。初中数学告诉我们,一个多项式有如下的形式: 其中a0,a1
  • np命令之前加入。 import numpy as np
  • 太让人震惊了,要是解决了这个问题,那岂不是所有的 NP 问题都可以通过计算机来解决? 圣战的结果是,有的存在,有的不存在。=_= 在这场圣战中,人们还发现了很多的东东,也就是我们接下来要介绍的 NPC 问题(啊喂,...
  • 解决办法: 需要修改的部分 import pandas 修改为: import pandas as pd 同样的,需要修改的部分: import numpy 修改为: import numpy as np 为什么会出现这个问题呢? 原因很简单,pd 和 np都是指...
  • NP难问题求解综述

    万次阅读 2020-09-29 05:34:14
    摘要:定义NP问题及P类问题,并介绍一些常见的NP问题,以及NP问题的一些求解方法,最后最NP问题求解的发展方向做一些展望。 关键词:NP难问题 P类问题 算法 最优化问题 正文: 一.NP难问题及P类问题 为了解释NP...
  • 浅谈P/NP问题

    万次阅读 2019-09-18 18:43:47
    这也符合常理,NPC问题是NP问题规约来的,所以NPC问题的难度一定大于NP问题,只要能在多项式时间内解决NPC问题,那么NP问题也能在多项式时间内解决,此时NP问题也就变成了P问题,P=NP。  在《西游记》的第二回中...
  • 研究计算资源中最常见的时间(要通过多少步演算才能解决问题)和空间(在解决问题时需要多少存储器) 归约: 是解决不同算法问题的一种手段。比如有两个算法任务A and B,假如任务A比任务B的复杂性低(简记为A≤B)...
  • 问题背景         把 32位 python 换成64位的,我直接把之前在...解决办法         卸载后重装numpy ,初步猜想是,之前安装的是适配32位的,现在要改成64位才合适 pip uninst
  • 如果要计算一个数组中存在无效值的统计量如mean,numpy提供了nanmean对数据中出现np.nan进行处理。但有时使用numpy.ma.masked_where将该值masked了,这时候mean和nanmean都可以得到相同的想要的结果,下面是代码 a...
  • 1 基本概念 1.1 多项式和时间复杂度 (1)多项式 axn+bxn−1+cax^n+bx^{n-1}+caxn+bxn−1+c,形如这种形式的就被称为x的最高位为n的多项式。...1.2 P和NP (1)P(deterministic polynomial time quest
  • ImportError: cannot import name np_utils问题解决的过程问题描述解决过程尝试其他解决途径(来源于网络)相关知识 问题描述 安装了tensorflow-GPU,未安装好cuda(即没配置好gpu加速运算) import keras 报错,返回 ...
  • name 'np_utils' is not defined解决方法

    万次阅读 2018-10-13 14:51:13
    加入代码: from keras import utils as np_utils
  • DataFrame转成tensor 这次跑实验的时候我是直接导入了csv表格,但是我使用的是pytorch,所以必须将csv中的数据类型转化成tensor形式,要不然无法跑后面的实验。...解决方法 这样就可以正常运行了。 ...
  • NameError: name ‘np‘ is not defined解决办法

    万次阅读 多人点赞 2020-10-05 10:52:13
    NameError: name ‘np’ is not defined解决办法 在代码前加 import numpy as np 主要是记录一下自己平时遇到的问题,和大家分享一下 如有侵犯,请联系我 点个赞支持一下吧
  • 算法复杂度与NP问题

    千次阅读 2019-05-02 19:14:51
    美剧《基本演绎法》S2E2中,两位研究 NP 问题的数学家被谋杀了,凶手是同行,因为被害者即将证明“P=NP 问题”。假设人类证明了P=NP 是真的,那么就会有一个算法,能够很快算出某个帐号的密码。《基本演绎法》里面所...
  • 旧版本np.set_printoptions(threshold=np.nan) 新版本np.set_printoptions(threshold=np.inf) 显示全部数组 更正后
  • 换句话说,只要解决了这个问题,那么所有的NP问题都解决了。这种问题的存在难以置信,并且更加不可思议的是,这种问题不只一个,它有很多个,它是一类问题。这一类问题就是传说中的NPC 问题,也就是NP-完全问题。NPC...
  • P和NP问题 首先,他们都是对算法问题的复杂程度进行归类的。也就是比较时间复杂度。直观理解,目的在于评价问题的难度。哪些比哪些更难? 首先我们先要定义什么是难,什么是简单? 时间复杂度:随着输入规模(n)变...
  • NameError: name np is not defined解决方案

    万次阅读 多人点赞 2020-06-18 21:57:11
    pip install numpy -i https://pypi.mirrors.ustc.edu.cn/simple/ import numpy as np
  • np.stack()解决所有axis参数问题
  • 如何理解P和NP问题

    千次阅读 2020-05-28 22:20:30
    2000 年,美国克莱数学研究所公布了世界七大数学难题,又称千禧年大奖难题,规定对每一难题的破解者颁发一百万美元的奖金。其中 P 与 NP 问题被列为这七大数学难题之首,P与 NP 问题被列为七大世界数学难题之首。
  • 时间复杂度并不是表示一个程序解决问题需要花多少时间,而是当程序所处理的问题规模扩大后,程序需要的时间长度对应增长得有多快。 多项式复杂度 容易看出,前面的几类复杂度被分为两种级别,其中后者的复杂度无论...
  • 当数组元素比较多的时候,如果输出该数组,那么会出现省略号 解决方法:在程序前写如下代码 import numpy as np np.set_printoptions(threshold=np.inf)

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 116,039
精华内容 46,415
关键字:

关于解决np