算法分析与设计第10讲Word格式.docx

1、看问题：问题怎样在计算机存储?首先明确输入长度为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的元素重量也不受到输入长度约束。受约束的含义：存在

2、多项式函数P（），使Max（I）P（Length（I）。将Max（I）不受Length（I）约束的问题单独分为一类，给个名份。定义6.2：对于判定问题，若不存在多项式函数P（），使对所有实例I有：Max（I）P（Length（I），则称为数问题。最大数值不受约束。就是最大数值可能很大的问题是数问题。不受输入长度约束。命题6.1：若判定问题不是数问题，PNP，则该问题不能被拟多项式算法解答。解释什么问题不是数问题。证明：设不是数问题，T= q（Length（I）, Max（I）q（length（I）, p（length（I） =q1（length（I）。若存在解答的拟多项式算法，则有多项式算法解

3、答，则P=NP，矛盾。问题，多项式函数P（），D（）表示该问题的所有实例组成的集合。对于多项式函数P（），定义一个新的实例集合：D（P） = I|ID, 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的，PNP，则一定不能被拟多项式算法解答。强NP

4、C问题不能有拟多项式算法，否则NPC问题就可以多项式解答了。受限子问题是NPC的，能被多项式时间算法解答，则任意NP问题都能被多项式时间算法解答。6.2证明强NPC与拟多项式变换先证明货郎问题是强NPC的。限制货郎问题的边长不是很大，也是NPC。结论：限制边长为1或2的TSP问题是NPC的。HCTSPHC实例为： 将该实例变为货郎问题实例如下：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实例存在不

5、超过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）存在正整数BZ+，满足：B/4S（ai）B/2，（4） 询问：是否存在A的划分：A=S1S2Sm，即将A划分为m个子集，使=B。简单解释：*三划分不是划分为三份。（1）划分的每个

6、子集中肯定是3个元素。因为：B/2。（2）每个集合中3个元素，就是3划分的含义。有很多东西，我们不讲了，4划分是强NPC，3划分也是强NPC。不要看书上有很复杂的符号，很多内容，看懂也应该比较简单。下面先定义什么是拟多项式变换：定义6.4：（1）判定问题1和2，实例集合分别为：D1，D2，（2）回答yes的实例集合为：Y1和Y2（3）两个问题的实例编码后分别有：Length（I），Max（I），Lengthf（I），Maxf（I）。（4）存在一个变换f：D1D2，满足：（a）对任意实例ID1，计算f（I）的时间复杂度是Length（I）和Max（I）的多项式函数。T（f（I）=P（Max（I）

7、,Length（I）。（b）对ID1，IY1当且仅当f（I）Y2（c）存在多项式函数p1（）使对ID1有LengthIp1（Lengthf（I），这个限制很有用，I的长度不能很大。仔细研究研究的话，估计这个条件可以去掉。一般越变越长，不会变短。推导的一步需要这个条件。Lengthf（I）p2（LengthI, MaxI），这个由前面就能得到。（d）存在两个变量的多项式函数q1,使Maxf（I）q1（MaxI,LengthI）则f称为1到2的拟多项式变换。变换与数值和长度都有关。如果数值参量受到输入长度限制，就是多项式时间变换。 条件（a）（b）是拟多项式变换的基本要求，变换计算时间复杂度要求更

8、宽一些。 （c）需要这个条件 （d）要求Max（*）不能增大到超过Max（*）和Length（*）的界定范围。拟多项式变换P引理6.1：是强NPC，是NP问题，存在一个到的拟多项式变换，则判定问题也是强NPC的。将和中的最大数值都限定受输入长度的多项式限制，则受P限制的是NPC问题，存在的拟多项式变换就是多项式变换Pq，所以受q（）限制的q是NPC的，所以不受限制的是强NPC的。区间排工问题：有限任务集合，T=t1,t2,tn，只有一台机器。r（tk）：最早起始时间d（tk）：最晚结束时间L（tk）：加工长度是否存在排工表：（tk），k=1,2,n，使d（tk）-L（tk）（tk）r（tk），

9、每个任务都能按时完成。任意ti, tj，ij，|（ti）-（tj）|maxL（ti）,L（tj）定理6.3：区间排工是强NPC。三划分P区间排工。三划分的实例：A=a1,a2,a3,a3m，S（ai）Z+，BZ+。由此构造区间排工实例：T=At1, t2, , tm-1L（ai）=S（ai），i=1,3mL（t1） = L（t2） = = L（tm） = 1+=mB+m-1r（ai）=0，i=1,3md（ai）=mB+m-1r（ti）=iB+i-1，i=1, , m-1；d（ti） = iB+i, i = 1, , m-1=mB+m-1，所以从0开始，总用时间是mB+m-1（1）变换可以在三划

10、分实例输入长度的多项式时间内完成。（2）若三划分实例回答yes，则变换后的区间排工实例也回答yes，若区间排工实例回答yes，则相应三划分实例一定有一个三划分。（3）条件（c）几乎总是满足。（4）最大数值变化不大。符合条件（d）。三划分中的最大数值为B,区间排工的最大数值为：mB+m-1，当然是B的多项式函数。所以区间排工是强NPC。就是说区间排工中的数值r（）,d（）,L（）都不必很大，问题就很难解。子林同构图G和H，G为树，H为林。图G是否包含一个子图与H同构。限制G和H都是树，则该问题是多项式时间可解的。限制G为树，H为林，则该问题是强NPC。首先判定两个图是否完全同构也是多项式时间可解

11、的。子林同构问题根本就没有数值参量，所谓强NPC与NPC等价的。这个例子的意义在于说明可以用证明强NPC的方法证明NPC。定理6.4：子林同构问题是强NPC。三划分拟多项式变换到子林同构。A=a1,a2,a3m，S（ai）, BZ+构造G和H如下：B+1个点。GH构造为：（1） （2）aiS（ai）个点的线： S（ai）个点的线。首先说明若三划分回答yes，则显然可以将对应的H的线图接起来对到G上去。另外若H中的线图接到星图上形成完全G的形状，则接到每一条线上去的线段的总长均为B，所以原来的三划分问题一定可以三划分。（3）变换的时间复杂度与B有关，变换出来的树的点的个数与B有关。主要说明： 限

12、制B不大时，即为输入长度的多项式函数时，三划分问题是NPC的， 变换本身是输入长度和最大数值的多项式函数，所以是多项式变换 所以子林同构是NPC的。 子林同构中根本没有数值参量，当然是强NPC的。6.3：复杂性类之间的关系很多问题不是NP的，所以不是NPC的，但是比NPC问题更难，这样的问题怎样说明难度。Hamilton问题补问题：无向简单图G=（V,E）图G没有hamilton回路吗？这个问题不能确定是多项式时间可验证的，不能确定是NP的，所以不能说是NPC的。这个问题能够正确回答，则hamilton回路问题也能正确回答。Tsp优化问题：城市集合C = C1,Cm，城市之间距离d（Ci,Cj

13、），求城市排列：，, ,使=min|C1C2Cm为城市排列这个问题也不是NP的，所以不是NPC的。这个问题能够正确回答，货郎判定问题也能正确回答。在问题中要找一个解的问题称为搜索问题。多项式规约，本身就说明一件事，若2能多项式时间正确解答，则1也能多项式时间正确解答。所以有turing规约的概念：turing规约是用神喻图灵机定义的，那是为了严格，这里就不再讲神喻图灵机了。讲一下直观的定义：条件：（1）1是一个搜索问题，2是一个搜索问题。（2）可以设计一个求解1的算法，算法中调用求解2的算法A（2）。（3）若A（2）的时间复杂度记为O（1），则求解1的算法是多项式时间复杂度。若有上述条件（1）

14、（2）（3），则称1图灵规约到2。首先多项式变换也是图灵规约！图灵归约不局限于NP问题之间，任意搜索问题都行。解释：（1）什么是搜索问题，搜索最优解的问题。（2）上述说法不严格，但是道理是这样的。举例，*若1是NPC问题，1可以图灵规约到2，则称2是NP-hard问题。这个定义说明所有NPC问题都是NP-Hard问题。还有一些问题不是NPC的，仍然是NP-Hard问题。*若1是NP-Hard问题，1可以图灵规约到2，则称2是NP-hard问题。举个例子：假设有一个货郎优化问题的算法为A设计货郎判定问题求解算法如下：假设货郎判定问题的实例为G,d,K1调用算法A（G,d）求得最优解，设得到的最短旅游长度为OPT（G,d）.2若OPT（G,d）K，则回答yes，否则回答no。