第四次算法作业-荆楠

1、1. 现有一台计算机，在某个时刻同时到达了 n个任务。该计算机在同 一时间只能处理一个任务，每个任务都必须被不间断地得到处理。 该 计算机处理这n个任务需要的时间分别为ai,a 2,an。将第i个任务 在调度策略中的结束时间记为 ei。请设计一个贪心算法输出这n个任 务的一个调度使得用户的平均等待时间 1/n Ee i达到最小。答案要求 包含以下内容：(1) 证明问题具有贪心选择性；(2) 证明问题具有优化子结构；(3) 根据贪心选择性和优化子结构用伪代码写出算法;(4) 分析算法的时间复杂度(题有问题，1/n Eei是平均响应时间，不是平均等待时间)答：贪心思想：为了使平均等待时间最短，每次

2、选择执行时间最短的任务。(1) 贪心选择性：不妨设编号为1的任务是n个任务中执行时间最短的，则我们只需要证明有 一个最优解是优先执行任务 1即可。那么，设i1,i 2,i n是一个最优解，则第 ij个任务的等待时间为fOi, 一 1,j = 1你-1j11eij-i =工 kk = 1,J * 1则平均等待时间T为:nn - 1乃=苕)1 .=-(n - 1) ?aj. + (n - 2)ai2 + (n -+ +. J若i 1=1，则显然有一个最有解优先执行任务1，若不然，设it=1，交换i 1和it，得到一个新的解i t,i 2,i t-1 ,i 1,i t+1,i n，这个新解的平均等待

3、时间T为nn - 11 ”-(n - 1)?日卜 + (n - 2)a|? +- t)%】+ +,n _ J由于那么，T - 1= (t - 1吕訂-aiJ 0。由于T是最小的，可知% 二 a二 min a,T=T,新解it,i 2,i t-i ,i i,i t+i,i n也是一个最优解，且。综上所述，该问题具有贪心选择性。(2) 优化子结构：设il,i2,in是n个任务的最优解，我们只需要证明i2,i n是剩余门-1个任务的最优解。显然i2,i n是子问题的一个最优解，其平均等待时间八 .,:-/ : H _I T X |。若不然，i 2,i n不是子问题门-1个任务的最优解，则一定有一个更

4、优的调度j2,jn,其平均 等待时间T vT，贝U ii,j 2,j n显然也是n个任务的解，且其平均等待 时间T二 T(n - 1)?曰i】+ (n -+ (n - t)曲 + + 日咕n二-(n - 1)?叭 + (n - 1)Tn|1r -(n - 1)?aM + (n - 1)T = I与i i,i 2,i n是n个任务的最优解相矛盾，因此i2,i n是子问题剩余n-1个任 务调度的最优解，该问题具有优化子结构。(3) 算法伪代码：In put : n个任务的时间a1: n Output: n个任务的调度 A1:nGreedy-Mi n-WaitTime(a)1 nlen gth(a)

5、2 create new array A1: n3 for i J1 to n4 do mi nx5 for j J1 to n6 do if aj18)分的纸币能够将它兑换成币值相等的硬币且使用硬币个数最少。 证明算法的正确性并分析其复杂度。答：贪心思想： 对于给定的面值， 每次都取尽可能多的当前可以取到的最大面值 硬币。 1 角=10分贪心选择性：尽可能多地取当前可取最大面值硬币， 即证明当n10时，最优解 是优先选择一个1角硬币，最优解为X。若不然，则需选择至少两个5分硬币来 替换该1角硬币，x x+1。以此类推，同理可证当5 nv 10时，优先选择一个 5分硬币，当2nv5时，优先选择

6、一个2分硬币，当nv 2时，选择1分硬币。 优化子结构：该问题显然具有优化子结构，当选择一个面值为m的硬币后，子问 题为n-m的硬币兑换问题，仍是选择面值Wn -m的最大面值的硬币。若不然，子 问题有一个更优的解使硬币个数 x-1x-1 ，那么加上选择的第一个硬币不等式 即可化为x vx，与原问题解是最优解相矛盾，因此该问题具有优化子结构。 算法伪代码：Input ：兑换面值 nOutput ：兑换硬币个数 xGreedy-Get-Change（n）1 x n/10+n%10/5+n%10%5/2+n%10%5%22 return x算法的时间复杂度为 O（1）。3.给定k个排好序的有序序列S

7、1,s 2，,s k,现在用2路归并排序算法对这些有序序列排序。 假定用 2 路归并排序算法对长度分别为 m 和 n 的有序序列排序要用 m+n-1 次比较操作。设计一个贪心算法合并S1,S2,，Sk使得所需的比较操作次数最少。答案要求包含以下内容：（1）证明问题具有贪心选择性；（2）证明问题具有优化子结构；（3）根据贪心选择性和优化子结构用伪代码写出算法；（4）分析算法的时间复杂度。答：贪心思想： 为了使比较操作的次数最少， 每次选择长度最小的两个有序序列 进行排序， 合成一个新的有序序列加入原序列中， 直至将 k 个有序序列合并为一 个有序序列为止。 整体思想类似赫夫曼编码， 可以将序列的

8、合并用树表示， 合并 得到的新序列用这两个左右节点的根节点表示。 则显然每个叶节点序列需比较的 次数就是这个序列所在树中的编码长度（树的深度，根节点深度为 0）。(1) 贪心选择性：不妨设S1,S2为长度最短的两个序列，则只需要证明存在一种最优解，其中 执行了 S1和S2的合并操作。设T是一个最优解构成的树，其中Sa和Sb是具有最 大深度的两个兄弟序列节点。不失一般性，设L(Sa) L(Sb)，L(Si) L(Si)，L(Sb) L(S2)。交换T中Sa和Si的位置，得到树 T，再交换Sb和 S2的位置得到树T。往证T是最优解构造的树。cost(T) - cost(TT )kk=JL(Si)?

9、dr(i) - (k - D - - (k - 1)i 二 1i = 1=LJdrtsa) + L(si)dr(si) -(希)-L(S)dT (si)=L(se)dT(sJ + HsdrCsi) - L(sfl)di(si) - L(si)di(sa)-CL(sa) - LfsO) (dT(sa) - dT(si)由 于 L(Sa) L(Si) ， dT(Sa)dT(Si)， 因 此 cost(T)- coSt(T) 0 ，coSt(T) coSt(T) 。同理可证 coSt(T ) coSt(T )，于是 coSt(T) cost(T)。由于 T 是最优化的，所以coSt(T) cost(

10、T)。于是cost(T)=cost(T) ，T也是合并最优解的树。因此该算法具有贪心选择性。(2) 优化子结构：设T是序列S=Si|0 i k的一个最优解构成的树，不妨设Sx和Sy是T中任 意连个相邻叶节点，Sz是他们的父节点，则Sz是长度为L(s z)= L(s x)+L(S y)的字 符，T=T-s x,s y是S=S-s x,Sy U Sz的优化解构成的树。往证 cost(T)=cost(T)+L(sx)+ L(s y)-i。对?v S-Sx,Sy ，:L。 由 于= dT(Sy)=+ 1,则有L(Sx)： ； +L(Sy)| 朋Q|- 1=(L(S x) + L(S y)( | 叱.冬

11、Q + 1)-1=(L(s x)+L(s y) dsj+ L(s x)+L(s y)-i=L(s z)L(S x)+L(s y)-i若T不是S的最优解，则必存在 T，使cost(T)cost(T) 。因为Sz是S 中的序列，则必为T中的叶子，把节点Sx与Sy加入T中，作为Sz的子节点， 则得到了 S的一个新的优化解树T，那么，cost(T、)=cost(T)+ L(sx)+L(s y)-iai,bibj ,不失一般性，优化解f中存在映射f(a i)=bj,f(a i)=bi。则代价* ap十血，Cr为其余映射项的代价和。交换bi与bj,令映射f 中包含映射f(a i)=bj,f(a J=bi。

12、那么一个新的解的代价 C=k - ? ; -C - C （a?1 + 詁十 Cr）-（昇 + a；b, + Cr）.r :一。又因为原映射f为优化解，故L W C。因此C二C,f 也为优化解，且ai=a , bi=bj。故 该问题具有贪心选择性。优化子结构：对排序后的 A,B中元素分别表示为ai,a2,a n和bi,b2,bn。映 射f : f(a i)=bi,1 i Wn是优化解，则只需证明映射f : f(a i)=bi,2 C-n，那么，C2-n，iC2-nW ,与f是原问题的优化解相矛 盾，因此厂 是其子问题的优化解，该问题具有优化子结构。5. 一个DNA序列X是字符集G, T, A,C

13、上的串，其上有大量信息冗余。设x是X的子串，x及其冗余形式在X内在出现的起、止 位置构成了一系列等长区间pi,qi,p円。试设计一个贪心算法 找出pi,q 1,p mqj中互不相交的区间的最大个数，即确定 x的独立冗余度。(1) 用伪代码写出算法；(2) 证明算法的正确性；答：贪心思想：为了获得最大的独立冗余度，每次选择qi最小的区间，使我们能够选更多的区间。(1)算法伪代码：不妨设等长区间I=p i,q 1,p m,q m已经按照qivq2Qj6 then S SU i7 j i8 return S(2)正确性证明：贪心选择性：需证明有一个优化解包含区间pi,qi即可。设S是一个优化解，按

14、终止位置排序S中的区间，设其第一个区间为k，第二个区间为j。如果k=1, 则命题成立；若kM 1,令S=S-k U 1,由于S中的区间互不相交，且qivqkvp , S中的区间也互不相交，因为|S|=|S| ，因此S也是一个优化解，且包含区间1, 故该问题具有贪心选择性。优化子结构：设A是一个优化解并且包括区间1,则A=A-1是子问题I=i I | piq#的优化解。显然A中的区间是不相交的，我们仅需要证明A是最大的，设不然，存在一个I 的相容区间问题的优化解 B，且|B|A，令B=1 U B，对于任意i I , piqi, B中的区间是不相交的，B是I的一个解。由于 |A|=|A|+1, |

15、B|=|B|+1|A|+1=|A| ，与A最大相矛盾，因此该问题具有优化子结构。6. 从哈尔滨到上海的高速公路上有若干个加油站。 如果汽车从一个加油站出发时油箱是满的， 则汽车可以顺利达到下一个加油站。 试设计一个汽车加油方案使得汽车在整个行驶路程中加油的次数最少， 证明所给方案的正确性。答：贪心思想： 当汽车到达一个加油站时， 若所剩汽油可以顺利到达下一个加油 站，则不加油，否则加油。贪心选择性：设在加满油后可行驶的 N千米这段路程上任取两个加油站 X,Y,且 X距离始点为m 丫距离始点为n,且mn那么，若在丫加油不能到达终点那么 在X加油一定不能到达终点，因为 m+Nn+N即在丫点加油可行

16、驶的路程比在 X 点加油可行驶的路程要长n-m千米，根据贪心选择，为使加油次数最少就会选择 距离加满油得点远一些的加油站去加油， 因此，加油次数最少这一问题具有贪心 选择性质。优化子结构：设公路沿途的加油站距起始位置的距离分别为 S1:n ， 需要加油的加油站编号 A1:k 为加油问题的一个优化解，则 A2:k 是剩余路程 S=S1:n-S1:A1的子问题的优化解。设不然，存在一个 S的加油问题的优化解 B， |B|A| ，由于第一次加油不影响后面的加油策略， 因此 B=BUA1 是S的一个优化解，且|B|=|B|+1 Sj _ 21，则X,Y 2,，丫 n是问题M的一个解，且 卩凶+耳-尸Y

17、i 与X1,X2，,Xn是优化解相矛盾。故该问题具有优化子结构。8. 写出分支界限的一般算法答：In put :搜索树的根rootOutput:问题的最优解SEARCH-TREE（root）1 新建一个队列Q, 个解re J null2 将root加入Q中3 while Q不为空4 do tmp J Q的队首元素出队5 for 每个 tmp 的孩子节点 v6 do if v是一个可行的节点789 价10then if v是一个解且(该解好于 re ，或 re 是 null )then reJ由节点v所在的分支构成的解else if v不是一个解且该分支代价小于 re 的代then将v加入Q中1

18、1 return reP1? Jk1、P2 ?J k2、R ?Jkn是一个可能解当且仅当 Jk1、Jk2、2. 证明如下命题：Jkn是一个拓扑排序的序列.证明：首先证明Pl? Jk1、P2 ?Jk2、Pn ? Jkn是一个可能解，则Jk1、Jk2、Jkn是 一个拓扑排序的序列。若不然，必有元素xvy,使JkxJky,而又有RvPy,与Pl? Jk1、 P2 ?Jk2、Pn ?Jkn是一个可能解矛盾，故Jk1、Jk2、Jkn是一个拓扑排序的序 列。接着证明若Jk1、Jk2、Jkn是一个拓扑排序的序列，则 R? Jk1、P2 ?Jk2、 Pn ?Jkn是一个可能解。根据定义，可知对任意xy,有RV

19、R且Jkx三Jky ,则R? Jk1、 P2?Jk2、Pn? Jkn是一个可能解。综上所述，命题成立。3. 修改拓扑排序算法，写出人员分配问题严格的分支界限搜索算法 答：其中RELAX-Z(C函数见第5题input: 人的集合 P, 偏序集合 J, 矩阵 C1:n1:n.output: 分配矩阵 X1:n1:n.Personnel-Assignment(P, J, C)1 新建根节点 root2 C, J RELAX-Z(C)3 新建小根优先队列 Q4 J 0, J J, j X, j null,nJlength(P)5 (root)6 while Q 非空7 do tmp J ()8 if

20、= n9 then if 10 thenJ tmp, J11 continue12 if 13 the n for each j14do if j15the n1617181920(x)21for i from n to 122do for j from 1 to n23do Xij24XiJ125wayJ26return X没有前序元素新建节点xJ+1, JJj,J + CjJ tmp将x加入到tmp的子节点中4. 构造下例的搜索树直到找出最优解/ =I234567i=lCO08393065020QC66371712263291X190125432S36600490805321567GO02

21、8608584289007180005813oc解：如下图:牲煙艸：穿t44M)*121:齐 mu Jtf |L. IJB*C*12*壽lM*7i 社型MH *.fe+4) fl聶*P5 J. mini then min if mini != X & mini!= then break for j from i to ndo if minj = 0then break if minj != 0 then continue 新建两个孩子 lchild, rchild Jclone, J clone for k from 1 to ndo minkJ XkminJX,J RELAX-ZJ + + m