第四次算法作业-荆楠

1、1. n个任务。该计算机在同计算机处理这 n 个任务需要的时间分别为 a ,a ,a 。将第 i 个任务1 2n在调度策略中的结束时间记为 e n个任i务的一个调度使得用户的平均等待时间 1/ne 达到最小。答案要求i包含以下内容：（1）证明问题具有贪心选择性；（2）证明问题具有优化子结构；（3）根据贪心选择性和优化子结构用伪代码写出算法；（4）分析算法的时间复杂度（题有问题，1/ne 是平均响应时间，不是平均等待时间）i答：贪心思想：为了使平均等待时间最短，每次选择执行时间最短的任务。（1） 贪心选择性：不妨设编号为 1 的任务是 n 一个最优解是优先执行任务 1 即可。那么，设i ,i ,

2、i 是一个最优解，则第i 个任务的等待时间为1 2nj0e，j = 1，j 1w = 则平均等待时间 T为：11T = = 1 =1)+( +12若 i ，则显然有一个最有解优先执行任务 1，若不然，设 i，交换 i 和1t1i，得到一个新的解 i,i ,i ,i ,i ,i ，这个新解的平均等待时间为tt 2t-1 1 t+1n11T = = 1=1)+( + +21 0T T=T，由于 = 11新解 i,i ,i ,i ,i ,i 也是一个最优解，且 = min。t 2t-1 1 t+1n1综上所述，该问题具有贪心选择性。（2） 优化子结构：设 i ,i ,i 是 n i ,i 是剩余 n

3、-1个任1 2n2n务的最优解。显然 i ,i 是子问题的一个最优解，其平均等待时间 T =2n1 ( +( ) +i,i 不是子问题n-1个2n2 j ,j T，2n则 i ,j ,j 显然也是 n个任务的解，且其平均等待时间1 2n1T = ( +( +( ) +121= ( +(n1)T11 ( +(n1)T = T1与 i ,i ,i 是 n i ,i 是子问题剩余 n-1个任务调度的最优解，该问题具有优化子结构。1 2n2n（3） 算法伪代码：n 个任务的时间 a1:nOutput：n 个任务的调度 A1:nGreedy-Min-WaitTime(a)1nlength(a)23cre

4、ate new array A1:nfor i1 to n4do min5for 1 to n6do if aj18)分的的正确性并分析其复杂度。硬币。1 角=10分 n10 是优先选择一个 1 角硬币，最优解为x。若不然，则需选择至少两个5 分硬币来替换该 1 角硬币，xx+1。以此类推，同理可证当 5n10 时，优先选择一个5 2n5 2 n2 1 分硬币。优化子结构：该问题显然具有优化子结构，当选择一个面值为 m 的硬币后，子问题为 n-m 的硬币兑换问题，仍是选择面值n-m 的最大面值的硬币。若不然，子问题有一个更优的解使硬币个数 x-1x-1即可化为 x，与原问题解是最优解相矛盾，因

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

6、化子结构用伪代码写出算法；（4）分析算法的时间复杂度。 k 个有序序列合并为一次数就是这个序列所在树中的编码长度（树的深度，根节点深度为 0（1）贪心选择性：不妨设 s ,s 1 2行了 s 和 s 的合并操作。设T 是一个最优解构成的树，其中s 和 s 是具有最大深度的两个兄弟序列节点。不失一般性，设12abL(s s ，L(s )L(s )。因为 s 和 s 是具有最短长度的序列，故有 L(s s ，ab1212a1L(s s 。交换 T 中 s 和 s 的位置，得到树 ，再交换 s 和 s 的位置得到树b2a1b2。往证 是最优解构造的树。kkcost(T)cost(T) = L(s )

7、d (k1)L(s )d (k1)iTiTi=1i=1)d (s )+L(s )d (s )L(s )d (s )L(s )d (s )=L(sa=Ta1T1aa11TTd (s )+d (s )(s ) (s )d (s )d (s )L(sa)L(s )L(s )L(s )Ta1T1aT11Ta= (L(s ) L(s )a11由于 L(s s ，d (s ) d (s ，因此 cost(T)-cost(T)0，cost(T)cost(T)。同理a1T aT 1可证 cost(T)cost(T)，于是 cost(T)cost(T)。由于 T 是最优化的，所以cost(T)cost(T)。于

8、是 cost(T)=cost(T)，T也是合并最优解的树。因此该算法具有贪心选择性。（2）优化子结构：设 T 是序列 S=s的一个最优解构成的树，不妨设s 和 s 是 T 中任意ixy连个相邻叶节点，s 是他们的父节点，则 s 是长度为 L(s )= L(s )+L(s 的字符，zzzxyT=T-s,s 是 S=S-s ,s s 的优化解构成的树。往证 cost(T)=cost(T)+L(s )+ L(s )-1。对vS-s ,s ， ( ) =x yx yzxy( )，L(s )d (s ) = L(s )d (s )。由于d (s ) =x yvTvvvTxd (s ) = d (s )+

9、1，则有TyvL(s )d (s )+L(s)d (s )-1=(L(s)+L(s )(d(s +1)-1xTxTyxyz=(L(s )+L(s )d (s )+ L(s)+L(s )-1xyzxy= L(s )d (s + L(s)+L(s )-1zzxy若 不是 S的最优解，则必存在，使cost(T)cost(T)。因为s 是 中的序z列，则必为 中的叶子，把节点 s 与 s 加入 中，作为 s 的子节点，则得到xyz了 S 的一个新的优化解树 ，那么，cost(T)=cost(T)+ L(s )+L(s )-1C ，那么，C +C +,与 f是原问题的优化解相矛盾，因此 f2-n2-n2

10、-n12-n1是其子问题的优化解，该问题具有优化子结构。5. 一个 DNA序列 X 是字符集G, T, A,C上的串，其上有大量信息冗余。设 x 是 Xx 及其冗余形式在 X 内在出现的起、止位置构成了一系列等长区间p ,q ,p ,q 。试设计一个贪心算法11m m找出p ,q ,p ,q x 的独1 1m m立冗余度。（1）用伪代码写出算法；（2）证明算法的正确性；q 最小的区间，使我们能够选更多的区间。i（1）算法伪代码：不妨设等长区间 I=p ,q ,p ,q 已经按照 q q Qjthen SSiji8 return S（2）正确性证明：贪心选择性：需证明有一个优化解包含区间p ,q

11、 即可。设S 是一个优化解，按11终止位置排序 S k j k=1命题成立；若 ，令 1，由于 S 中的区间互不相交，且 q q q 是最大的，i1设不然，存在一个 I 的相容区间问题的优化解 ，且|B|A，令 ，对于任意 iI pq B中的区间是不相交的，B是 I|A|=|A|+1，i1|B|=|B|+1|A|+1=|A|，与 A最大相矛盾，因此该问题具有优化子结构。6.所给方案的正确性。站，则不加油，否则加油。贪心选择性：设在加满油后可行驶的 N 千米这段路程上任取两个加油站 X,Y，且 X 距离始点为 m，Y 距离始点为 n，且 mn。那么，若在 Y 加油不能到达终点那么在 X Y点加油

12、可行驶的路程比在 X 点加油可行驶的路程要长 n-m 千米，根据贪心选择，为使加油次数最题具有贪心选择性质。优化子结构：设公路沿途的加油站距起始位置的距离分别为 S1:n，需要加油的加油站编号 A1:k为加油问题的一个优化解，则 A2:k是剩余路程S=S1:n-S1:A1的子问题的优化解。设不然，存在一个 S的加油问题的优化解 |B|A|，由于第一次加油不影响后面的加油策略，因此A1是 S|B|=|B|+1|A|+1=|A| A 结构。7.背包问题定义如下：输入：正数 P ,P ,P ,W ,W ,W ,M12n12m输出：X ,X ,X ,0X使得12ni PX 最大1 n i i WXM1

13、 ni i给出一个求解背包问题的贪心算法，并证明算法的正确性。答：贪心思想：计算每件物品的单位价值 P/W，取尽可能多的单位价值最高的物品，若这一物品放入背包后没有放满，则继续取单位价值次之的物品，重复ii此过程，直至背包放不下为止。算法正确性证明：贪心选择性：不妨设 C =P /W 是单位价值最高的物品，则只需要证明有一个优111即可。设 X ,X , ,X 是一组优化解，若化解中包含 min(1,，即 X112nX min(1,1min(1,中，这 y*W 的背包空间由剩余物品占用，设这些物品的数量分别是A，令 y= 11,在优化解1111-,A ,A 。则 y*W ,因此有23n1max

14、 ，则 X ,Y ,Y 是问题M 的一个解，X ,X ,X 是优化解相矛盾。故该问题具有优1且112n+ 与1 112n化子结构。8.写出分支界限的一般算法答：搜索树的根 rootOutput：问题的最优解SEARCH-TREE(root)1 新建一个队列 ，一个解 null2 将 root 加入 Q中3 while Q不为空456do tmp Q的队首元素出队for 每个 tmp 的孩子节点 vdo if v是一个可行的节点7then if v是一个解且（该解好于 ，或 re是 null）8910then 由节点 v 所在的分支构成的解else if v不是一个解且该分支代价小于 re的代价

15、then 将 v 加入 Q中11 return re2.证明如下命题：P J P J P J 是一个可能解, 当且仅当 J 、1k12k2nknk1J J 是一个拓扑排序的序列.k2kn证明：首先证明 P J P J P J 是一个可能解，则J J J1k12k2nknk1k2kn是一个拓扑排序的序列。若不然，必有元素 ，使 J J ，而又有 P P ，与kx kyxyP J 、P J 、P J 是一个可能解矛盾，故J J 、J 是一个拓扑排序的序列。1k12k2nknk1k2kn接着证明若 J J J P J P J 、k1k2kn1k12k2P J P P 且 J J P nknxykxk

16、y1J P J 、P J 是一个可能解。综上所述，命题成立。k12k2nkn3.修改拓扑排序算法，写出人员分配问题严格的分支界限搜索算法答：其中 RELAX-Z(C)函数见第 5 题input: 人的集合 P, 偏序集合J, 矩阵 C1:n1:n.output: 分配矩阵 X1:n1:n.Personnel-Assignment(P, J, C)1 新建根节点 root2 C, root.cost RELAX-Z(C)3 新建小根优先队列 Q4 root.depth 0, root.J J, way.cost , way.node null,nlength(P)5 Q.add(root)6 w

17、hile Q 非空7do tmp Q.front()8if tmp.depth = n91011then if tmp.cost way.costthen way.node tmp, tmp.costcontinue12131415if tmp.cost way.costthen for each jtmp.Jdo if j 没有前序元素then 新建节点 x16x.depth tmp.depth+1, x.J tmp.J-j1718x.x j, x.cost tmp.depth + Cx.depthjx.parent tmp1920将 x 加入到 tmp 的子节点中Q.add(x)21 fo

18、r i from n to 12223do for j from 1 to ndo Xij 02425Xiway.node.x1wayway.node26 return X4.构造下例的搜索树直到找出最优解解：如下图：5.给出求解旅行商问题的详细算法答：算法伪代码如下：Input: 各边的邻接矩阵 Z1:n1:nOutput: 最短的旅行路线 L1:nTSP(Z)1 n length(Z)2 , cost RELAX-Z(Z)3 新建一个小根优先队列 minQ4 新建一个树根 root5 root.Z , root.cost cost6 way.root null, way.cost 7 mi

19、nQ.add()8 while minQ 非空9do tmp minQ.front()101112if tmp 是一个问题的解 且 (tmp.cost tmp.Zminithen min jif tmp.Zmini != X & tmp.Zmini!=then breakfor j from i to ndo if tmp.Zminj = 0then breakif tmp.Zminj != 0then continue新建两个孩子 lchild, rchildlchild.Zclone(tmp.Z), rchild.Z clone(tmp.Z)for k from 1 to ndo lchild.Zmink Xrchild.Zkmin Xlchild.Z, lchild.cost RELAX-Z(lchild.Z)lchild.cost lchild.cost + tmp.cost + tmp.Zminjlchild.parenttmp, lchild.road min+“”+jminQ.add(lchild)rchild.Zminj cost tmp.cost, min11, min21for