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

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

《算法分析与设计第10讲Word格式.docx》由会员分享，可在线阅读，更多相关《算法分析与设计第10讲Word格式.docx（11页珍藏版）》请在冰点文库上搜索。

看问题：

问题怎样在计算机存储?

首先明确输入长度为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：

若判定问题不是数问题，PNP，则该问题不能被拟多项式算法解答。

解释什么问题不是数问题。

证明：

设不是数问题，T=q（Length（I）,Max（I））q（length（I）,p（length（I）））=q1（length（I））。

若存在解答的拟多项式算法，则有多项式算法解答，则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，则一定不能被拟多项式算法解答。

强NPC问题不能有拟多项式算法，否则NPC问题就可以多项式解答了。

受限子问题是NPC的，能被多项式时间算法解答，则任意NP问题都能被多项式时间算法解答。

§

6.2证明强NPC与拟多项式变换

先证明货郎问题是强NPC的。

限制货郎问题的边长不是很大，也是NPC。

结论：

限制边长为1或2的TSP问题是NPC的。

HCTSP

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）存在正整数BZ+，满足：

B/4<

S（ai）<

B/2，

（4）

询问：

是否存在A的划分：

A=S1S2…Sm，即将A划分为m个子集，使

=B。

简单解释：

***三划分不是划分为三份。

（1）划分的每个子集中肯定是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），Length’[f（I）]，Max’[f（I）]。

（4）存在一个变换f：

D1D2，满足：

（a）对任意实例ID1，计算f（I）的时间复杂度是Length（I）和Max（I）的多项式函数。

T（f（I））=P（Max（I）,Length（I））。

（b）对ID1，IY1当且仅当f（I）Y2

（c）存在多项式函数p1（）使对ID1有

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）需要这个条件

●（d）要求Max’（*）不能增大到超过Max（*）和Length（*）的界定范围。

拟多项式变换P

引理6.1：

是强NPC，’是NP问题，存在一个到’的拟多项式变换，则判定问题’也是强NPC的。

将和’中的最大数值都限定受输入长度的多项式限制，

则受P限制的是NPC问题，

存在的拟多项式变换就是多项式变换P’q，

所以受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），每个任务都能按时完成。

任意ti,tj，ij，|（ti）-（tj）|max{L（ti）,L（tj）}

定理6.3：

区间排工是强NPC。

三划分P区间排工。

三划分的实例：

A={a1,a2,a3,…,a3m}，S（ai）Z+，BZ+。

由此构造区间排工实例：

T=A{t1,t2,…,tm-1}

L（ai）=S（ai），i=1,…,3m

L（t1）=L（t2）=…=L（tm）=1

+

=mB+m-1

r（ai）=0，i=1,…,3m

d（ai）=mB+m-1

r（ti）=iB+i-1，i=1,…,m-1；

d（ti）=iB+i,i=1,…,m-1

=mB+m-1，所以从0开始，总用时间是mB+m-1

（1）变换可以在三划分实例输入长度的多项式时间内完成。

（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。

首先判定两个图是否完全同构也是多项式时间可解的。

子林同构问题根本就没有数值参量，所谓强NPC与NPC等价的。

这个例子的意义在于说明可以用证明强NPC的方法证明NPC。

定理6.4：

子林同构问题是强NPC。

三划分拟多项式变换到子林同构。

A={a1,a2,…,a3m}，S（ai）,BZ+

构造G和H如下：

B+1个点。

G

H构造为：

（1）

（2）aiS（ai）个点的线：

S（ai）个点的线。

首先说明若三划分回答yes，则显然可以将对应的H的线图接起来对到G上去。

另外若H中的线图接到星图上形成完全G的形状，则接到每一条线上去的线段的总长均为B，所以原来的三划分问题一定可以三划分。

（3）变换的时间复杂度与B有关，变换出来的树的点的个数与B有关。

主要说明：

●限制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），

求城市排列：

，

…,

使

=min{

|C1C2…Cm为城市排列}

这个问题也不是NP的，所以不是NPC的。

这个问题能够正确回答，货郎判定问题也能正确回答。

在问题中要找一个解的问题称为搜索问题。

多项式规约，本身就说明一件事，若2能多项式时间正确解答，则1也能多项式时间正确解答。

所以有turing规约的概念：

turing规约是用神喻图灵机定义的，那是为了严格，这里就不再讲神喻图灵机了。

讲一下直观的定义：

条件：

（1）1是一个搜索问题，2是一个搜索问题。

（2）可以设计一个求解1的算法，算法中调用求解2的算法A

（2）。

（3）若A

（2）的时间复杂度记为O

（1），则求解1的算法是多项式时间复杂度。

若有上述条件

（1）

（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,K

1调用算法A（G,d）求得最优解，设得到的最短旅游长度为OPT（G,d）.

2若OPT（G,d）K，则回答yes，否则回答no。