NP完全问题分析
- 格式:ppt
- 大小:181.00 KB
- 文档页数:36
NP 完全问题研究P=NP 的问题有两条基本思路:1.证明NP 类中的某些问题是难解的,从而得到NP ≠P 。
但是要证明这一点几乎同证明P=NP 一样困难。
2.考察NP 类中问题之间的关系,从中找到一些具有特殊性质的、与P 类问题显著不同的问题。
沿着这一路线人们已经证明了在NP 类中存在被称为NP 完全的子类,简称NPC 问题,并由此发展了一套著名的NP 完全理论。
本节简要先介绍NP 完全性理论。
为此,首先给出各语言之间的多项式变换的概念。
定义 1 所谓从一个语言*11∑⊆L 到另一个语言*22∑⊆L 的多项式变换是指满足下面两个条件的函数*2*1:∑→∑f ,(1) 存在计算f 的一个多项式时间DTM 程序;(2) 对于所有的*1∑∈x 有:1L x ∈当且仅当2)(L x f ∈。
用21L L ∝表示存在一个从语言1L 到语言2L 的多项式变换。
相应地,对于判定问题21,∏∏,设e 1和e 2是相应的编码策略。
若],[],[2211e L e L ∏∝∏,则记为21∏∝∏。
也可以从问题的层次来叙述:由判定问题1∏到判定问题2∏的多项式变换是满足下列条件的函数21:∏∏→D D f ,(1) f 可由一个多项式时间的确定性算法来计算;(2) 对于所有的1∏∈I D 有:1∏∈I D 当且仅当2)(∏∈I Y f 。
定义2 称一个语言L (判定问题∏)为NP 完全的(NPC ),如果)(NP NP L ∈∏∈,且对于所有别的语言NP L ∈'(判定问题NP ∈∏')均有)'('∏∝∏∝L L 。
按照定义2,要证明问题∏是NP 完全的,需要证明所有的NP 问题均能够经多项式变换变成∏。
这几乎是很难做到的。
如果NP 完全问题比较多,我们也不能对每一个这样的问题都这样验证。
为此我们讨论一些NPC 问题的有用的性质。
性质1 如果L L ∝',则P L ∈意味着P L ∈'。
如何⽤整数规划求解NP完全问题如何⽤整数规划求解NP完全问题⼀、NP完全问题NP完全问题是⼀类具有⾮常⾼难度的组合最优化问题,所有NP完全问题都是NP难问题。
虽然P问题是⽐较容易的问题,NP问题却不⼀定是困难问题,必须看见NP完全或者NP难这样的字才能说这个问题求解起来很困难。
经常听砖家说,NP完全/NP难问题不能⽤整数规划求解。
实际情况怎样?实事证明砖家的话只能信⼀半:)。
这⾥咱就看看⽤整数规划求解⼀个NP完全问题⾏也不⾏。
这⾥有⼀个货真价实的整数规划问题——划分问题(The partition problem)。
问题是:给定⼀个⼤⼩不等的整数集合,问是否可以把这些整数划分成两个集合,任何⼀个整数或者在集合S1中或者在S2中,但不能同时在两个集合中;对任意给的⼀个整数集合,请设计算法,解决是否存在⼀个划分,使得S1种整数之和恰好等于S2集合的整数之和。
⼆、建⽴整数规划模型对每个整数定义⼀个0-1变量xi, xi=1 表⽰第i个整数位于集合S1中, xi=0表⽰第i个整数位于S2中。
⽤s1表⽰第⼀集合的整数之和,⽤s2表⽰第⼆个集合⾥的整数之和。
即:设d是s1和s2之间差的绝对值。
于是:我们只要极⼩化d就可以了,即:完整模型:三、上⾯的模型的⽂本表达上⾯的模型不只是⽤来摆摆看的,还可以真的被求解哈。
我们需要把模型写成⽂本格式(Leapms建模语⾔格式),让计算机理解。
⽬标函数就写成min d加上其余约束部分(注意西格玛符合的写法)subject tos1=sum{i=1,...,n}x[i]S[i]s2=sum{i=1,...,n}((1-x[i])S[i])d>=s1-s2d>=s2-s1加上符号说明(符号必须说明,不然计算机不知道哪些是常数,哪些是变量)wheren is an integerS is a sets1,s2,d are variables of numberx[i] is a variable of binary|i=1,...,n加上数据(注意整数个数是从集合S上⾃⼰数出来的)data_relationn=_$(S)dataS={11,47,159,137,85,47,142,35,119,61,88,175,13,96,-11,176,126,15,98,46,163}四、求解把如下完整模型贴到记事本上,保存为 partition.leap⽂件。
3.4 NP完全性的证明一、六个基本的NPC问题三元可满足性问题(3SAT)三维匹配问题(3DM)顶点覆盖问题(VC)团的问题哈密顿回路(HC)均分问题二、基本NP完全问题的证明三、NP完全问题的证明方法一、六个基本NP完全问题3SAT实例: 有穷布尔变量集U 和U上的子句集C={c1,c2,...,cm},其中|ci|=3, 1≤i≤m.问: 对于U是否存在满足C中所有子句的真值赋值?3DM实例: 集合M ⊆W×X×Y, 其中W,X,Y互不相交, 且|W|=|X|=|Y|=q.问: M是否包含一个匹配, 即是否存在子集M’⊆M使得|M’|= q且M’中任意两个元素的三个坐标都不相同?肯定实例:W={a1,a2,a3,a4},X={b1,b2,b3,b4},Y={c1,c2,c3,c4}M={(a1,b2,c1),(a1,b1,c1),(a2,b1,c2),(a2,b2,c1), (a3,b3,c3),(a4,b4,c4),(a4,b2,c1)}VC实例: 图G=(V,E), 正整数k≤|V|.问: G中是否存在大小不超过k的顶点覆盖, 即是否存在子集V’⊆V,使得|V’|=k, 且对每条边{u,v}∈E都有u∈V’或v∈V’?团实例: 图G=(V,E), 正整数J≤|V|.问: G是否包含大小不小于J的团, 即是否存在子集V’⊆V,使得|V’|≥J, 且V’中每两个顶点都由E中的一条边连接?独立集实例:图G=(V,E),正整数J≤|V|问:G中是否包含大小不小于J的独立集,即是否存在V’⊆V, 使得|V’|≥J,且∀u,v∈V’,{u,v}∉E?HC实例: 图G=(V,E),|V|=n.问: G 中是否包含一条哈密顿回路, 即是否有G 的顶点排列><n j j j v v v ,...,,21?},{,1,},{11E v v n i E v v j j j i j n i ∈<≤∈+∑=∑-∈∈'')()(A A a A a a S a S 使得均分实例: 有穷集合A, ∀a ∈A 有”大小”S(a)∈Z +问: 是否存在子集A ’⊆ A 使得证明顺序均分HC 团(独立集)1.3SAT∈NPC证明思路证3SAT∈NP将SAT的实例变换成3SAT的实例:根据子句中的文字个数k 分别处理1个子句转变成多个子句保证每个子句含有3个文字转变前与转变后的真值不变证显然3SAT属于NP.设U={u1,u2,...,un}, C={c1,c2,...,cm}是SAT的任何实例.对于C中任意子句c j ={z1,z2,...,zk},构造新增的变量集Uj ’和子句集Cj’.}},,}{,,{},,,{},,,{{'},{'21121121121121j j j j j j j j j j j j y y z y y z y y z y y z C y y U ==C j ’被满足⇔c j 被满足.若k=2, c j ={z 1,z 2}, 则}},,{},,,{{'}{'1211211j j j j j y z z y z z C y U ==C j ’被满足⇔z 1+z 2为真⇔c j 被满足.若k=3, 则U j ’= ∅C j ’= {c j }若k=1, c j ={z 1}, 则},,{},,,{},,,{{'},{'54223112121z z y y z y y z z C y y U j j j j j j j j ==c j 可满足⇔z 1+z 2+...+z 5为真⇒C j ’可满足如z 1+z 2为真, 则y j 1= y j 2 = F ;如z 3为真, 则y j 1= T,y j 2 = F ;如z 4+z 5为真, 则y j 1= T,y j 2 = T .反之, 若C j ’可满足而c j 不满足, 则z 1+z 2+...+z 5为假, 即z 1,z 2,...,z 5全为假, 必须y j 1=T,y j 2 =T, 最后的子句不满足.若k>3, 例如c j = {z 1,z 2,...,z 5}, 则一般若c j ={z 1,z 2,...,z k }, k>3}},,{{}41:},,{{}},,{{'}31:{'1312121k k k ji ji i j j j i j j z z y k i y z y y z z C k i y U --++⋃-≤≤⋃=-≤≤=令U ’= U ⋃U 1’⋃U 2’⋃...⋃U m ’C ’= C 1’⋃C 2’⋃...⋃C m ’下面证明f是多项式变换.易见若t满足C’, 则t满足C. 假若t不满足cj,则z 1,z2,…,zk全为假,只能有Tyyy k jjj====-321...C’的最后一个字句不满足.反之,设t:U→{T,F}是满足C的真值赋值, 将U’-U的变量分成U1’, U2’, ..., Um’, 且Uj’的变量只出现于子句Cj ’中。
NP完全的问题一个NP-完全的问题具有如下性质:它可以在多项式时间内求解,当且仅当所有的其他的NP-完全问题也可以在多项式时间内求解。
P是所有可在多项式时间内用确定算法求解的判定问题的集合。
NP 问题是所有可用多项式时间算法验证其猜测准确性的问题的集合。
令L1和L2是两个问题,如果有一确定的多项式时间算法求解L1,而这个算法使用了一个在多项式时间内求解L2的确定算法,则称L1约化为L2。
如果可满足性约化为一个问题L,则称L问题是NP-难度的。
如果L是NP难度的且L(-NP,则称L是NP-完全的。
NP并不是NON-POL YNOMIAL,把NP说成是NON-POL YNOMIAL,是望文生义,读书不求甚解。
事实上,如果你能够证明某个NP问题是个NON-POL YNOMIAL的问题,你就可以去领那七个百万美元数学大奖中间的一个了。
数学上著名的NP问题,完整的叫法是NP完全问题,也即“NP COMPLETE”问题,简单的写法,是NP=P?的问题。
问题就在这个问号上,到底是NP等于P,还是NP不等于P。
证明其中之一,便可以拿百万美元大奖。
这个奖还没有人拿到,也就是说,NP 问题到底是Polynomial,还是Non-Polynomial,尚无定论。
NP里面的N,不是Non-Polynomial的N,是Non- Deterministic,P代表Polynomial倒是对的。
NP就是Non-deterministic Polynomial的问题,也即是多项式复杂程度的非确定性问题。
如果一个判定性问题的复杂度是该问题的一个实例规模n的多项式函数,则这种可以在多项式时间内解决的判定性问题属于P类问题。
P类问题就是所有复杂度为多项式时间的问题的集合。
通俗地称所有复杂度为多项式时间的问题为易解的问题类,否则为难解的问题。
有些问题很难找到多项式时间的算法(或许根本不存在),例如“找出无向图中哈米尔顿回路”问题。
但如果给了该问题的一个答案,可以在多项式时间内判断这个答案是否正确。
P问题、NP问题、NP完全问题和NP难问题在讲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)。
取其最⾼次,可以看出,这是⼀个时间复杂度为多项式的表⽰⽅式。