资源描述：
《算法分析与设计2007第a讲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第A讲上次内容：(1)先行约束排工，限制很强时是多项式可解的，没有限制是NP-Complete。(2)着色问题，限制顶点度不超过4的图3着色问题是NPC，限制平面图的3着色问题是NPC。(3)拟多项式变换与NPC类，划分问题的拟多项式算法。划分问题拟多项式时间算法。一个问题中有两个参数影响时间复杂度：划分问题。输入长度：Length(I)=
2、A
3、log2
4、A
5、+
6、A
7、log2()最大数值：问题的实例中碰到的最大数值。Max(I)=B=说明：可以设计算法与两个参数有关系。l一个问题的编码不是完全相同的，因此输入长度和最大数值会根据编码不同有所不同。一般来说，不
8、管用什么样的编码，输入长度是差不多的，多项式相关的。不同人编不同的程序。l有的问题根本不含有数值参量，这样MAX(I)=0。l划分问题算法时间复杂性：O(nB)定义6.1：拟多项式算法：判定问题p，存在解答算法，算法的时间复杂度为：T(I)=P(Length(I),Max(I))，I为任意实例，则该算法称为求解问题p的拟多项式算法。看问题：最好讲讲怎样问题怎样在计算机输入?首先明确输入长度为n，则最大数值可能是2n。(1)SAT，该问题中根本没有Max(I)这一项。没有最大数值，Max(I)=0(2)团问题，最大数值，J£
9、V
10、。自然受到限制。第12页第A讲
11、(3)TSP，该问题中边长或K是最大数值Max(I)项。(4)划分问题，元素重量是Max(I)项。O(nB)考虑(1)，Max(I)=0，这个问题是NPC的，可以认为，最大数值本身受到输入长度的限制。Max(I)£P(Length(I))考虑问题(2)团问题中的数值参量受到输入长度约束。J£
12、V
13、。Max(I)£P(Length(I))(3)TSP问题中，边长根本不受输入长度的约束，每条边长可能很大，问题3的元素重量也不受到输入长度约束。函数P不存在，使Max(I)£P(Length(I))。(4)划分问题中，元素价值不受输入长度的约束。函数P不存在，使Ma
14、x(I)£P(Length(I))。受约束的含义：存在多项式函数P(*)，使Max(I)£P(Length(I))。n位输入，则数值大小为2n，Max(I)=2Length(I)£P(Length(I))Max(I)=£P(Length(I))定义6.2：对于判定问题p，若不存在多项式函数P，使对所有实例I有：Max(I)£P(Length(I))，则称p为数问题。最大数值不受约束。就是最大数值可能很大的问题是数问题。不受输入长度约束。命题6.1：若判定问题是NPC类，不是数问题，P¹NP，则该问题不能被拟多项式算法解答。解释什么问题不是数问题。证明：T=q
15、(Length(I),Max(I))£q(length(I),p(length(I)))=q1(length(I))第12页第A讲。若有拟多项式算法，则有多项式算法，则P=NP，矛盾。下面是几个问题p，多项式函数P，D(p)表示该问题的所有实例组成的集合。定义一个新的实例集合：D(pP)={I
16、IÎD(p),Max(I)£P(Length(I))}，由D(pP)中实例表达的问题就是多项式可解的吗。注意多项式函数给定。再次强调问题是实例的集合！定义6.3：判定问题p，存在多项式函数P，使pP是NPC的，则称p是强NPC的。命题6.2：若问题p是强NPC的，P¹
17、NP，则一定不能被拟多项式算法解答。强NPC问题不能有拟多项式算法，否则NPC问题就可以多项式解答了。受限子问题是NPC的，能被多项式时间算法解答，则任意NP问题都能被多项式时间算法解答。§6.2证明强NPC与拟多项式变换先证明货郎问题是强NPC的。限制货郎问题的边长不是很大，也是NPC。HCµTSPHC实例为：第12页第A讲®将该实例变为货郎问题实例如下：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回路，则相应
18、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划分问题实例：讲清楚，但不证明。第12页第A讲(1)集合A，含有3m个元素，A={
19、a1,a2,…,a3m}，(2)S(ai)ÎZ+，(
