5算法第五章贪心法讲义.ppt

* 确定作业集合J是否是可行解 检验J的所有可能的排列 б=i1,i2,…,ik是J中作业的一种排列; 完成作业ij的最早时间是j，1≤j≤k； 若排列中的每个作业的dij≥j，则б是一个允许的调度序列，J是一个可行解；否则，检验其他排列形式。 检验一种特殊的排列：按期限的非降次序。 * 一个例子 (p1,p2,p3,p4)=(100,10,15,20), (d1,d2,d3,d4)=(2,1,2,1) б : d2 ≤ d4 ≤ d1 ≤ d3 J={1, 4} 处理次序: 4, 1 , J是一个可行解 J={2, 3} 处理次序: 2, 3 , J是一个可行解 J={2, 4} 处理次序: 2, 4 , 但是作业4违反的它的期限, 所以J不是一个可行解 * 定理5.3 设J是k个作业的集合, б=i1,i2,…,ik是J中作业的一种排列, 它使得di1≤di2≤…≤dik。J是一个可行解, 当且仅当J中的作业可以按照б的次序而又不违反任何一个期限的情况来处理。 * 证明思想 如果J中的作业可以按照б的次序而又不违反任何一个期限，则J是一个可行解。 若J是可行解，则必存在б’=r1,r2,…,rk，使得drj≥j，1≤j≤k。 假设б’≠б，令a是使得ra≠ia的最小下标。 设rb=ia，显然ba。 在б’中交换ra与rb的位置，产生新的可行排列б”。 连续使用这种方法，就将б’转换成б且不违反任何一个期限。 б’ : ……ra.…...….. б : ……ia ……….. rb. б” : ……rb.…...….. б : ……ia ……….. ra. ra延后执行是否可行？ drb=dia≤dra * 首先将作业按p1≥p2 ≥ … ≥ pn排序, 将作业1存入数组J中, 然后处理作业2到作业n。 假设已处理了i–1个作业, 其中有k个作业已存入J(1),J(2)…J(k)中, 且D[J(1)]≤D[J(2)]≤…≤D[J(k)]。 现在处理作业i, 判断J∪{i}是否可行, 既是否能找到一个适当的位置r，使i排列在r+1位置，满足如下条件： D[i]r； D[J(r)]≤D[i]； D[J(l)]l, r+1≤l≤k； 若找到，则进行如下处理： 位置r+1…k共k–r个作业依次后移一个位置，即延迟一个单位时间再处理； 作业i插入到r+1位置,既在时间片r开始时处理。 根据定理5.3, 带有限期的作业排序问题可如下处理。 类似于直接插入法对期限值进行非降次序排列。 * J[0] J[1] J[2] J[3] J[4] J[5] 0 3 1 2 J[0] J[1] J[2] J[3] J[4] J[5] 0 1 0 1 2 3 4 5 p 20 15 10 5 1 d 0 2 3 1 4 4 2 实例: n=5, (p1,p2,p3,p4,p5)=(10, 1,15,20, 5) (d1,d2,d3,d4,d5)=( 1, 4, 3, 2, 4) J[0] J[1] J[2] J[3] J[4] J[5] 0 1 2 2 1 3 4 D[J(l)]l, r+1≤l≤k； D[J(r)]≤D[i]； D[i]r； * 算法5.4 带有限期的作业排序的贪心算法 从D(J[k])到 D(J[1])依次与D(i)比较来寻找插入位置r的过程 满足条件表示找到插入位置r 实现作业r+1到作业k依次往后移动一个位置 将作业i插入到r+1位置 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 l ← k to r+1 by –1 do J(l+1) ← J(l) repeat J(r+1) ← i ; k ← k+1； endif repeat end JS * 实例: n=5, (p1,p2,p3,p4,p5)=(10, 1,15,20, 5) (d1,d2,d3,d4,d5)=( 1, 4,