第四次算法作业荆楠

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

2、 贪心选择性：不妨设编号为1的任务是n个任务中执行时间最短的，则我们只需要证明有一个最优解是优先执行任务1即可。那么，设i1,i2,in是一个最优解，则第ij个任务的等待时间为wij=0 ，j=1eij-1=k=1j-1aik ，j1则平均等待时间T为：T=1nj=1nwij=1nj=1n-1eij =1n(n-1)ai1+n-2ai2+(n-t)ait+ain-1若i1=1，则显然有一个最有解优先执行任务1，若不然，设it=1，交换i1和it，得到一个新的解it,i2,it-1,i1,it+1,in，这个新解的平均等待时间T为T=1nj=1nwij=1nj=1n-1eij =1n(n-1)a

3、it+n-2ai2+(n-t)ai1+ain-1由于ai1ait，那么，T-T=(t-1)(ai1-ait)0。由于T是最小的，可知T=T，新解it,i2,it-1,i1,it+1,in也是一个最优解，且ait=ai1=minj=0naij。综上所述，该问题具有贪心选择性。（2） 优化子结构：设i1,i2,in是n个任务的最优解，我们只需要证明i2,in是剩余n-1个任务的最优解。显然i2,in是子问题的一个最优解，其平均等待时间 T=1n-1n-2ai2+n-tait+ain-1。若不然，i2,in不是子问题n-1个任务的最优解，则一定有一个更优的调度j2,jn，其平均等待时间TT，则i1,

4、j2,jn显然也是n个任务的解，且其平均等待时间T =1nn-1ai1+n-2ai2+n-tait+ain-1=1nn-1ai1+n-1T<1nn-1ai1+n-1T=T与i1,i2,in是n个任务的最优解相矛盾，因此i2,in是子问题剩余n-1个任务调度的最优解，该问题具有优化子结构。（3） 算法伪代码：Input：n个任务的时间a1:nOutput：n个任务的调度A1:nGreedy-Min-WaitTime(a)1 nlength(a)2 create new array A1:n3 for i1 to n4 domin5 for j1 to n6do if aj<min7t

5、hen minaj8 Aij9 aAi10return A（4）时间复杂度分析：算法12行时间复杂度为O(1)，39行时间复杂度为O(n2)，10行时间复杂度为O(1)。故算法的时间复杂度为O(n2)。以上算法是根据贪心思想缩写的，但仔细观察可以发现该问题可等同于将任务按照执行时间大小进行递增排序，排序结果即为该组任务的一个最优调度，因此时间复杂度可降低为排序算法的时间复杂度O(nlogn)。2. 现有面值为1角、5分、2分、1分的硬币，每种硬币的个数都是无限的。给出一个贪心算法，使得对任意给定的面值为n(n>18)分的纸币能够将它兑换成币值相等的硬币且使用硬币个数最少。证明算法的正确性

6、并分析其复杂度。 答：贪心思想：对于给定的面值，每次都取尽可能多的当前可以取到的最大面值硬币。1角=10分贪心选择性：尽可能多地取当前可取最大面值硬币，即证明当n10时，最优解是优先选择一个1角硬币，最优解为x。若不然，则需选择至少两个5分硬币来替换该1角硬币，xx+1。以此类推，同理可证当5n10时，优先选择一个5分硬币，当2n5时，优先选择一个2分硬币，当n2时，选择1分硬币。优化子结构：该问题显然具有优化子结构，当选择一个面值为m的硬币后，子问题为n-m的硬币兑换问题，仍是选择面值n-m的最大面值的硬币。若不然，子问题有一个更优的解使硬币个数x-1<x-1，那么加上选择的第一个硬币

7、不等式即可化为xx，与原问题解是最优解相矛盾，因此该问题具有优化子结构。算法伪代码：Input：兑换面值nOutput：兑换硬币个数xGreedy-Get-Change(n)1xn/10+n%10/5+n%10%5/2+n%10%5%22return x算法的时间复杂度为O(1)。3.给定k个排好序的有序序列s1,s2 , , sk ,现在用2路归并排序算法对这些有序序列排序。假定用2路归并排序算法对长度分别为m和 n的有序序列排序要用m+n-1次比较操作。设计一个贪心算法合并 s1,s2,sk使得所需的比较操作次数最少。答案要求包含以下内容： （1）证明问题具有贪心选择性； （2）证明问题具

8、有优化子结构； （3）根据贪心选择性和优化子结构用伪代码写出算法； （4）分析算法的时间复杂度。 答：贪心思想：为了使比较操作的次数最少，每次选择长度最小的两个有序序列进行排序，合成一个新的有序序列加入原序列中，直至将k个有序序列合并为一个有序序列为止。整体思想类似赫夫曼编码，可以将序列的合并用树表示，合并得到的新序列用这两个左右节点的根节点表示。则显然每个叶节点序列需比较的次数就是这个序列所在树中的编码长度（树的深度，根节点深度为0）。（1）贪心选择性：不妨设s1,s2为长度最短的两个序列，则只需要证明存在一种最优解，其中执行了s1和s2的合并操作。设T是一个最优解构成的树，其中sa和sb是

9、具有最大深度的两个兄弟序列节点。不失一般性，设L(sa)L(sb)，L(s1)L(s2)。因为s1和s2是具有最短长度的序列，故有L(sa)L(s1)，L(sb)L(s2)。交换T中sa和s1的位置，得到树T，再交换sb和s2的位置得到树T。往证T是最优解构造的树。costT-costT=i=1kL(si)dTi-(k-1)-i=1kL(si)dT'i-k-1=L(sa)dTsa+L(s1)dTs1-L(sa)dT'sa-L(s1)dT's1 =L(sa)dTsa+L(s1)dTs1-L(sa)dTs1-L(s1)dTsa=(L(sa)-L(s1)(dTsa-dT(s1

10、)由于L(sa)L(s1)，dT(sa) dT(s1)，因此cost(T)-cost(T)0，cost(T)cost(T)。同理可证cost(T)cost(T)，于是cost(T)cost(T)。由于T是最优化的，所以cost(T)cost(T)。于是cost(T)=cost(T)，T也是合并最优解的树。因此该算法具有贪心选择性。（2）优化子结构：设T是序列S=si|0ik的一个最优解构成的树，不妨设sx和sy是T中任意连个相邻叶节点，sz是他们的父节点，则sz是长度为L(sz)= L(sx)+L(sy)的字符，T=T-sx,sy是S=S-sx,sysz的优化解构成的树。往证cost(T)=c

11、ost(T)+L(sx)+ L(sy)-1。对vS-sx,sy，dTv=dT'v，LsvdTsv=L(sv)dTsv。由于dTsx=dTsy=dTsv+1，则有L(sx) dTsx+L(sy) dTsy-1=(L(sx)+L(sy)( dTsz+1)-1=(L(sx)+L(sy) dTsz+ L(sx)+L(sy)-1= L(sz) dTsz+ L(sx)+L(sy)-1若T不是S的最优解，则必存在T，使cost(T)<cost(T)。因为sz是S中的序列，则必为T中的叶子，把节点sx与sy加入T中，作为sz的子节点，则得到了S的一个新的优化解树T，那么，cost(T)=cost

12、(T)+ L(sx)+L(sy)-1<cost(T)+ L(sx)+L(sy)-1=cost(T)，与T是优化解矛盾，故T是S的优化解树。（3）算法伪代码Input：k个序列S1:kOutput：合并最小代价costMin-Merge-Cost(S)1nlength(S)2cost03QS/*用build-heap建立堆*/4fori1 to n-1 5do zAllocate-Node()6xleftzExtract-MIN(Q) /*堆操作*/7yrightzExtract-MIN(Q) /*堆操作*/8zMerge (x,y)9costcost+length(x)+length(y

13、)-110Insert(Q,z) /*堆操作*/11return cost（4）时间复杂度分析：设Q由一个堆实现，建堆的时间复杂度为O(n)，每个堆操作要求O(logn)，循环n-1次为O(nlogn)。总的时间复杂度为T(n)= O(n)+ O(nlogn)。4.给定两个大小为n的正整数集合A和B。对于A到B的一个一一映射f，不妨设f(ai)=bi（i=1,n），则f的代价为i=1naibi。试设计一个贪心算法，找出从A到B的代价最大的一一映射。你的答案应包括： （1）用伪代码写出算法； （2）证明算法的正确性； 答：（1）贪心思想：为了得到代价最大的映射，每次选择A，B集合中最大的ai和b

14、i使得f(ai)=bi，这样获得的i=1naibi将最大。算法伪代码：Input：正整数集合A1:n,B1:nOutput：A到B的映射fMAX-MAP(A,B)1create new array f1:n1:22nlength(A)3Merge-Sort(A,1,n)4Merge-Sort(B,1,n)5for i1 to n6do fi1Ai7 fi2Bi8return f算法时间复杂度分析：算法第1-2行时间复杂度为O(1)，第3-4行时间复杂度为O(nlogn)，第5-7行时间复杂度为O(n)，第8行时间复杂度为O(1)。算法总的时间复杂度为T(n)=O(nlogn)。（2）证明算法正

15、确性贪心选择性：排序后的A,B中元素分别表示为a1,a2,an和b1,b2,bn。只需证明一个优化映射中存在f(a1)=b1。若优化解中不存在这一映射，设a1ai，b1bj，不失一般性，优化解f中存在映射f(a1)=bj,f(ai)=b1。则代价C=a1bj+aib1+Cr，Cr为其余映射项的代价和。交换b1与bj，令映射f 中包含映射f(a1)=bj,f(ai)=b1。那么一个新的解的代价C=a1b1+aibj+Cr。C-C=(a1b1+aibj+Cr)-(a1bj+aib1+Cr) =a1b1-a1bj+(aibj-aib1)=a1bja1b1-bj-1+aibj(1-aib1-bj)由于

16、b1bj，因此a1b1-bj-10, 1-aib1-bj0，CC。又因为原映射f为优化解，故CC。因此C=C,f 也为优化解，且a1=ai，b1=bj。故该问题具有贪心选择性。优化子结构：对排序后的A,B中元素分别表示为a1,a2,an和b1,b2,bn。映射f：f(ai)=bi,1in是优化解，则只需证明映射f ：f(ai)=bi,2in是子问题A-a1和B-b1的优化解。若不然，存在一个更优的映射f 使得A-a1到B-b1的代价更大，即C2-n>C2-n，那么，C2-n+a1bj>C2-n+a1bj,与f是原问题的优化解相矛盾，因此f 是其子问题的优化解，该问题具有优化子结构。

17、5. 一个 DNA序列 X 是字符集G, T, A,C上的串，其上有大量信息冗余。设 x 是 X的子串，x 及其冗余形式在 X 内在出现的起、止位置构成了一系列等长区间p1,q1,pm,qm。试设计一个贪心算法找出p1,q1,pm,qm中互不相交的区间的最大个数，即确定 x 的独立冗余度。 （1）用伪代码写出算法； （2）证明算法的正确性；答：贪心思想：为了获得最大的独立冗余度，每次选择qi最小的区间，使我们能够选更多的区间。（1）算法伪代码：不妨设等长区间I=p1,q1,pm,qm已经按照q1<q2<<qm排序。Input：排序后区间p1,q1,pm,qm的集合I对应的区间

18、起始位置集合P，和终止位置集合QOutput：互不相交的区间集合SGreedy-Interval-Selector(P,Q)1nlength(P)2S13j14for i2 to n5do if Pi>Qj6then SSi7 ji8return S（2）正确性证明：贪心选择性：需证明有一个优化解包含区间p1,q1即可。设S是一个优化解，按终止位置排序S中的区间，设其第一个区间为k，第二个区间为j。如果k=1，则命题成立；若k1，令S=S-k1，由于S中的区间互不相交，且q1<qk<pj，S中的区间也互不相交，因为|S|=|S|，因此S也是一个优化解，且包含区间1，故该问题具

19、有贪心选择性。优化子结构：设A是一个优化解并且包括区间1，则A=A-1是子问题I =iI | pi>q1的优化解。显然A中的区间是不相交的，我们仅需要证明A是最大的，设不然，存在一个I 的相容区间问题的优化解B，且|B|>A，令B=1B，对于任意iI ，pi>q1，B中的区间是不相交的，B是I的一个解。由于|A|=|A|+1，|B|=|B|+1>|A|+1=|A|，与A最大相矛盾，因此该问题具有优化子结构。6.从哈尔滨到上海的高速公路上有若干个加油站。如果汽车从一个加油站出发时油箱是满的，则汽车可以顺利达到下一个加油站。试设计一个汽车加油方案使得汽车在整个行驶路程中加油

20、的次数最少，证明所给方案的正确性。 答：贪心思想：当汽车到达一个加油站时，若所剩汽油可以顺利到达下一个加油站，则不加油，否则加油。贪心选择性：设在加满油后可行驶的N千米这段路程上任取两个加油站X,Y，且X距离始点为m，Y距离始点为n，且m<n。那么，若在Y加油不能到达终点那么在X加油一定不能到达终点，因为m+N<n+N，即在Y点加油可行驶的路程比在X点加油可行驶的路程要长n-m千米，根据贪心选择，为使加油次数最少就会选择距离加满油得点远一些的加油站去加油，因此，加油次数最少这一问题具有贪心选择性质。优化子结构：设公路沿途的加油站距起始位置的距离分别为S1:n，需要加油的加油站编号A

21、1:k为加油问题的一个优化解，则A2:k是剩余路程S=S1:n-S1:A1的子问题的优化解。设不然，存在一个S的加油问题的优化解B，|B|<|A|，由于第一次加油不影响后面的加油策略，因此B=BA1是S的一个优化解，且|B|=|B|+1<|A|+1=|A|，与A最小矛盾，因此该问题具有优化子结构。7.背包问题定义如下：输入：正数P1,P2,Pn,W1,W2,Wm,M输出：X1,X2,Xn,0£Xi£1,使得 S1£ i£ nPiXi最大 S1£ i£ nWiXi£M给出一个求解背包问题的贪心算法，并证明算法的正确

22、性。答：贪心思想：计算每件物品的单位价值Pi/Wi，取尽可能多的单位价值最高的物品，若这一物品放入背包后没有放满，则继续取单位价值次之的物品，重复此过程，直至背包放不下为止。算法正确性证明：贪心选择性：不妨设C1=P1/W1是单位价值最高的物品，则只需要证明有一个优化解中包含min(1,M/W1)即可。设X1,X2,Xn是一组优化解，若X1min(1,M/W1)，即X1min(1,M/W1)，令y= min(1,M/W1)-X1,在优化解中，这y*W1的背包空间由剩余物品占用，设这些物品的数量分别是A2,A3,An。则y*W1i=2nWiAi,因此有i=2nPiAi=i=2nCiWiAimax

23、i=2 to nCii=2nWiAi<C1yW1=yP1。即将这些物品的组合换成y个P1可以得到更优解，与,Xn是最优解相矛盾。因此X1=min(1,M/W1)，算法具有贪心选择性。优化子结构：不妨设C1=P1/W1是单位价值最大的物品，设X1,X2,Xn是一组优化解，则只需证明X2,Xn是M-X1W1的优化解。若不然，设Y2,Yn是M-X1W1的优化解，有i=2nPiYi>i=2nPiXi，则X1,Y2,Yn是问题M的一个解，且P1X1+i=2nPiYi>i=1nPiXi与X1,X2,Xn是优化解相矛盾。故该问题具有优化子结构。8.写出分支界限的一般算法答：Input：搜索

24、树的根rootOutput：问题的最优解SEARCH-TREE(root)1新建一个队列Q，一个解renull2将root加入Q中3while Q不为空4 do tmp Q的队首元素出队5 for 每个tmp的孩子节点v6 do if v是一个可行的节点7 then if v是一个解且（该解好于re，或re是null）8 then re由节点v所在的分支构成的解9 else if v不是一个解且该分支代价小于re的代价10 then 将v加入Q中11return re2.证明如下命题：P1® Jk1、P2 ® Jk2、Pn ® Jkn是一个可能解, 当且仅当Jk1

25、、Jk2、Jkn是一个拓扑排序的序列.证明：首先证明P1® Jk1、P2 ® Jk2、Pn ® Jkn是一个可能解，则Jk1、Jk2、Jkn是一个拓扑排序的序列。若不然，必有元素x<y，使Jkx>Jky，而又有Px<Py，与P1® Jk1、P2 ® Jk2、Pn ® Jkn是一个可能解矛盾，故Jk1、Jk2、Jkn是一个拓扑排序的序列。接着证明若Jk1、Jk2、Jkn是一个拓扑排序的序列，则P1® Jk1、P2 ® Jk2、Pn ® Jkn是一个可能解。根据定义，可知对任意x<y，

26、有Px<Py且JkxJky，则P1® 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新建根节点root2C, root.cost RELAX-Z(C)3新建小根优先队列Q4root.depth 0, root.J J, way.cost , way.node null,

27、nlength(P)5Q.add(root)6while Q 非空7 do tmp Q.front()8 if tmp.depth = n9 then if tmp.cost < way.cost10 then way.node tmp, way.costtmp.cost11 continue12 if tmp.cost < way.cost13 then for each jtmp.J14 do if j没有前序元素15 then 新建节点x16 x.depth tmp.depth+1, x.J tmp.J-j17 x.x j, x.cost tmp.depth + Cx.dep

28、thj18 x.parent tmp19 将x加入到tmp的子节点中20 Q.add(x)21for i from n to 122 do for j from 1 to n23 do Xij 024 Xiway.node.x 125 way way.node26return X4.构造下例的搜索树直到找出最优解解：如下图：5.给出求解旅行商问题的详细算法答：算法伪代码如下：Input: 各边的邻接矩阵Z1:n1:nOutput: 最短的旅行路线L1:nTSP(Z)1n length(Z)2Z, cost RELAX-Z(Z)3新建一个小根优先队列minQ4新建一个树根root5root.Z

29、Z, root.cost cost6way.root null, way.cost 7minQ.add(Z)8while minQ 非空9 do tmp minQ.front()10 if tmp 是一个问题的解 且 (tmp.cost < way.cost)11 then way.roottmp, waytmp.cost12 continue13 i 114 while i n15 do min 116 for j from 1 to n17 do if tmp.Zji != X && tmp.Zmini!=18 then if tmp.Zji > tmp.Zmi

30、ni19 then min j20 if tmp.Zmini != X && tmp.Zmini!=21 then break22 for j from i to n23 do if tmp.Zminj = 024 then break25 if tmp.Zminj != 026 then continue27 新建两个孩子lchild, rchild28 lchild.Z clone(tmp.Z), rchild.Z clone(tmp.Z)29 for k from 1 to n 30 do lchild.Zmink X31 rchild.Zkmin X32 lchild.Z, lchild.cost RELAX-Z(lchild.Z)33 lchild.cost lchild.cost + tmp.cost + tmp.Zminj34 lchild.parent tmp, lchild.road m