(算法分析与设计2009第a讲.docVIP

上次内容： (1)先行约束排工，限制很强时是多项式可解的，没有限制是NP-Complete。 (2)着色问题，限制顶点度不超过4的图3着色问题是NPC，限制平面图的3着色问题是NPC。 (3)拟多项式变换与NPC类，划分问题的拟多项式算法。 划分问题拟多项式时间算法。 一个问题实例中有两个因素影响算法时间复杂度：划分问题。 输入长度： Length(I)=|A|log2|A|+|A|log2() 最大数值：问题的实例中碰到的最大数值。 Max(I)=B= 算法时间复杂性：O(nB)=P(Length(I),Max(I)) 说明：可以设计算法与两个参数有关系。 一个问题的编码不是完全相同的，因此输入长度和最大数值会根据编码不同有所不同。不同人编不同的程序。 有的问题根本不含有数值参量，这样MAX(I)=0。 定义6.1：拟多项式算法：判定问题?，存在解答算法A，算法A的时间复杂度为：T=P(Length(I), Max(I))，I为任意实例，则称算法A为求解问题?的拟多项式算法。 看问题：问题怎样在计算机存储?首先明确输入长度为n，则最大数值可能是2n。 (1)SAT，该问题中根本没有MAX(I)这一项。没有最大数值，Max(I)=0 (2)TSP，该问题中边长或K是最大数值MAX(I)项。 (3)划分问题，元素重量或B是Max(I)项。O(nB) (4)团问题，最大数值，J?|V|。自然受到限制。 考虑(1)，Max(I)=0，这个问题是NPC的，可以认为，最大数值本身受到输入长度的限制。Max(I)?P(Length(I))，P(?)是多项式函数。 考虑问题(2)(3)，TSP问题中，边长根本不受输入长度的约束，每条边长可能很大，问题3的元素重量也不受到输入长度约束。 受约束的含义：存在多项式函数P(?)，使Max(I)?P(Length(I))。 将Max(I)不受Length(I)约束的问题单独分为一类，给个名份。 定义6.2：对于判定问题?，若不存在多项式函数P()，使对所有实例I有：Max(I)?P(Length(I))，则称?为数问题。最大数值不受约束。 就是最大数值可能很大的问题是数问题。不受输入长度约束。 命题6.1：若判定问题不是数问题，P?NP，则该问题不能被拟多项式算法解答。解释什么问题不是数问题。 证明：设?不是数问题，T= q(Length(I), Max(I))?q(length(I), p(length(I))) =q1(length(I))。若存在解答?的拟多项式算法，则有多项式算法解答?，则P=NP，矛盾。 问题?，多项式函数P()，D(?)表示该问题的所有实例组成的集合。对于多项式函数P(?)，定义一个新的实例集合：D(?P) = {I|I?D?, Max(I)?P(Length(I))}，由D(?P)中实例表达的问题就是多项式可解的吗。注意多项式函数给定。 例如划分问题中，每个元素长度S(a)?n2，n是元素个数。P(n)=n2，则?P是多项式可解得。 再次强调问题是实例的集合！ 定义6.3：判定问题?，存在多项式函数P，使?P是NPC的，则称?是强NPC的。 (1)非数NPC问题一定是强NPC问题 (2)主要讨论数问题是否为强NPC问题 命题6.2：若问题?是强NPC的，P?NP，则?一定不能被拟多项式算法解答。 强NPC问题不能有拟多项式算法，否则NPC问题就可以多项式解答了。 受限子问题是NPC的，能被多项式时间算法解答，则任意NP问题都能被多项式时间算法解答。 §6.2证明强NPC与拟多项式变换 先证明货郎问题是强NPC的。限制货郎问题的边长不是很大，也是NPC。 结论：限制边长为1或2的TSP问题是NPC的。 HC?TSP 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)=2。满足下式否？ Max(I)?Length(I)，满足这种限制的TSP仍然是NPC的。所以TSP问题是强NPC的。 对于一个NPC问题，如果你能说明其受限子问题是NPC的，则就说明这个问题是强NPC的。 先讲一个问题，3划分问题 实例：讲清楚，但不证明。 (1)集合A，含有3m个元素，A={a1,a2,…,a3m}， (2)S(ai)?Z+， (3)存在正整数B?Z+，满足：B/4S(ai)B/2， (4) 询问：是否存在A的划分：A=S1?S2