《算法分析与设计2009第a讲》由会员分享，可在线阅读，更多相关《算法分析与设计2009第a讲（14页珍藏版）》请在金锄头文库上搜索。
1、上次内容：(1)先行约束排工，限制很强时是多项式可解的，没有限制是NP-Complete。着色问题，限制顶点度不超过4的图3着色问题是NPC,限制平面图的3着色问题是NPC。(3)拟多项式变换与NPC类，划分问题的拟多项式算法。划分问题拟多项式时间算法。一个问题实例中有两个因素影响算法时间复杂度：划分问题。输入长度：Length(I)=IAIlog2IAI+IAIlog2(工s(a)ia eAi最大数值：问题的实例中碰到的最大数值。Max(I)=B=工 S (a )iaeAi算法时间复杂性： O(nB)=P(Length(I),Max(I)说明：可以设计算法与两个参数有关系。 一个问题的编码不
2、是完全相同的，因此输入长度和最大数值会根 据编码不同有所不同。不同人编不同的程序。有的问题根本不含有数值参量，这样MAX(I)=0o定义6.1：拟多项式算法：判定问题I，存在解答算法A，算法A的时 间复杂度为：T=P(Length(I), Max(I)，I为任意实例，则称算法A为 求解问题兀的拟多项式算法。看问题：问题怎样在计算机存储?首先明确输入长度为n则最大数值可能是 2no(l)SAT，该问题中根本没有MAX(I)这一项。没有最大数值，Max(I)=0 TSP，该问题中边长或K是最大数值MAX(I)项。(3) 划分问题，元素重量或B是Max(I)项。O(nB)(4) 团问题，最大数值，J
3、VV1。自然受到限制。考虑(1), Max(I)=O,这个问题是NPC的，可以认为，最大数值本身 受到输入长度的限制。Max(I)P(Length(I), P()是多项式函数。 考虑问题(2)(3)，TSP问题中，边长根本不受输入长度的约束，每条 边长可能很大,问题 3 的元素重量也不受到输入长度约束。受约束的含义：存在多项式函数P()，使Max(I)P(Length(I) 将Max(I)不受Length约束的问题单独分为一类，给个名份。定义6.2：对于判定问题兀，若不存在多项式函数P()，使对所有实例 I有：Max(I)P(Length(I)，则称兀为数问题。最大数值不受约束。就是最大数值可
4、能很大的问题是数问题。不受输入长度约束 命题6.1：若判定问题不是数问题，pNP,则该问题不能被拟多项式 算法解答。解释什么问题不是数问题。证明：设兀不是数问题，T= q(LengthQ), Max(I)q(length(I),p(length(I) =q1(length(I)o若存在解答兀的拟多项式算法，则有多项式算法解答兀, 则p=np，矛盾。问题兀，多项式函数p(), D(兀)表示该问题的所有实例组成的集合。对 于多项式函数P(町，定义一个新的实例集合：D(兀p) = IlIeD ,p兀Max(I)P(Length(I),由D(兀丿中实例表达的问题就是多项式可解的 吗。注意多项式函数给定
5、。例如划分问题中，每个元素长度S(a)n2, n是元素个数。P(n)=n2, 则兀p是多项式可解得。再次强调问题是实例的集合！定义6.3：判定问题兀，存在多项式函数P,使兀戶是NPC的，则称兀是强NPC的。非数NPC问题一定是强NPC问题(2)主要讨论数问题是否为强NPC问题命题6.2：若问题兀是强NPC的，PhNP,贝肮一定不能被拟多项式算法解答。强NPC问题不能有拟多项式算法，否则NPC问题就可以多项式解答了。受限子问题是NPC的，能被多项式时间算法解答，则任意NP问题都能被多项式时间算法 解答。6.2证明强NPC与拟多项式变换先证明货郎问题是强NPC的。限制货郎问题的边长不是很大，也是n
6、pc。结论：限制边长为1或2的TSP问题是NPC的。HCxTSPHC 实例为：cc将该实例变为货郎问题实例如下：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(1)=2。满足下式否？ Max(I)Length(I),满足这种限制的TSP仍然是NPC的。所以TSP 问题是强NPC的。对于一个NP
7、C问题，如果你能说明其受限子问题是NPC的，则就说 明这个问题是强NPC的。先讲一个问题，3划分问题实例：讲清楚，但不证明。集合A,含有3m个元素，A=a,a2，.,a3m,S(a戶Z+,(3)存在正整数 BgZ+，满足：B/4S(ai)B/2，工S (a ) 二 mBia eAi询问：是否存在A的划分：A=S1uS2U.uS，即将A划分为m个子12m集，使工S(a )=B。iaieSi简单解释： *三划分不是划分为三份。(1) 划分的每个子集中肯定是3个元素。因为：B/4S(ai)B/2o(2) 每个集合中3个元素，就是3划分的含义。有很多东西，我们不讲了，4 划分是强 NPC，3 划分也是
8、强 NPC。 说明：不要看书上有很复杂的符号，很多内容，看懂也应该比较简单。 下面先定义什么是拟多项式变换：定义 6.4：(1) 判定问题兀和兀2，实例集合分别为：D , D 2，1 2 1 2(2) 回答 yes 的实例集合为： Y 1和 Y 2(3) 两个问题的实例编码后分别有： Length(I)， Max(I)， Lengthf(I)， Maxf(I)。(4) 存在一个变换f： D計D池，满足：(a)对任意实例I叫,计算f(I)的时间复杂度是Length(I)和Max(I)的 多项式函数。T(f(I)=P(Max(I),Length(I)的对IeD 1，1叫1当且仅当f(I)eF2(c
9、) 存在多项式函数p1()使对IwD冗有Length Ip 1 (Length f(I)，这个限制很有用，i的长度不能很大。仔细研究研究的话，估计这个条件可以去掉。一般越变越长，不会变短。推导的一步需要这个条件。Lengthf(I)p2(LengthI, MaxI)，这个由前面就能得到。(d) 存在两个变量的多项式函数q,使Maxf(I)o(tk)r(tk)，每个任务都能按时完成。 任意 t, t.， ij lc(t )p(t .)lmaxL(t ),L(t.)I Jijij定理6.3：区间排工是强NPC。 证明：三划分区卩区间排工。三划分的实例：A=a,a2,a3，,a3 ，S(a.)wZ+
10、, BwZ+。12 3 3mi由此构造区间排工实例：T=AUti，t2,tm-1L(ai)=S(ai)， i=1,.,3mL(t1) = L(t2) = = L(tm-1) = 1迅 L(a )+ 艺 L(t )=mB+m-1iir(a.)=0, i=l,.i.,3md(a.)=mB+m-1r(ti)=iB+i-1 , i=1, , m-1 ；d(ti) = iB+i, i = 1, , m-1说明：迟L(a )+艺L(t) =mB+m-1，所以从0开始，总用时间是mB+m-1 ii亠Tdt1亠 O ht2ot3m-1BP B BB(1) 变换可以在三划分实例输入长度的多项式时间内完成。(2)
11、 若三划分实例回答yes,则变换后的区间排工实例也回答yes,若 区间排工实例回答yes，则相应三划分实例一定有一个三划分。(3) 条件(c)几乎总是满足(4) 最大数值变化不大。符合条件(d)。三划分中的最大数值为B,区间 排工的最大数值为：mB+m-1，当然是B的多项式函数。所以区间排工是强NPC。就是说区间排工中的数值r(e),d(e),L(e)都不必很大，问题就很难解。子林同构实例：图G和H, G为树，H为林。询问：图G是否包含一个子图与H同构。限制G和H都是树，则该问题是多项式时间可解的。限制G为树，H为林，则该问题是强NPC。首先判定两个图是否完全同构也是多项式时间可解的。子林同构
12、问题 根本就没有数值参量，所谓强NPC与NPC等价的。这个例子的意义 在于说明可以用证明强NPC的方法证明NPC。定理6.4：子林同构问题是强NPC。证明：三划分拟多项式变换到子林同构。A=a,a2,a3m, S(ai), BeZ+构造G和H如下：B+1个点。GI I IH 构造为：(1)(2)aiS(ai)个点的线:JS(a.)个点的线。首先说明若三划分回答yes,则显然可以将对应的H的线图接起来对 到 G 上去。另外若H中的线图接到星图上形成完全G的形状，则接到每一条线所以原来的三划分问题一定可以三划分。(3) 变换的时间复杂度与B有关,变换出来的树的点的个数与B有关。主要说明：限制B不大
13、时，即为输入长度的多项式函数时,三划分问题是NPC 的， 变换本身是输入长度和最大数值的多项式函数，所以是多项式变 换 所以子林同构是 NPC 的。 子林同构中根本没有数值参量，当然是强 NPC 的。 6.3：复杂性类之间的关系很多问题不是 NP 的，所以不是 NPC 的，但是比 NPC 问题更难，这 样的问题怎样说明难度。Hamilton 问题补问题： 实例：无向简单图 G=(V,E) 询问：图 G 没有 hamilton 回路吗？ 这个问题不能确定是多项式时间可验证的，不能确定是 NP 的，所以 不能说是 NPC 的。这个问题能够正确回答，则 hamilton 回路问题也 能正确回答。Tsp 优化问题：实例：城市集合C = q,.,C ,城市之间距离d(C.,C.),1mi j询问：求城市排列： C* ，C* , , C* 使兀 1兀2nm迟d(C*,c*)=min Yd(C ,c)IC 1C 2C 为城市排列兀i 兀i+1兀i 兀i+1 兀1 兀2兀mi=1i
