算法分析和设计[贪心法].ppt

1、多机调度问题：设有n 项独立的作业{1,2,…, n},由m 台相同的机器加工处理。作业i 所需要的处理时间为ti。约定：任何一项作业可在任何一台机器上处理，但未完工前不准中断处理；任何作业不能拆分成更小的子作业。多机调度问题要求给出一种调度方案，使所给的n 个作业在尽可能短的时间内由m 台机器处理完。利用贪心策略，设计算法解决多机调度问题，并计算其时间复杂度。 2、设有7 项独立的作业{1,2,3,4,5,6,7},要由三台机器M1, M2 ,M3 处理。各个作业所需要的处理时间分别为{ 2,14,4,16,6,5,3}。利用你设计的贪心算法，安排作业的处理顺序使得机器处理作业的时间最短。 课 后 思 考 题 带限期序作业排序的贪心算法 procedure JS(D,J,n,k) integer D(0:n),J(0:n),i,k,n,r D(0)?J(0)?0; k?1;J(1)?1; for i?2 to n do r?k; while D(J(r))D(i) and D(J(r)) ≠r do r?r -1; repeat if D(J(r))≤D(i) and D(i)r then for i?k to r+1 by –1 do J(i+1)?J(i) repeat J(r+1)?i ; k?k+1； endif repeat End JS 找到插入位置 检查插入的可能性 插入值 对于带限期序作业排序的贪心算法JS有两个赖以测量其复杂度的参数，即作业数 n 和包含在解中的作业数 s 。内层的while循环至多循环k次，插入作业 i 要执行时间为O(k-r)，外层for循环共执行(n-1)次。 如果s是k的终值，即s是最后所得解的作业数，则JS算法所需要的总时间为O(sn)。由于s ≤n，所以JS算法的时间复杂度为O(n2)。 带限期序作业排序的贪心算法 一种更快的作业排序算法 通过使用不相交集合的UNION与FIND算法以及使用一个不同的方法来确定部分解的可行性，可以将该问题的计算时间由O(n2)降到接近于O(n)。 规则是：若还没有给作业i分配处理时间，则分配给它时间片[a-1,a],其中a应尽量取大且时间片[a-1,a]是空的。若正被考虑的新作业不存在这样的a，这个作业就不能计入解中。 一种更快的作业排序算法(续) 例：设n=5,(p1,…,p5)=(20,15,10,5,1)和（d1,…,d5)=(2,2,1,3,3) 0 1 2 3 j1 j2 j4 最优解是J={1,2,4} J 已分配时间片 正被考虑作业 动作 0 无 1 分配[1,2] {1} [1,2] 2 分配[0,1] {1,2} [0,1],[1,2] 3 不适合，舍弃 {1,2} [0,1],[1,2] 4 分配[2,3] {1,2,4} [0,1],[1,2],[2,3] 5 舍弃 作业排序的一个更快算法 procedure FJS(D,n,b,J,k) //假定p1≥p2≥…≥pn , b=min{n,max{D(i)}} Integer b,D(n),J(n),F(0:b),P(0:b) for i=0 to n do F(i)=i; P(i)=-1 repeat k=0 for i=1 to n do j=FIND(min(n,D(i))) if F(j)0 then k=k+1;J(k)=i L=FIND(F(j)-1); call UNION(L, j) F(j)=F(L) endif repeat end FJS 查看实例 课后思考题 0/1背包问题：在杂货店比赛中你获得了第一名，奖品是一车免费杂货。店中有n 种不同的货物。规定从每种货物中最多只能拿一件，车子的容量为c，物品i 需占用wi 的空间，价值为pi。你的目标是使车中装载的物品价值最大。当然，所装货物不能超过车的容量，且同一种物品不得拿走多件。如何选择量度标准才能找到最优解？ 若n=2, w=[100,10,10],p=[20,15,15],c=105。证明利用价值贪心准则时，所得结果是否是最优解？ 3.4 最优归并模式 X1 X2 X3 X4 Y1 Y2 Y3 X1 X2 X3 X4 Y1 Y2 Y3 第二章中学习了如何用分治法将两个分别包含n个和m个记录的已分类文件在O(n+m)时间内归并成一个包含(n+m)个记录的分类文件。下面是两种将4个文件进行归并的方法。不同的配对法要求不同的计算时间。 什么是归并模式 给出n个文件，则由许多种把这