一共考5道题，每道题2问 一、（★重要）设L为n元数组，其中的数已按增序排列，另给定数值x，试采用二分搜索技术设计算法，查找数值是否在L中。要求若x在L中，则输出j，使L(j)=x；其x不在L中，则输出0。并证明，在最坏情况下，对所有n元数组L(n≥1)，二分搜索算法将数值x与L中元素比较次数为。 logn 1 2解： 1、l 1,r n2、if(l r)j 0转6l r 3、j 2 4、if(x l(j))转65、if(x l(j))则l j 1，否则r j 1，转26、输出j，结束 比较次数：由于是2分搜索，每次比较或者成功，或者将搜索范围缩小一半。n 1因此最多比较次数为2的对数，又当时，至少比较1次，所以比较次数不超logn 1 过。 2二、满足三角不等式的TSP问题是否是NPC？为什么？ HC TSP解：证明思路，将哈密顿回路HC问题多项式变换到TSP问题:，且HC NPC变换到TSP问题的实例是满足三角不等式的。因为，故满足三角不等式的。 TSP NPCHC TSP多项式变换： V}G V,E,V {VV......设HC的实例为，据此构造TS实例m1,2, G V,E,V V,(G必为完全)图，两个顶点之间的距离定义为1 i,j E d i,j 2 i,j EB m ，并设TSP旅游界值为。 易知这个变换是多项式的。 1 / 29

GB m若HC存在一条哈密顿回路，则这条回路在上的长度必为B，而是最短旅游的界值，故这条回路是满足实例的一个TSP旅游。 G若存在一个满足B的TSP旅游，则该旅游必经过长度为1的边，而这些边均在G上，因此这个TSP旅游在G上是一条HC回路。 HC TSPHC NPC这样就将，而。 变换到的TSP实例的边长为1或2，可知该实例满足三角不等式，这就证明了满足三角不等式的TSP问题是NPC问题。 三、给定城市集合，任两城市距离，求最C {C......C}d(i,j),d(i,j) d(i,k) d(k,j)1n小货郎旅游。试证明满足三角不等式的货郎优化问题为NP-hard。（★重要）求满足三角不等式的TSP的近似算法，并设计出能解答该问题的多项式时间近似3算法A，其近似性能比为。 R A2证明：即满足三角不等式的TSP问题。 HC TSP证明思路，将哈密顿回路HC问题多项式变换到TSP问题:且变换到HC NPCTSP问题的实例是满足三角不等式的（见第1题）。因为，故满足三角不等式的TSP问题是NPC问题。 A设存在TSP优化问题求解算法，设计TSP判定问题的算法如下： G,d,kA(G,d)对于给定TSP判定问题的实例：，调用，求得城市排列：m **d(C,C) k ***C,C......Cii 1，若，则回答yes，否则回答no。 21mi 1A若为多项式算法，则上述算法能够在多项式时间内解答，故TSP判定问题可以图灵归约到TSP优化问题，而已知TSP判定问题是NPC的，所以TSP优化问题是NPH的。 A算法： 2 / 29

G①对调用最小支撑树（有权图权值之和最小的连通子图）算法，得到树T(V,E) TV}{VV......VV......GT，在中求点集②设的奇数顶点为的最小对集2t1,2,2t1EE {e,e......e} ETT，将加入中，形成欧拉图 pp12t1VVVV......T③在中求欧拉回路 (2m 2),(1)(1),(2),1TSP:V V...VV④抄近路得到 (1)(1)(m)(1)3R A2证明： 因为TSP是回路，最小生成树是树， d(T) OPT(I)所以 d(v,v) d(v,v)又对于所有最小对集的两条边，小于这四点相连的最小ii 1i 2i 31 2TSP旅游距离， 133d(T) d(T) OPT(I) OPT(I)MM(I) d(T) OPT(I) 11222所以， 四、对于背包问题 n maxPX ii X {0,1}1 i nPW Zi 1 ii,in WX mii i 1证明： (1)、当时，该问题不存在多项式时间绝对近似算法 P NP(2)、背包问题存在绝对近似性能比的多项式时间近似算法 R 2a证明: (1)假设存在A,则存在常数 （2）：实例为价值，为重量，为背包容量 P {P...P}W {W...W}m Z1n1n 3 / 29

n maxPX ii 询问：求向量，使。 x0,1i 1 n WX mii i 1PPPP算法：①将物体按照排序，使 n12 ...... WWWW12n②从1到n将物体装包，直到不能装为止，记其总价值和为 GA(I)③取 A(I) max{GA(I),maxP(w B)}ii1 i n复杂性：步骤①，步骤②，故总的时间复杂性为 O(nlogn)O(nlogn)O(n)近似性能比：设包含物体价值为，则 P...PGA(I)1r ， P P ... P P OPT(I)12rr 1r 而， A(I) P,A(I) Pimaxi 1r 故， 2A(I) P P OPT(I)imaxi 1OPT(I) 即 2,R 2 AA(I)n 五、n个整数，正整数m。求向量。 aa......axxx a1,2,ni1,2,ni 1i 1 证明是NPC的；若，求多项式时间算法，证明其正确性。 a aijj 1六、给定WPAR问题 实例：集合，对于每个有长度。 *r RR {r,r,......r}S(r) Z,1 i ni12ni1 询问：是否存在子集 R R,使S(r) S(r)? ii2r R'r R R'ii(1)、试利用划分PAR是NPC问题，证明WPAR问题属于NPC类； (2)、试设计拟多项式算法： (a)判断是否存在，(b)若存在，应给出一个满足询问条件的。 RR 4 / 29

(3)、针对如下实例，说明你设计算法的执行过程 R {r,r,r,r,r} 12345S(r) {1,5,7,8,9}i解：(1)、证明WPAR是NPC 证明：(将)设PAR实例为， PAR WPARA:aa......a,B S(a)2,ni1,73构造WPAR实例：，其中 b B,b BR:{aa......abb} 121,2,n,1,222B 若PAR中存在一个划分，使得，则在WPAR中，S(a) i2AB7B3 ，而。 S(a) b B 4BS(a) b B 2B i1i22222 AA A1 因此，必存在使 R RS(r)S(r) ii2 R RR1 ，则。 若WPAR中存在使 R RS(r)S(r) S(r) 2B iii2 R RRR分析元素构成，中必含不含，而中必含，不含。则有 bbbbRR R2112BB ，即A中存在一个划分。 S(r) b ,S(r) b i2i122 RR R又上述变换可在多项式时间内进行，因此，又，因此PAR WPARPAR NPC WPAR NPC（2）、设计WPAR拟多项式算法 解：设，若B不能被3整除则无划分；若B能被3整除，则设计表tB S(r)iB为n行，列。 1 3jT,前i个元素中有元素和为 ， t[i,j] F，其它情况 B若，则最终回答yes，否则no t[n,] T 3① ② t[i,0] Tt(1,j) T③若则 t[i 1,j] T,t[i,j] T 5 / 29

④若，则 t[i 1,j S(r)] Tt[i,j] Ti⑤ t[i, 1] F⑥ t[0,j] FB求解算法：记 为b,记n a 31、if(a 0或b 0)，则返回A为所求elseif(t[a 1,b] T){ 2、a ,go1}else 3、将a加入集合b b Sa;a ,go1i（3）、用设计算法求解实例 R {1,5,7,8,9},B 30 0 1 2 3 4 5 6 7 8 9 10 j：i 1 T T 2 T T T T 3 T T T T T T 4 T T T T T T T 5 T T T T T T T T 七、（★重要）给定2SAT问题实例，布尔变量集合，项集合U {uu......u}1,2,n，为U上布尔变量字母。 C {CC......C}Ci {x,y} {uu......u} {u,??},1 i n,xy1,2,nii1,2,nii,i试设计多项式时间算法：(1)、判定2SAT实例是否有可满足真值指派；(2)、若有可满足真值指派则算法给出使C满足U的真值指派。 八、证明团问题属于NPC 思路：已知顶点覆盖，而最大独立集问题，故最大独立集问题VC NPCVC NPC（若是上的点覆盖，则是上的最大独立集。若是上的最大独立 VGGVGV V 6 / 29

(若是上集，则是上的点覆盖）。又最大独立集问题，故 VGGV V CLPCCL N的最大独立集，则在的补图上所对应的子图是上的团) oo GGVG点覆盖：上的最小顶点集合，覆盖上所有的边； GVVG独立集：上的点集合，中任两点之间无边； GVV补图：（？？？） o G V,E ,V V,团：上最大完全子图 G九、TSP判定问题是数问题吗？是否存在拟多项式算法？为什么？ 答：TSP判定问题是数问题，因为任两城市间的距离及界值没有任何d i,j B约束。因为可以将，从而证明，而有限制， TSP1 d i,j 2HC TSPTSP NPC事实上,故不受限制的原始TSP问题是强NPC。因此TSP问题不存d i,j 1或2在拟多项式时间算法。 十、集合覆盖问题T 实例：为子集族 S {ss......s},C {cc......c},C1,2,n1,2,n询问：求，使最小 C CC S且CiC Ci求证：时，上述问题无多项式时间绝对近似算法 P NP证明：若限制,则集合覆盖问题变为X3C问题。而， X3C NPCS 3q,C 3,C Cii故集合覆盖问题是NPC问题。 (反证法)设存在多项式时间绝对算法A，有 A(I) OPT(I) k现将复制份到，易知，在上应用算法A有 OPT(I) (k 1)OPT(I)IIIK 1 A(I)k ，故： A(I) OPT(I) k,A(I) (k 1)OPT(I) k, OPT(I) 1 k 1k 1 A(I) (之所以取整，是因为集合覆盖问题是求最小值问题） OPT(I) k 1 因此可以构造算法：（1）、；（2）、对调用A，得子集族的子集及； I IA(I)IA 7 / 29

A(I) （3）、计算即为实例的最优解值 OPT(I)I k 1 因为是多项式的，所以也是多项式的，这就多项式时间回答了集合覆盖问题。 AA而我们已知集合覆盖问题是NPC，这与矛盾，故假设不成立。即不存在P NP多项式时间绝对近似算法。 十一、假设一台处理机可连续加工任务。但在每个时刻，只允许加工一个任务，含有待加工任务集合其中所有任务都有相同的加工最早起始。T {TT...T}1,2,n时间，但它们所需要的加工时间和加工最迟完成时间不同，即t t ...... t 012n对于一个任务，其所需加工时间为，加工最迟完成时间为LT Tii且，试设计一个多项式时间算法，给出任d(1 i n)L L,d d,(i j)iijij务集合的排工表，使能按要求完成的任务数达到最大。 要求证明你所设计算法的正确性，并分析其时间复杂性，并通过下述实例说明算法的运行情况： T {T，TTTTT}1,2,3,4,5,6 L 6,L 4,L 3,L 5,L 7,L 2;123456 d 8,d 9,d 10,d 11,d 16,d 17;123456（★重要）算法，将所有任务按其结束时间由小到大排列，若满足时，d1 i ni有。令空，S为排工表。 d dS ij① S S {T},k 1,m 11②若，转④ k n ③设对个任务，已经安排了个任务加工。。则对第个任k 1mL(s) L(T)kiT Si务，只要有,则将其安排为第个任务：即L(s) L dm 1k 1k 1，然后转② S S{T},m m 1,k k 1 k 1 8 / 29

若,则从已安排的个任务中，另择一个加工时间最长的任务L(s) L dmk 1k 1，若，则将从中移出，将后的任务前移，再把并入，TTTTL LSSiiik 1ik 1，转② L(s) L(s) L L,k k 1k 1i否则（），k=k+1, 转② LL ik 1④完成，S即排工表。 正确性：由于的排序是一定的，只需证明每一步操作都使加工时间最短，则di它的加工任务最多。 归纳法证明： （1）当时，显然成立； n 1（2）假设 时正确，即若个中拔下个，且加工时间最短，下面kn k(k 1)m证明时也正确。 n k 1当时，若，则安排第个任务，显然个任务最多L(s) L dk 1k 1n k 1k 1k 1能安排个，且时间最短； m 1若，则由于算法中选择了中最长的任务，且当时用TL LL(s) L dSiik 1k 1k 1代替，使总加工时间，故仍满足加工时间最短，任务最多。 TTL(s) L L L(s)ik 1k 1i综上所述，把个任务排完时，算法是正确的。 n复杂性：设有个任务，则最坏情况下对每个加工任务都有，从而L(s) L dnk 1k 1从中查找最长加工时间任务，则一次查找为，每个任务都查找为，2O(n)SO(n)排序加工任务为，因此总的复杂度为。 2O(n)O(nlogn)算法的实例运行情况： d 8,d 9,d 10,d 11,d 16,d 17;123456 L 6,L 4,L 3,L 5,L 7,L 2;123456 S={t1} k=1 m=1 Ls=6 9 / 29

S={t2} Ls+L2=10>d2 Ti=T1, Li>L2,Ti out, T2 in k=2, Ls=4 S={t2t3}ls+L3=6<10, k=3,m=2,Ls=6 S={t2t3t4}Ls+L4=11=d4,k=4,m=3,Ls=11 m=3 S={t2t3t4}Ls+L5=18>d5,Ti=T4,Li十二、排工问题（区间排工） 实例：只有一台机器，n个任务，。对于每任务有加工起始时T {TT...T}1,2,n间，终止时间，加工长度 rdliit询问：加工表，表示的真正开始。 (t)(t),(t),......(t)kn12n (t) r(t) 使按时完成。时，，在之前开始，或 kk(t) (t) l(t)tti j ijjij (t) l(t) d(t) kkk，在之前开始。（两个任务不同时开始进行） (t) l(t) (t)ttijjij试证：(1)、问题 NPC（2）、若限制，称为限制排工问题，试设计一多项式算法，限制r r ......r r12n0排工任务数目最大，再证明算法的正确性，分析其复杂性。 解：（1）见教材，试图将区间排工。 PAR n 设实例，对每一个有均为整数，。根据问aS(a)A {a,a......a}B S(a)PARPARiii12ni 1题实例构造排工问题实例： T {tt...t,E},r(t) r(t) ...... r(t) 01,2,n12nBB 1 ， d(t) d(t) ... d(t) B 1,L(t) S(a),r(E) ,d(E) 12nii22 10 / 29

我们不考虑B为奇数的情况，因为B为奇数时，PAR不存在一个划分。 若存在一个划分，则可如此排工：将中所对应的任务安排在E atPARAAii之前完成，将所对应的任务安排在E之后完成。由此排工问题存在一个排 A A工。 若排工问题存在一个排工，则可如此进行划分：将位于E之前的任务对应ti的置入集合，E之后的任务所对应的放在中。由于E之前的任务加 aaA AAiiBB （B为偶数），E之后的任务加工长度为工长度为 22 BBBB 1 ，而，故，即存L(t) ?(a)S(a) S(a) B 1 B 1 ( 1) PAR iiii2222 a Aa A Aii在一个划分。 因此，我们得区间排工，由于，故区间排工。 NPCPAR NPCPAR (2)、算法，将所有任务按其结束时间由小到大排列，若满足时，d1 i ni有。令空，S为排工表。 d dS ij① S S {T},k 1,m 11②若，转④ k n ③设对个任务，已经安排了个任务加工。。则对第个任k 1mL(s) L(T)kiT Si务，只要有,则将其安排为第个任务：即L(s) L dm 1k 1k 1，然后转② S S{T},m m 1,k k 1 k 1若,则从已安排的个任务中，另择一个加工时间最长的任务L(s) L dmk 1k 1，若，则将从中移出，将后的任务前移，再把并入，TTTTL LSSiiik 1ik 1，转② L(s) L(s) L L,k k 1k 1i否则，k=k+1, 转② ④完成，S即排工表。 11 / 29

正确性：由于的排序是一定的，只需证明每一步操作都使加工时间最短，则di它的加工任务最多。 归纳法证明： （3）当时，显然成立； n 1（4）假设 时正确，即若个中拔下个，且加工时间最短，下面kn k(k 1)m证明时也正确。 n k 1当时，若，则安排第个任务，显然个任务最多L(s) L dk 1k 1n k 1k 1k 1能安排个，且时间最短； m 1若，则由于算法中选择了中最长的任务，且当时用TL LL(s) L dSiik 1k 1k 1代替，使总加工时间，故仍满足加工时间最短，任务最多。 TTL(s) L L L(s)ik 1k 1i综上所述，把个任务排完时，算法是正确的。 n复杂性：设有个任务，则最坏情况下对每个加工任务都有，从而L(s) L dnk 1k 1从中查找最长加工时间任务，则一次查找为，每个任务都查找为，2O(n)SO(n)排序加工任务为，因此总的复杂度为。 2O(n)O(nlogn)i 1 十三、给定个整数，满足（超递增序列），有一正整数，试aa......ansa a1,2,nijj 1n 设计算法，找出一维0，1向量，使得或无解。 {x......x}s axnA1niii 1解：算法 A 12 / 29

s sfori ndownto1do ifs atheni x 1;s s a;iielsex 0;iendifendfor ifs 0then向量X {x......x}为答案1n else回答noendifi 1i 1x 证明：因为，所以若，必有，故应为1，否则使全 a sx xa aa sii1i 1ijjj 1j 1为1也没有正确答案。 复杂度：易知为。 O(n)十四、（1）平面图的最大团问题有多项式时间算法吗？Why? 答：有，因为当在平面图上考虑团问题时，任何平面图都不会含有多于4个顶点的完全图，故只需检查所有的顶点个数，不超过4个子图就能找到极大团。因4是常数，故子图数目是多项式有界的。所以必有多项式算法。 (2)平面图的3着色问题有多项式算法吗？Why? 答：没有，因为我们可以设计一个转线轨道图，用局部替换技术将一般图中的交点处理，将其转化为平面图。一般图的3着色问题，故平面图3着色也 NPC是NPC的，所以不存在多项式时间算法。 十五、（★重要）当时，TSP优化问题是否存在的多项式算法？ R P NPA答：不存在，用反证法证明。 证明：设存在常数，使，即存在算法，对TSP的任意实例有 R kkGAA。设是哈密顿问题任意实例，由构造TSP问题实例GA(G) k*OPT(G)G (V,E)HH如下。 GTSP 13 / 29

V(G) V(G) VTSPH1,(u,v) E(G) Hd(u,v) kv,(u,v) E(G) H若存在哈密顿回路，则 OPT(G) V,A(G) k*OPT(G) kvGHTSPTSPTSP若不存在哈密顿回路，则， OPT(G) VA(G) OPT(G) kvG HTSPTSPTSP因此可以设计哈密顿问题的TSP实例，调用算法由是否成立判 AA(G) kV定哈密顿是否存在解，又是多项式时间的，即哈密顿可以多项式时间求解，这A与矛盾。故假设不成立，TSP不存在的多项式算法。 R HC NPCA十六、（★重要）划分问题的拟多项式时间算法，并求划分的具体方案 B S(a)i解：设，若B为奇数，显然不能划分。若B为偶数，设一个布尔变量：a Aij的子集T如果{a...a}包括总价值为 1it(i,j) F其它情况 Bt(n,) T 2若,则回答yes，否则no t(i,j) T计算的条件： t(i 1,j) Tt(i,j) T①若，则 t(i 1,j S(a)) Tt(i,j) T②若，则 it(i,0) T③ t(i, 1) F④ 框图如右： B O(nB)logB2B时间复杂度：外循环n，内循环，故。因为的输入长度为，并不2logBO(nB) O(n2)2。是输入长度的多项式，故不是多项式算法，是拟多项式算法， 十七、已知MAXLA问题属于NPC类，MAXLA问题描述为 ，实例：简单图G=(VE)及正整数K。 14 / 29

： 询问：是否存在一一对应映射PV→{1,2,...,|V|}，使 |P(u) P(v)| K?(u,v) E试证明MINLA问题也属于NPC类，MINLA问题为 实例：与MAXLA相同。 ： 询问：是否存在一一对应映射PV→{1,2,...,|V|}，使 |P(u) P(v)| K?(u,v) EMAXLA MINLA证明：试图将 G(V,E)G(V,E)kMINLAMAXLA 设图及正整数为的实例，定义的实例为图，2n(n 1)n(n 1)(n 1) k k k V V,E {(u,v)|u v,(u,v) E}. GG66其中，，即为的补图。 iVP 对顶点集合中所有可能的映射，考虑：固定一点与其它所有点的 V P(i) V 1 P(i) ... 1 P(i) P(u) P(v){P(i) P(j)}i值，即对固定顶点，为 n 1n 1n 1(n 1)nn(n 1)(2n 1)1 22 P(u) P(v) i(n i) ni i n n(n 1) 266i 1i 1i 1u,v V 所以 u v GG又与互为补图 2n(n 1) P(u) P(v) P(u) P(v) P(u) P(v) 6所以 (u,v) E(u,v) E(u,v) E2n(n 1) |P(u) P(v)| K|P(u) P(v)| k k 6所以当且仅当 (u,v) E(u,v) EMAXLA MINLAMINLA NPC所以， 十八、用图灵归约技术证明个最大子集 NP HARDk个最大子集问题： k实例：个元素，，每个元素有一个长度。两个**A {aa......a},nS(a) ZS(a) Z1,2nii A非负整数和 k 2B S(a)a A询问：中是否有个不同的子集。满足且 A AkS(A) S(a) BA 15 / 29

S(A) B, a A A,其中S(A) S(a) a AA {aa......a},S[A,S,B,K]k证明：假设是解个最大子集问题的子程序，其中长度1,2n A S:A Z,B S(A),k 2 函数A {aa......a} S:A Z设集合和长度函数是划分问题的任意实例。 1,2nS(A)b S(A)S(A)2设计划分问题的算法。从计算开始，若是奇数，则回答NO。否则，S[A,S,B,K]并调用子程序 A算法： S(A)①若为奇数，则划分问题回答NO，结束。 S(A)b 2B②置，调用算法 S(A) b,S(A) S(a) b, a A A的子集A*LB算法：求满足的最大数目。 *L①，（可能的界限） nL 0,L 2minmax*L L 1L L②若，则并结束。 maxminminL (L L)2 S[A,S,b,L]S(A) b LA③；调用，检查是否有个子集满足 maxminL L若回答YES，则,转② minL L若回答NO，则,转② max 根据求出的满足的子集的最大数目，调用一次 ** LS[A,S,b 1,L]S(A) bA S(A) bS(A) b 1 A若回答YES，则表明所有满足的子集，也都满足，故相应划分问题回答No S(A) b若回答NO，则满足的子集一定存在，所以划分回答Yes。 16 / 29

十九、排工问题大全 1、区间排工 实例：有限任务集合最晚结束时间，,最早开始时间，l(t)d(t)r(t)T {tt......t}kkk1,2,n加工长度。 询问：是否存在排工表 (t)k 1,2......nk(1)区间排工，用划分区间排工 NPC(2)区间排工 强NPC 证明：将3划分区间排工 A {aaa......a},S(a) Z,B Z设三划分实例为 1,2,3,3mi由此构造区间排工实例： T A {t,......t}，L(t) 1,i [1...m 1],L(a) S(a),i 1...3m,r(t) iB i 11m 1iiiir(a) 0,d(t) iB i,d(a) mB m 1 iii若三划分问题回答yes，变换后的区间排工也回答yes。 若区间排工回答yes，则三划分问题也回答yes。且该变换是拟多项式变换。 强NPC 强NPC因为：三划分，所以：区间排工 2、最小迟序排工，有半序关系和最晚结束时间，不能按时完成的任务，证 k明，用证明。 CL NPC3、先行约束排工：为1，处理机为，半序关系 mL（1）没有半序或半序为树时是P问题 （2）时是P问题 m 1or2（3）半序和任意则是NPC m4、（★重要）多任务排工 实例：个处理机 mPPP......m1,2, 17 / 29

处理任务，加工时间， u(t)T {tt......t}i1,2,n任务之间有半序关系。 询问：最短时间内完成 NI(I,L)1 2 mOPT(I)（任意主次表，有空就加工）（1），非空闲算法 算法： ①开始所有处理都空闲，所有任务都未加工 t②对任务主次表从左向右扫描，判定每个任务是否处于加工状态。若可加j工，则安排至下标最小的空闲处理机上加工。 任务主次表是按半序关系的。 NI(I,L)1 2 mOPT(I) （2）证明将的时间区分成两部分： N(I,L)[0,N(I,L)]闲A每个区间所有机器非空 B { ... }显然k不相交B至少有一台机器空闲 1k则在半序关系中存在一条通路，该通路覆盖子区间 ... tt......t1ki1,i2,illk 所以： OPT(I) u(t) u( )ijjj 1j 1n1 OPT(I) u(t) ijmj 1knnk11m 1m 1 NI(I,L) (u(t) (m 1)u( )) u(t) u( ) OPT(I) OPT(I) jijimmmmj 1j 1i 1i 11即 NI(I,L) (2 )OPT(I) m1 注：当最大加工时间，限制时，变成PAR问题 m 2,D L(a) D i2a Ai5、（★重要）独立任务排工 18 / 29

实例：任务，加工长度 tt...tTT......T1,2,n1,2,nLPT(I)41（1）LPT算法，先排时间长的: OPT(I)33m①将任务排序，形成加工主次表 L {TT......T},t t... t1,2,n12n②对主次表从1到n扫描，若有空闲机器，则将任务安排空闲机器上加工，直至完成。 复杂度：，多项式算法 O(nlogn)LPT(I)41证： OPT(I)33mm 1①当时，显然成立。 ②当时，假设最后完成的任务为。若最后完成的任务是，则只考虑ttm 1nk前个任务，若前个满足，则个当然满足。 nkk内所有任务都非常空闲 在LPTI t[0,()] nn 11 LPT(I) t t nim i 1n1m 1 LPT(I) t t inmmi 1n1又 OPT(I) t imi 1tLPT(I)m 1 n 1 OPT(I)mOPT(I)若，则每个机器上最多安排2个任务，这样的排工是最优的，当OPT(I) 3tn然满足； LPT(I)41若，则 OPT(I) 3t nOPT(I)33m综上得证（再举例说明上界不能小于3） 19 / 29

1 F(I)1（2）F算法：多项式近似方案： m 1 OPT(I)1 k m①将任务从大到小时间排序： T {TT......T}1,2,n②确定正整数，对前个任务，求最优先排工，后个按先大后小顺kkn k序排工。 证明：①设T是前个任务的排工时间，若，则,设kF(I) TOPT(I) F(I)。 F(I) T②在区间所有的处理器非空闲，开始做时，其它有任务可能未t[0,F(I) t]k 1k 1做完。 n t m(F(I) t) tik 1k 1i 1n1m 1 OPT(I) t F(I) t ik 1mmi 1k 又，至少有一台机器加工了和前个任务的平均个数，即个任务；t1 k k 1m 又，是前个中最小的。 tk 1k 1k OPT(I) (1 )t k 1m 1 ttm 1m 1F(I)1 k 1k 1mmm 1 1 1 OPT(I)OPT(I)1 t1 kk k 1mm算法复杂度： kT(m,n) O(m nlogn)A 20 / 29

二十、装箱问题 实例：个物体集合，，每个物体，体积为，容量为na SW(a)S {aa......a}ii1,2nC的箱子。 询问：需要多少个箱子才能全部装完 FF(I)（1）首次适合算法Fit-First: 2 OPT(I)算法：按照一定顺序依次装入箱子。。 O(n)证明：任意两个相邻箱子装入物体体积大于，， BBB......Bc i 1i1knn 若为偶数，则；又， FF(I)2W(a) C FF(I)W(a) C OPT(I)iii 1i 1 FF(I) 2OPT(I)n 若为奇数，则， FF(I) FF(I) 2OPT(I) 12W(a) C (FF(I) 1)ii 1FF(I)又，为整数， 2FF(I),OPT(I) OPT(I)（2）FD算法，先大后小 11将物体排序，体积从大到小依次装箱， FD(I) OPT(I) 4 9二十一、背包问题 实例：有限集合为重量，为价值 W(u) ZU {uu...u},S(u) Zi1,2,ni 判定问题：是否存在 U U,S(u) B,V(u) kii u Uu UiiMaxPX ii 优化问题：，求向量。 n[x...x] XW M1n ii i 1(1)、判定问题 NPC1 限制为偶数，，则上述问题变为PAR问题。S(u)S(u) V(u),B k S(u) iiii2 u Uu Uii 21 / 29

。 PAR NPC, 背包 NPC(2)、背包问题无多项式时间绝对近似算法，将价值扩大倍，变成另一个问k 1题。反证法. (3)、的算法（见前文） R(I) 2AA*P1(4)、（★）多项式近似方案：，证明这个公式，给出时间复杂度 1 P1 kmax算法描述：对任意一种个元素的组合都先放入包中尝试，最后选择一个最k好的尝试。伪代码： Procedureapprox(P,W,M,n,k)//(价值、重量向量、重量限制、元素个数、k)P 0maxforallcombinationsIofsize kandweight Mdo P PIii IP max{P,P L(I,P,W,M,n)}//L()子程序maxmaxI下面endforend算法先装个再继续装： kProcedureL(I,P,W,M,n) s 0;T M W;ii Ifori 1tondoifi IandW Tthenis s P;T T W;iiendif endforreturn(max{s,max{P|i I,1 i n}}iend*P1证明：，为最优解，为算法的解 *PP 1 approx maxP1 kmax (1)设是最优解的背包元素下标集合，。 *P P,W MRiii Ri R若，则有最优解，假设。 R kR kˆˆˆˆˆˆ . (2)将中物体排序按照以下规则，,W)(P,W)......(P,W)(PR1122 RR 22 / 29

ˆˆˆ是前个最大价值。 ①k,P......PP12kˆˆPPii 1 ˆˆ。 ②从开始到满足WW i k 1Rii 1ˆ是第一个未装进去的价值，则 设PmP，， *maxP P P sP P s P mmaxIImk 1*P1，复杂度 k 1 O(n) 1 P1 kmax此处省略完全多项式近似方案及复杂度的分析 二十二、TSP问题 1、满足三角不等式的TSP是NPC HC TSP解：证明思路，将哈密顿回路HC问题多项式变换到TSP问题:，且HC NPC变换到TSP问题的实例是满足三角不等式的。因为，故满足三角不等式的。 TSP NPCHC TSP多项式变换： V}G V,E,V {VV...... 设HC的实例为，据此构造TS实例m1,2, G V,E,V V,(G必为完全)图，两个顶点之间的距离定义为1 i,j E d i,j 2 i,j EB m ，并设TSP旅游界值为。 易知这个变换是多项式的。 GB m若HC存在一条哈密顿回路，则这条回路在上的长度必为B，而是最短旅游的界值，故这条回路是满足实例的一个TSP旅游。 G若存在一个满足B的TSP旅游，则该旅游必经过长度为1的边，而这些边均在G上，因此这个TSP旅游在G上是一条HC回路。 HC TSPHC NPC这样就将，而。 23 / 29

变换到的TSP实例的边长为1或2，可知该实例满足三角不等式，这就证明了满足三角不等式的TSP问题是NPC问题。 2、TSP是强NPC：将其边长为1，2，是NPC， 强NPCHC TSP,答：TSP判定问题是数问题，因为任两城市间的距离及界值没有任何d i,j B约束。因为可以将，从而证明，而有限制， TSP1 d i,j 2HC TSPTSP NPC事实上,故不受限制的原始TSP问题是强NPC。因此TSP问题不存d i,j 1或2在拟多项式时间算法。 3、TSP优化 NP HARD将TSP判定TSP优化 4、TSP延伸 NP HARD已知部分旅游，能否延伸出一个长度不超过B的全程旅游回路 证明：将TSP判定TSP延伸。假设是求解TSP延伸问题的算法。 S[c,d, G ,B]设计TSP判定算法如下（折半法）： ① B m,B m max{d(cc)|cc C}minmaxi,ji,j②若 *B B 1，则B Bmaxminmin③ B (B B)2 midmaxmin④调用子程序：，若回答yes,则令,转②；否则S[c,d, C ,B]B Bmaxmid1mid，转②。 B Bminmid若，回答yes,否则no *k B复杂度 O(log(B B))2maxmin TSP判定是NPC TSP延伸是NP HARD（★重要）还有排工问题的考课件上的两个近似算法；和顶点覆盖问题 满足三角不等式的TS问题。 24 / 29

对实例对应的有权完全图G=，求最小生成树记为T;T中度为奇数的顶点集为，必为偶数个;调用最小对集算法P在V’中求出最小对集;将中加入T中，形成欧拉图D;在欧拉图中求出欧拉回路（P）;用抄近路方法将欧拉回路转换为TS旅游 证明：1中d(T)中d(Ep)<=1/2OPT(I)故有d(T)<=1/2OPT(I)... 当PNP时，求证TS优化问题不存在的多项式时间近似算法。反证法。 假设存在，则存在常数k使得;即存在多项式算法A，对最优解超过某常数的TSP实例G，有;设是HC实例，则构造TSP实例如F，，其中V’=V,;当中存在HC时，当中不存在时;因此可得当且仅当时，中存在HC回路;又因为A是多项式时间算法，故存在多项式时间算法解HC问题 与PNP矛盾 原题得证 排工问题 区间排工（有最早加工起始时间及加工最后期限） 证明 区间问题是排工问题 证明：设PAR实例，，长度，，构造排工实例 当B为奇数时，不能划分，所以只考虑B为偶数的情况 若存在PAR，则排工如下 ：将A’中对应的任务安排在之前，A- A’对应的安排之后，即为一个区间排工。 若存在一个排工，则将之前的所对应置入A’，又由于，故，，即PAR的一个划分。 因此，，所以区间排工NPC 独立排工问题 算法LPT Step1：将任务排序使：形成主次表：L={T1,T2,…,Tn}，t1 t2 … tn。 Step2：对主次表从1到扫描，若有空闲机器，则将任务安排到空闲机器上加工。直到完成。 独立任务排工问题的任意实例I，采用近似算法LPT求解，有： LPT(I)41 OPT(I)33m证明： 当m=1时，定理结论为真，结论显然是对的，就1台机器。 下面假设m>1。 观察性质： 首先可以假设最后完成的任务是tn，为什么，因为若最后一个任务为tk，则只考虑前k个任务即可。n-k个任务不管。若前k个任务满足结论，则前n个任务当然也满足结论。 取前k个任务形成实例I1，则OPT(I) OPT(I1)，LPT(I)=LPT(I1) 所以在[0,LPT(I)-tn]内所有任务都非空闲。 n 11 t LPT(I)-tn imi 1nm 11 t LPT(I) tn + immi 1n1 t OPT(I) imi 1tLPT(I)m 1n 1 所以： OPT(I)mOPT(I)因OPT(I) 3tn，若不然则每个机器上最多可以安排2个任务，n≤2m。这样的排工是最优的。当然满足。 所以... 背包问题 PNP时，背包问题不存在多项式时间绝对近似算法。 证明：假设存在算法A，则存在常数k，使得 将I复制k+1份得到I’ 所以OPT(I’)=(k+1)OPT(I) 由此可得背包问题的多项式最优解算法，与PNP矛盾，故假设不成立。 背包问题设计绝对性能比的多项式时间近似算法 1)将所有元素按排序2)按上述顺序依次装入背包，直至放不下，得可行解GA(I) 3)令A(I)=max{GA(I),}, 25 / 29

背包问题有最优解为，是得到的解，求证 证明：1）设R是最优解的背包元素下标集合，，，若|R|k，则可求到最优解，下面假设|R|>k2)将R中物体排成有序对，具体规则如下：a)前k个为R中受益最大的k个b)从i=k+1到|R|满足3)算法中必存在如下情况，即选定前k个作为包底，记; 设s是在此情况下调用L(I,P,W,M,n)增加的收益 设是在调用L(I,P,W,M,n)过程中第一个没有被装入包的元素4) 时间复杂度O(nk)=O(n) 划分 在已知划分问题实例存在划分的情况下T，求出具体划分：假定已有一张表t，n行，列，记，由于存在划分，则t[n,b]=T,记n=a 设一个集合A存放入选元素的下标 If (a<0 或 b0) 则返回集合A，为所求； Else 判断 a--，go 1) 将a加入集合A；b=b-S(a)；a--；go 1) WPAR问题 设计WPAR的拟多项式算法，判定并求解。 解：设，若B不能被3整除则无划分，若B能被3整除，则设计表t：n行，列 若，则最终回来yes，存在划分，否则No t(i,0)=T t(1,j)=T 若t[i-1,j]=T，则t[i,j]=T 若t[i-1,j-S()]=T，则t[i,j]= T T[i,-1]=F T[0,j]=F 求解算法： 记，记n=a （将入选元素的下标存入集合A） If (a<0 or b<=0) 则返回A为所求 Else 判断 a--; go 1) 将a加入集合A；；a--；go 1) 集合覆盖问题 实例，，C为子集族，询问询问：求使且最小，求证时，无多项式时间近似算法。 证明：1) 对任意实例，限制|S|=3q，，，则集合覆盖问题变为X3C 2) 假设该问题存在多项式时间近似算法A，则有 现将I复制k+1份，构造新实例I’，则有OPT(I’)=OPT(I)*(K+1)，在I’上应用算法A，则有 又且集合覆盖问题是求最小值问题，恒有， 因此，可构造算法A’，根据实例 I构造I’，用A求解I’得A(I’)及子集族C的子集C’ 计算，可得实例的最优解 因为A是多项式的，则A’亦是，即可在多项式时间内解答NPC问题，与PNP矛盾 故原题得证 给定几个整数满足(超递增)，有一正整数S，设计多项式算法A，找出一个n维向量使或确定无解，证明并分析复杂性。 算法：S’=S For (i=n to 1) {if () =1;; Else =0 ;} If (S’==0) x为所求 Else 无解 复杂性：O(n) 26 / 29

L为N元数组，其中元素递增，给定数值x，设采用二分搜索，查找x是否在数组中，要求，若x在L中，输出下标，否则输出0，并求出最大比较次数。 a)算法： l=1,r=n if (l>r) 则j=0; 转6) j=; if (x==L(j));转6) if (x>L(j)) l=j+1; else r=j-1; 转2) 输出j b) 比较次数：对二维搜索，每次搜索成功将范围减半，故最多比较次数为2的对数，又因为当n=1时至少比较1次，故比较次数不超过 2SAT实例，,判断是否有真值指派，若有求出。 算法：根据U,C构造有向图G，2n个顶点，分别是 若，则添加和两条边， 对，若有，则；若，则 判定：若图G中对，有和同时存在，则无真值指派。反之，亦是 （G上没有回路真值指派，因为G中无回路不同时存在） 求解： a)如2)所述赋值 b)扩展赋值（若有，则在的同时，对所有指向的节点赋0，所有指向的节点赋1） c) 对a、b之后，仍未赋值的变量，可同时赋0或同时赋1 已知MAXLA问题是NPC，求证MINLA亦是NPC MAXLA：简单图，询问是否一一映射，使 证明：根据MAXLA实例构造MINLA实例如下： 及k’，其中V’=V，，，则G’为G的补图： 又从MAXLA到MINLA的变换是多项式的 求证：第k个最大子集是NP-hard实例：有限集集合A每个，有，两个非负整数， 询问：A中是否存在k个不同的子集，满足 证明：设S[A,S,B,k]是个解第k个最大子集问题的子程序.构造划分问题实例A，，设计划分问题算法如下： S(A)为奇，则返回No 再调用一次S[A,S,B-1,] 若回答yes，则所有满足的A’也满足，故无划分 若回答No，则使，则划分 综上所述，若S是多项式算法，则可以多项式时间解释划分问题。 即PAR第k个最大子集问题 所以是Np-hard 运动员比赛表算法： var a:array[1-1024,1-1024] of integer Procedure bs(k:integer) Begin If k=0 then a[1,1]=1 else [ bs(k-1); {排左上角} for i=1 to do for j=+1 to do {排右上角} a[i,j]=a[i,j-]+ for i=+1 to do [ 27 / 29

for i=+1 to do {复制生成左下角} for j=1 to do a[i,j]=a[i-,j+] for j=+1 to do {复制生成右下角} a[i,j]=a[i-,j-] ] ] End Begin read(k); bs(k); Print(a); End. 算法16题 1 满足三角不等式的TSP问题是否是NPC问题，为什么？ 2 证明团问题是NPC问题 3 TSP判定问题是否为数问题，是否属于伪多项式算法，为什么？ 4 集合覆盖问题中，当P！=NP时，不存在多项式时间绝对近似算法。 5 区间排工是否是NPC问题，如果是独立排工问题，请设计一多项式时间算法，限制排工任务数目最大，再证明算法的正确性，并分析其复杂度 6 给定n个整数的超递增序列{a1,a2,…an}，对于一个正整数S，求出一个n维向量(x1,x2,…xn)，使得S=a1*x1+a2*x2+…+an*xn,或者无解。证明算法的正确性，分析算法的复杂性。【比较有可能，简单变形】 7 平面图的最大团问题有多项式时间算法吗？为什么？ 平面图的三着色问题有多项式时间算法吗？为什么？ 8 当P！=NP时，TSP优化问题是否存在多项式近似算法？ 9 划分问题的近似算法 10 L为n元数组，并且已经从大到小排好序，并给定数值x，试采用二分搜 28 / 29

索技术设计算法查找x是否再L中，要求：如果x在L中，输出L（j）=x，如果不在，则输出j=o，并证明比较次数为Llog2n+1 11 三角不等式的TSP问题是NP-Hard 12 2SAT问题 13 背包问题有时间复杂度为O（nlogn）的近似性能比R小于2的算法 14 已知MAXLA问题是NPC类，。。。 15 用图灵规约技术证明K个最大子集问题是NP-Hard问题。 16 比赛日程安排。 算法考试相关内容，师兄电脑里的 1 第二章算法设计技术，出一个题目。 2 第三，四章复杂的NPC（NP-hard）都不考，非常简单的可能考。 3 第五章中，2SAT问题 4 第六章划分问题的拟多项式算法可能考，也可能不考。 5 第七章的近似算法中，背包问题，装箱问题，TSP问题，排工问题。 6 最后两次课的内容可能考一个，不过最后一次讲的比较粗略，有可能考前一次讲的内容。 7 考试只有四个大题。 29 / 29

传说中的算法宝典