算法分析与设计-2012-第5讲.ppt

《算法分析与设计-2012-第5讲.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法分析与设计第5讲-2012山东大学计算机学院上次内容：(1)P，NP，NPC类定义，第一个NPC问题，sat，NPC，(2)Cook定理，第一个NPC问题，首先选中一些称为NP问题的问题开始研究。可认为NP-complete问题是NP问题中最难的问题。(reduction)只要讨论复杂性就会有归约的概念，归约用来比较两个问题的求解难度，是比较两个问题求解难易的工具。难和易是质区别。能多项式时间求解称为容易，不能多项式时间求解称为难。都是多项式的，可以有难和易。都是指数的，也有难和易。(3)NPC的含义，若一个NPC问题多

2、项式时间可解，则所有NP问题多项式时间可解。下面证明一些新的NPC问题。NPC问题不只一个。设=(,L,),若存在一个多项式时间的确定图灵程序M，对任意x*，xL,当且仅当存在一个up(x),M(x,u)=1.则为NP问题。12,下面的结论成立吗？1可以多项式时间求解，2可以多项式时间求解1可以多项式时间求解，2不可以多项式时间求解1不可以多项式时间求解，2不可以多项式时间求解1不可以多项式时间求解，2可以多项式时间求解易易易难难难难易由假设将问题分为多项式时间和指数时

3、间两大类而形成的学说。*若1NPC，2NP，12，则2NPC。已知satNPC，从SAT开始证明其他NPC。*万事开头难，需要找一些典型的办法。难在开始找不到合适的办法。*证明第二个NPC问题也不容易，仍然属于开头。其实，每一步进展仍然不容易，目前有许多问题是未知的。*已经证明了SAT是NPC了，其他问题是NPC的证明肯定与SAT不同了，怎么做，做个示范看看。Cook说明若SAT多项式时间可解，则所有NP问题多项式时间可解，但没有形成完整的体系来证明问题的复杂性(难度)。第四章：证明NPC类问题的技术KA

4、RP的证明，6个NPC问题，一年时间证明20多个NPC问题。定理4.1：3satNPC。(1)在集成电路测试中的应用证明在后面，先多讲几个问题实例：布尔变量集合：U={u1,…,un}，项集合：C={C1,C2,…,Cm}，

5、Ci

6、=3询问：是否存在U的真值指派使C中所有项均满足？3维对集问题3DMNPC，完美三人组合实际含义：100个编程人，100个数学推导，100个写文章的，组成100个数学建模队，但并不是任意两人都可以分到同一队，所以每个人可以与他人共事的选择并不是任意的。能组成吗？123456789101112{

7、1,2,12}；{3,2,12}；{3,5,12}；{3,5,4}；{6,5,11}；{6,7,11}；{8,7,11}；{8,9,10}。X={1,3,6,8},Y={2,5,7,9},W={4,10,11,12}问题描述：实例：集合：W,X,Y，MW*X*Y。

8、W

9、=

10、X

11、=

12、Y

13、=q询问：是否存在M的子集M’M，使

14、M’

15、=q，M’中没有任意两个3元组有相同的分量。完美匹配完美对集。例子：M={(w1,x1,y1),(w2,x1,y3),(w3,x3,y3),(w1,x2,y1),(w2,x2,y3)}M中不存在完

16、美对集M’，若M中再加上(w3,x3,y2)则可以存在M’了。完美对集是：{(w1,x1,y1)，(w2,x2,y3)，(w3,x3,y2)}(w3,x3,y2)顶点覆盖问题VCNPC：背景，通信网络，结点设探测点，每条线路最少设一头探测点，在网络上最少设几个探测点才能覆盖所有线路。例子图：是否存在2个点覆盖所有边?实例：G=(V,E),非负整数K

17、V

18、，(3)询问：是否存在V的子集V’，

19、V’

20、K，使(u,v)E，总有uV’或vV’。团问题CLNPC：背景，从100人中选择50人，互相不认识。能选出来吗？问图

21、中是否含有3个点的团。当然有。实例：无向简单图G=(V,E)，一个非负整数J

22、V

23、询问：是否存在V的子集V’V，使任意u,vV’，总有(u,v)E，且

24、V’

25、J。即V’中的点形成G的一个完全子图。定理4.1：3SATNPC证明：SAT的实例，描述实例：布尔变量集合：U={u1,…,un}，项集合：C={C1,C2,…,Cm}，询问：是否存在U的真值指派使C中所有项均满足？把上述实例变成一个3SAT的实例。先面只用一个例子说明怎样变化的，任取一个SAT的实例：U={u1,u2,u3,u4,u5}C={C1,C2,C

26、3,C4,C5}C1={u1}C2={u2,}C3={u1,,u5}C4=C2=(2)针对C2增加1个变量y21，把C2变成2个项C21=C22=把这个实例变成3SAT的实例，怎么做？(1)针对C1=(u1)，增加两个变量{y11,y12}，把C1变成4个项。C11=(u1,y11,y12