算法分析与设计-2016第10讲.ppt

算法分析与设计,第10讲-2016 山东大学计算机学院/软件学院,上次内容： (1)先行约束排工，限制很强时是多项式可解的， 没有限制是NP-Complete。NPC和多项式可解有分界线吗？ 找了一个问题来说明，分界线无为有时有为无。 (2)着色问题，限制顶点度不超过4的图3着色问题是NPC， 限制平面图的3着色问题是NPC。 说明有些问题的子问题仍然为NPC，有意思，有意义。 (3)划分问题的拟多项式算法。划分问题拟多项式时间算法。,nlog2B,需要重新认识时间复杂度。,例如：B = 2n*n*n,Length(I)=n4 O(nB)=O(n2n*n*n),(1)一个问题实例的编码不是完全相同的， 因此输入长度和最大数值会跟据编码不同有所不同。 不同人编不同的程序。 (2)有的问题根本不含有数值参量，这样MAX(I)=0。 定义6.1：拟多项式算法：判定问题，存在解答算法A， 算法A的时间复杂度为：T=P(Length(I), Max(I)，I为的任意实例， 则称算法A为求解问题的拟多项式算法。 看问题：问题怎样在计算机存储?首先明确输入长度为n， 则最大数值可能是2p(n)。,在考虑算法时间复杂度时，往往忽略怎样编码的，其实编码也有学问。,问题：另外的NPC问题是否也有这么好的算法？,(1)SAT，该问题中根本没有MAX(I)这一项。 没有最大数值，Max(I)=0 (2)TSP，该问题中边长，或界值K是最大数值Max(I)项。 Max(I)=K (3)划分问题，元素价值或B是Max(I)项。O(nB) (4)团问题，最大数值，J|V|。自然受到限制。 考虑(1)，Max(I)=0，这个问题是NPC的， 可以认为，最大数值本身受到输入长度的限制。(4)也这样。 Max(I)P(Length(I)，P()是多项式函数。 考虑问题(2)(3)，TSP问题中， 边长根本不受输入长度的约束，每条边长可能很大， 问题(3)的元素价值也不受到输入长度约束。,怎样区分(1)(4)/(2)(3),什么叫不受约束：如果长度为x，则数值大小为2p(x)。 受约束的含义：存在多项式函数P()，使Max(I)P(Length(I)。 最大数值不会增大到超过输入长度的某个多项式函数的程度。 将Max(I)不受Length(I)约束的问题单独分为一类，给个命名。 定义6.2：对于判定问题，若不存在多项式函数P()， 使对问题的所有实例I有：Max(I)P(Length(I)， 则称为数问题。 最大数值不受约束。 就是最大数值可能很大的问题是数问题。不受输入长度约束。,SAT和团问题不是数问题， 划分问题和货郎问题是数问题。,证明：设不是数问题，反证：若存在拟多项式算法A， 解答问题实例I的时间复杂度为： T(I)= q(Length(I), Max(I)q(Length(I), p(Length(I) =q1(Length(I)。 其实算法A是多项式时间算法。 即：若存在解答的拟多项式算法， 则该算法是多项式算法(解答)。 则P=NP，矛盾。 问题，多项式函数P()， D()表示该问题的所有实例组成的集合。 对于多项式函数P()，定义一个新的实例集合： D(P) = I|ID() ，Max(I)P(Length(I)， 由D(P)中实例表达的问题就是多项式可解的吗。,BP(n),命题6.1：若NPC类判定问题不是数问题，PNP， 则该问题不能被拟多项式算法解答。,解释什么问题不是数问题。数值不会很大的问题。 Max(I)q(Length(I)。不存在这样的q()。,每个D(P)的实例都是D()的实例。所以P是的子问题。 注意多项式函数给定。 例如划分问题中，每个元素长度S(a)n2，n是元素个数。 P(n)=n3，则P是多项式可解的。 再次强调问题是实例的集合！,定义6.3：判定问题，存在多项式函数P， 使P是NPC的，则称是强NPC的。 (1)非数NPC问题一定是强NPC问题， 对于非数问题，NPC与强NPC是等价的。 (2)主要讨论数问题是否为强NPC问题,P中的每个实例I，都满足：Max(I)P(Length(I),命题6.2：若问题是强NPC的，PNP， 则一定不能被拟多项式算法解答。 证明：若有拟多项式算法A， 则证明A是解答p的多项式算法。 TA(I)=q(Max(I),Length(I) 因存在P()，P是NPC的。 那算法A解答P的实例I1，Max(I1)P(Length(I1) TA(I1)=q(Max(I1),Length(I1) q(P(Length(I1),Length(I1)=q1(Length(I1) 强NPC问题不能有拟多项式算法， 否则NPC问题就可以多项式解答了。 受限子问题是NPC的，能被多项式时间算法解答， 则任意NP问题都能被多项式时间算法解答。,I1D(p),TA(I)=q(Max(I),Length(I)：A是拟多项式时间算法。 TA(I)=q(Length(I)：A是多项式时间算法。,6.2强NPC类与拟多项式变换 先证明货郎问题是强NPC的。 限制货郎问题的边长不是很大，也是NPC。 结论：限制边长为1或2的TSP问题是NPC的。 HCTSP TSP实例给定完全图，每条边都有长度。 HC的图不一定是完全图，边也没有长度。,TSP: 实例：城市集合c1,cn，城市距离d(i,j)1,2,正整数K。 询问：是否存在货郎旅游，其长度不超过K？,证明：HC实例为，,将该实例变为货郎问题实例如下： d(a,b)=d(a,c)=d(a,d)=d(a,e) =d(b,c)=d(c,d)=d(c,e)=d(d,e)=1， d(b,d)= d(b,e)=2 常数K=5 显然，若HC实例存在Hamilton回路， 则相应TSP实例存在长度为K的旅游， 若TSP实例存在长度为K的旅游， 则HC实例存在Hamilton回路。,每条边的长度不超过2，可以认为Max(I)=n。 满足Max(I)Length(I)，满足这种限制的TSP仍然是NPC的。 所以TSP问题是强NPC的。 对于一个NPC问题： 如果你能说明其数值大小受限的子问题是NPC的， 则就说明这个问题是强NPC的。 受限子问题即受多项式函数P()约束的子问题。,很多人分家时，数值不必很大就很难,例子：A=11,12,13,14,15,15,11,12,17, B=40,m=3,这也是一个很典型的问题，很多人用它来证明其他问题是NPC或强NPC,1,2,3,有很多东西，省略去了，4划分是强NPC， 3划分也是强NPC。 说明：书上有很复杂的符号，不需要害怕。 很多内容，理解含义，也应该比较简单。 下面先定义什么是拟多项式变换： 定义6.4：先说明想干什么？,变换的时间复杂度也不需要是输入长度的多项式函数了！ 对所有实例，和对受P()限制的实例的变换， 是多项式时间就可以！ 时间复杂度不同。,多项式变换,1=；2= 变换f：,(1)IL1，f(I)L2， (2)1(I)=12(f(I)=1，充分必要的。 IY(1)f(I)Y(2)。不关心回答No的实例。 实际前面NTM定义中就只关心回答Yes的实例。 (3)f变换可以在p(|I|=n)时间内计算完成。,p q,企图定义一种变换，当Max(I)P(length(I)时，这个变换是多项式变换。,(1)判定问题1和2，实例集合分别为：D1，D2， (2)回答yes的实例集合为：Y1和Y2 (3)两个问题的实例编码后分别有输入长度和最大数值： Length(I)，Max(I)，LengthI，MaxI。 (4)存在一个变换f：D1D2，满足： (a)对任意实例ID1，计算f(I)的时间复杂度 是Length(I)和Max(I)的多项式函数。 T(f(I)=P(Max(I),Length(I)。 (b)IY1当且仅当f(I)Y2 (c)存在多项式函数p1()使对ID1有 LengthI p1(Lengthf(I)， 这个限制很有用，I的长度不能很大。 仔细研究的话，估计这个条件可以去掉，这个条件怪。 一般越变越长，不会变短。推导的一步需要这个条件。,为了保证2的最大数值受到输入长度约束,q1(LengthI)Lengthf(I)P(MaxI,LengthI),Lengthf(I)p2(LengthI, MaxI)， 这个由前面的条件(a)就能得到。 (d)存在两个变量的多项式函数q1,使 Maxf(I)q1(MaxI,LengthI) 则f称为1到2的拟多项式变换。 变换与数值和长度都有关。 说明：如果数值参量受到输入长度约束， 就是多项式时间变换。 条件(a)(b)是拟多项式变换的基本要求， 变换计算时间复杂度要求更宽一些。 (c)需要这个条件，保证2的实例中最大数值受到输入长度约束。 (d)要求Max(*)不能增大到超过Max(*)和Length(*)的界定范围。 拟多项式变换P, (1)Yes实例的变换 (2)受约束实例的变换 pq,(a)对任意实例ID1，计算f(I)的时间复杂度 是Length(I)和Max(I)的多项式函数。 T(f(I)=P(Max(I),Length(I)。 (b)IY(1)f(I)Y(2) (c)存在多项式函数p1()使对ID1有 LengthIp1(Lengthf(I)，,Lengthf(I)p(LengthI, MaxI)， 这个由前面的条件(a)就能得到。 (d)存在两个变量的多项式函数q1,使 Maxf(I)q1(MaxI,LengthI) 则f称为1到2的拟多项式变换。 变换与数值和长度都有关。 说明：如果数值参量受到输入长度约束， 就是多项式时间变换。 条件(a)(b)是拟多项式变换的基本要求， 变换计算时间复杂度要求更宽一些。 (c)需要这个条件，保证2的实例中最大数值受到输入长度约束。 (d)要求Max(*)不能增大到超过Max(*)和Length(*)的界定范围。 拟多项式变换P, (1)Yes实例的变换 (2)受约束实例的变换 pq,Maxf(I)q1(MaxI,LengthI) q1(q(LengthI),LengthI) q1(q(p1(Lengthf(I),p1(Lengthf(I) P1(Length(f(I),T(f(I)=P(MaxI,LengthI) P(q(LengthI),LengthI) =P1(LengthI),变换的时间复杂性,中的实例，其数值参量受约束,区间排工问题： 实例：有限任务集合，T=t1,t2,tn，只有一台机器。 r(tk)：最早起始时间 d(tk)：最晚结束时间 L(tk)：加工长度 询问：是否存在排工表：(tk)，k=1,2,n，使 d(tk)-L(tk)(tk)r(tk)，每个任务都能按时完成。 任意ti, tj，ij，|(ti)-(tj)|maxL(ti),L(tj)： 两个任务不能同时进行！ 定理6.3：区间排工是强NPC。 证明：三划分P区间排工。,前面讲过区间排工问题,相差只有1,就是说区间排工中的数值r(),d(),L()都不必很大， 问题就很难解。 子林同构: 实例：图G和H，G为树，H为林。 询问：图G是否包含一个子图与H同构。 限制G和H都是树，则该问题是多项式时间可解的。 限制G为树，H为林，则该问题是强NPC。 首先判定两个图是否完全同构是否多项式时间可解是未知的。 子林同构问题根本就没有数值参量，所谓强NPC与NPC等价的。 这个例子的意义在于说明可以用证明强NPC的方法证明NPC。,不断问自己为什么？人们会猜想区间排工也会象划分问题那样求解，其实不行。,定理6.4：子林同构问题是强NPC。 证明：三划分拟多项式变换到子林同构。 A=a1,a2,a3m，S(ai), BZ+ 构造G和H如下：,B+1个点。G,针对每个ai,构造一根长度为S(ai)的绳子。,首先说明若三划分回答yes， 则显然可以将对应的H的线图接起来对到G上去。 另外若H中的线图接到星图上形成完全G的形状， 则接到每一条线上去的线段的总长均为B， 所以原来的三划分问题一定可以三划分。,B,(3)变换的时间复杂度与B有关，(mB) 变换出来的树的点的个数与B有关。 主要说明： 限制B不大时，即为输入长度的多项式函数时， 三划分问题是NPC的， 变换本身是输入长度和最大数值的多项式函数， 所以是多项式变换 所以子林同构是NPC的。 子林同构中根本没有数值参量，当然是强NPC的。,6.3：复杂性类之间的关系 很多问题不是NP的，所以不是NPC的，但是比NPC问题更难， 这样的问题怎样说明难度。 Hamilton问题补问题： 实例：无向简单图G=(V,E) 询问：是否不存在图G的hamilton回路？ 这个问题不能确定是多项式时间可验证的，不能确定是NP的， 所以不能说是NPC的。这个问题能够正确回答， 则hamilton回路问题也能正确回答。,D1=G|G有Hamilton回路 任给G1和顶点排列，如果验证顶点排列是Hamilton回路，则G1D1,D2=G|G没有Hamilton回路 任给G2和顶点排列，如果验证顶点排列不是Hamilton回路，则不能说G2D2,假设货郎优化问题有一个多项式算法A(G,d)。 货郎判定问题实例为G,d,K 则解答货郎判定问题的算法如下： 1