算法分析与设计2007第a讲

第A讲第1页上次内容：(1)先行约束排工，限制很强时是多项式可解的，没有限制是NP-Complete。(2)着色问题，限制顶点度不超过4的图3着色问题是NPC，限制平面图的3着色问题是NPC。(3)拟多项式变换与NPC类，划分问题的拟多项式算法。划分问题拟多项式时间算法。一个问题中有两个参数影响时间复杂度：划分问题。输入长度：Length(I)=|A|log2|A|+|A|log2(AaiiaS)()最大数值：问题的实例中碰到的最大数值。Max(I)=B=AaiiaS)(说明：可以设计算法与两个参数有关系。一个问题的编码不是完全相同的，因此输入长度和最大数值会根据编码不同有所不同。一般来说，不管用什么样的编码，输入长度是差不多的，多项式相关的。不同人编不同的程序。有的问题根本不含有数值参量，这样MAX(I)=0。划分问题算法时间复杂性：O(nB)定义6.1：拟多项式算法：判定问题，存在解答算法，算法的时间复杂度为：T(I)=P(Length(I),Max(I))，I为任意实例，则该算法称为求解问题的拟多项式算法。看问题：最好讲讲怎样问题怎样在计算机输入?首先明确输入长度为n，则最大数值可能是2n。(1)SAT，该问题中根本没有Max(I)这一项。没有最大数值，Max(I)=0(2)团问题，最大数值，J|V|。自然受到限制。第A讲第2页(3)TSP，该问题中边长或K是最大数值Max(I)项。(4)划分问题，元素重量是Max(I)项。O(nB)考虑(1)，Max(I)=0，这个问题是NPC的，可以认为，最大数值本身受到输入长度的限制。Max(I)P(Length(I))考虑问题(2)团问题中的数值参量受到输入长度约束。J|V|。Max(I)P(Length(I))(3)TSP问题中，边长根本不受输入长度的约束，每条边长可能很大，问题3的元素重量也不受到输入长度约束。函数P不存在，使Max(I)P(Length(I))。(4)划分问题中，元素价值不受输入长度的约束。函数P不存在，使Max(I)P(Length(I))。受约束的含义：存在多项式函数P(*)，使Max(I)P(Length(I))。n位输入，则数值大小为2n，Max(I)=2Length(I)P(Length(I))Max(I)=)(2ILengthP(Length(I))定义6.2：对于判定问题，若不存在多项式函数P，使对所有实例I有：Max(I)P(Length(I))，则称为数问题。最大数值不受约束。就是最大数值可能很大的问题是数问题。不受输入长度约束。命题6.1：若判定问题是NPC类，不是数问题，PNP，则该问题不能被拟多项式算法解答。解释什么问题不是数问题。证明：T=q(Length(I),Max(I))q(length(I),p(length(I)))=q1(length(I))。第A讲第3页若有拟多项式算法，则有多项式算法，则P=NP，矛盾。下面是几个问题，多项式函数P，D()表示该问题的所有实例组成的集合。定义一个新的实例集合：D(P)={I|ID(),Max(I)P(Length(I))}，由D(P)中实例表达的问题就是多项式可解的吗。注意多项式函数给定。再次强调问题是实例的集合！ID()ID(P)定义6.3：判定问题，存在多项式函数P，使P是NPC的，则称是强NPC的。命题6.2：若问题是强NPC的，PNP，则一定不能被拟多项式算法解答。强NPC问题不能有拟多项式算法，否则NPC问题就可以多项式解答了。受限子问题是NPC的，能被多项式时间算法解答，则任意NP问题都能被多项式时间算法解答。§6.2证明强NPC与拟多项式变换先证明货郎问题是强NPC的。限制货郎问题的边长不是很大，也是NPC。HCTSPHC实例为：第A讲第4页aedcbaedcb1111111221将该实例变为货郎问题实例如下：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)=2n。满足下式否？Max(I)Length(I)，满足这种限制的TSP仍然是NPC的。所以TSP问题是强NPC的。对于一个NPC问题，如果你能说明其受限子问题是NPC的，则就说明这个问题是强NPC的。货郎问题就不可能有拟多项式算法：P(Max(I),Length(I))=P(2n,q(n))，拟多项式算法就是多项式算法。先讲一个问题，3划分问题实例：讲清楚，但不证明。第A讲第5页(1)集合A，含有3m个元素，A={a1,a2,…,a3m}，(2)S(ai)Z+，(3)存在正整数BZ+，满足：B/4S(ai)B/2，(4)mBaSAaii)(询问：是否存在A的划分：A=S1S2…Sm，即将A划分为m个子集，使iiSaiaS)(=B。简单解释：***三划分不是划分为三份。(1)划分的每个子集中肯定是3个元素。因为：B/4S(ai)B/2。(2)每个集合中3个元素，就是3划分的含义。有很多东西，我们不讲了，4划分是强NPC，3划分也是强NPC。说明：不要看书上有很复杂的符号，很多内容，实际当你看懂得时候也很简单。下面先定义什么是拟多项式变换：D(1P)D(1)D(2)D(2q)定义6.4：(1)判定问题1和2，实例集合分别为：D1，D2，(2)回答yes的实例集合为：Y1和Y2第A讲第6页(3)两个问题的实例编码后分别有：Length(I)，Max(I)，Length’[f(I)]，Max’[f(I)]。(4)存在一个变换f：D1D2，满足：(a)对任意实例ID1，计算f(I)的时间复杂度是Length(I)和Max(I)的多项式函数。T(f(I))=P(Max(I),Length(I))。(b)对ID1，IY1当且仅当f(I)Y2(c)存在多项式函数p1使对ID1有Length[I]p1(Length’[f(I)])，这个限制很有用，I的长度不能很大。仔细研究研究的话，估计这个条件可以去掉。Length’[f(I)]p2(Length[I],Max[I])，这个由前面就能得到。(d)存在两个变量的多项式函数q1,使Max’[f(I)]q1(Max[I],Length[I])则f称为1到2的拟多项式变换。变换与数值和长度都有关。说明：如果数值量受到输入长度限制，就是多项式时间变换。条件(a)(b)是拟多项式变换的基本要求，变换计算时间复杂度要求更宽一些。(c)Length[f(I)]p2(Length[I],Max[I])，(d)要求Max’(*)不能增大到超过Max(*)和Length(*)的界定范围。引理6.1：是强NPC，’是NP问题，存在一个到’的拟多项式变第A讲第7页换，则判定问题’也是强NPC的。证明：将和’中的最大数值都限定受输入长度的多项式限制，则受限制的是NPC问题，存在的拟多项式变换就是多项式变换，所以受限制的’是NPC的，所以不受限制的’是强NPC的。实例：有限任务集合，T={t1,t2,…,tn}，只有一台机器。r(tk)：最早起始时间d(tk)：最晚结束时间L(tk)：加工长度询问：是否存在排工表：(tk)，k=1,2,…,n，使d(tk)-L(tk)(tk)r(tk)，每个任务都能按时完成。任意ti,tj，ij，|(ti)-(tj)|max{L(ti),L(tj)}将前面的区间排工拷贝过来的定理6.3：区间排工是强NPC。证明：三划分P区间排工。三划分的实例：A={a1,a2,a3,…,a3m}，S(ai)Z+，BZ+。由此构造区间排工实例：T=A{t1,t2,…,tm-1}L(t1)=L(t2)=…=L(tm-1)=1L(ai)=S(ai)，i=1,…,3mr(ti)=iB+i-1，i=1,…,m-1；d(ti)=iB+i,i=1,…,m-1第A讲第8页r(ai)=0，i=1,…,3md(ai)=mB+m-1说明：3111()()mmiiiiLaLt=mB+m-1，所以从0开始，总用时间是mB+m-1t1t2t3tm-1BB+12B+12B+23B+23B+3(m-1)B+m-2mB+m-1BBBB(1)变换可以在三划分实例输入长度的多项式时间内完成。(2)若三划分实例回答yes，则变换后的区间排工实例也回答yes，若区间排工实例回答yes，则相应三划分实例一定有一个三划分。(3)条件(c)几乎总是满足。Length[I]p1(Length’[f(I)])(4)最大数值变化不大。符合条件(d)。三划分中的最大数值为B,区间排工的最大数值为：mB+m-1，当然是B的多项式函数。所以是强NPC。子林同构实例：图G和H，询问：图G是否包含一个子图与H同构。限制G和H都是树，则该问题是多项式时间可解的。限制G为树，H为林，则该问题是强NPC。首先判定两个图是否完全同构也是多项式时间可解的。子林同构问题根本就没有数值参量，所谓强NPC与NPC等价的。这个例子的意义第A讲第9页在于说明可以用证明强NPC的方法证明NPC。定理6.4：子林同构问题是强NPC。证明：三划分拟多项式变换到子林同构。A={a1,a2,…,a3m}，S(ai),BZ+构造G和H如下：B+1个点。GH构造为：(1)(2)aiS(ai)个点的线：S(ai)个点的线。首先说明若三划分回答yes，则显然可以将对应的H的线图接起来对到G上去。另外若H中的线图接到星图上形成完全G的形状，则接到每一条线上去的线段的总长均为B，所以原来的三划分问题一定可以三划分。(3)变换的时间复杂度与B有关，变换出来的树的点的个数与B有关。主要说明：限制B不大时，即为输入长度的多项式函数时，三划分问题是NPC第A讲第10页的，变换本身是输入长度和最大数值的多项式函数，所以是多项式变换所以子林同构是NPC的。子林同构中根本没有数值参量，当然是强NPC的。§6.3：复杂性类之间的关系很多问题不是NP的，所以不是NPC的，但是比NPC问题更难，这样的问题怎样说明难度。Hamilton问题补问题：实例：无向简单图G=(V,E)询问：图G没有hamilton回路吗？这个问题不是多项式时间可验证的，不是NP的，所以不能说是NPC的。这个问题能够正确回答，则hamilton回路问题也能正确回答。Tsp优化问题：实例：城市集合C={C1,…,Cm}，城市之间距离d(Ci,Cj)，询问：求城市排列：*1C，*2C,…,*mC使miiiCCd1*1*),(=min{miiiCCd11),(|C1C2…Cm为城市排列}这个问题也不是NP的，所以不是NPC的。这个问题能够正确回答，货郎判定问题也能正确回答。在问题中要找一个解的问题称为搜索问题。第A讲第11页多项式归约，本身就说明一件事，若2能多项式时间正确解答，则1也能多项式时间正确解答。所以有turing规约的概念：图灵规约是多项式变换概念的推广。先举个例子：假设货有一个货郎优化问题的算法为A设计货郎判定问题求解算法如下：假设货郎判定问题的实例为G,d,K1调用算法A(G,d)求得最优解，设得到的最短旅游长度为OPT(G,d).2若OPT(G,d)K，则回答yes，否则回答no。turing规约是用神喻图灵机定义的，那是为了严格，这里就不再讲神喻图灵机了。讲一下直观的定义：条件：(1)1是一个搜索问题，2是一个搜索问题。(2)可以设计一个求解1的算法，算法中调用求解2的算法A(2)。(3)若A(2)的时间复杂度记为O(1)，则求解