4贪心法2013.pptVIP

3、采用树结构表示集合，并用根k代表集合。采用过程Find(i)找到根节点k，找到了根节点，即找到了作业i的安排区间。 4、用集合的不相交并运算Union(k,j)将以k为根的树所代表的集合与以j为根的树所代表的集合合并成一个新的集合。 GreedyTreeJob(D, n, b, J, k) //p1? p2? ?????? ? pn ， for i ← 0 to n do F[i] ← i // F[i]=i表示集合i最右的空闲区间 P[i] ← -1 //将树初始化，P[i]=-1表示i是根节点 endfor k=0 // 初始化J for i ← 1 to n do //开始使用贪心准则 { j ← Find(min{n,D[i]}); //找i的根节点 if F[j]?0 then //找到了最靠右的空闲区j { k←k+1 J[j] ←i //安排作业i s ← Find(F[j]-1) //找前一个集合的根节点 F[j] ← F[s] //两个集合共用一个最靠右的空闲区F[s] t ← Union(s, j) //合并两个集合,t是新的根节点 P[t] ← P[s]+P[j] // 集合中的节点数 } } end GreeduTreeJob n=5,(p1,p2,p3,p4,p5)=(20,15,10,5,1),(d1,d2,d3,d4,d5)=(2,2,1,3,3) -1 -1 -1 -1 -1 P 0 1 2 3 4 5 F -2 1 -1 -1 -1 P 0 1 1 3 4 5 F i=2 D[i]=2 j= 1←find(2) J[1] ←2 k ←2 S← find(0)=0 t←Union(s, j) =0 -1 0 1 2 3 4 5 0 1 2 3 4 5 -1 0 1 -1 -1 -1 P -3 i=1 D[i]=2 j←find(2)=2 J[2] ←1 k ←1 S←find(1)=1 t←Union(s, j) =1 0 0 1 3 4 6 F i=3 D[i]=1 j= 0←find(1) 不能安排 0 1 0 -1 -1 P -3 0 0 1 0 4 6 F i=4 D[i]=3 j←find(3)= 3 J[3] ←4 k ←3 i=5 D[i]=3 j←find(3)= 0 不能安排 find(a) //查找树根 b←a while p[b]≥0 do //找根节点 b←p[b] root←b b←a while p[b]≥0 do//路径压缩 { c←p[b] p[b]←root b←c } return root end -6 1 1 1 3 2 3 4 5 4 5 6 -6 1 1 3 4 5 2 3 4 5 6 例：a=6 root =1 -6 1 1 1 3 2 1 1 1 4 5 6 -6 1 1 1 1 1 2 3 4 5 6 union( a, b) //合并两个集合 c ← find(a) d ← find(b) p[c] ← p [c]+ p[d] //维护结点数 p[d] ← c } 多机调度问题 多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。 这个问题是NP完全问题，到目前为止还没有有效的解法。对于这一类问题,用贪心选择策略有时可以设计出较好的近似算法。 多机调度问题 设7个独立作业{1,2,3,4,5,6,7}由3台机器M1，M2和M3加工处理。各作业所需的处理时间分别为{2,14,4,16,6,5,3}。按算法greedy产生的作业调度如下图所示，所需的加工时间为17。 贪心法总结 适合用贪心法的问题应具有最优子结构性质：原问题的最优解包含了其子问题的最优解。 例如背包问题，原问题的最优解是在背包的容积的限定 下利润达到最大，实际上是一个单位容积利润最大的问题。它包含子问题的最优。 带限期的作业调度，是在限期的约束下，利