第六章贪心法.ppt

6.3 带有限期的作业排序 6.3.4 可行性判定---(2)如何变为有效算法? 定理6-3 X=(x0,x1,…xk)是k个作业的集合,a=(a0,a1,a2…ak)是X的一种特定排列,它使得da0=da1=….dak,其中，daj是作业aj的时限.X是一个可行解当且仅当X中的作业能够按a次序调度而不会有作业超期. 证明:(1)”?”如果X中作业能够按照a次序调度而不会有作业超期, 则X是可行解. (2)”-”如果X是可行解，则必存在X的至少一种排列使得X中作业可以按该排列执行而不会有超期，设β=(β0,β1,…βk),β≠α 是这样的排列. 令i是使得αi≠βi的最小下标，那么作业αi的时限必然小于βi的时限, 由于α和β是X中作业的两种不同的排列, 所以β中必定也包含作业αi,很显然, αi在β中的位置比它在α中的位置靠后. 将β中的αi与βi交换位置, 不会引起作业超期. 重复以上过程, 最终将β变换成α,这就是说,按α次序调度作业不会出现超期, 因此α是可行的调度方案 第二十九页，共四十八页，2022年，8月28日 带时限的且每个作业运行单位时间的作业排序过程: (1),按收益非增次序对作业排序:p0≥p1≥…pn-1; (2),按作业收益从大到小考察作业; 初始时,x[0]=0,即X={x[0]}; 现在处理作业j,假设已处理了I-1个作业,其中有k+1个作业已计入部分解向量X={x[0],x[1]…x[k]}之中,且有d[x[0]]≤d[x[1]]≤…≤d[x[k]]。 ∵部分解可行 ∴d[x[i]]≥i+1(0≤i≤k) 为了判断XU{j}是否可行,只需看能否找出按期限的非降次序插入作业j的适当位置r,使得作业j在此处插入后有d[X[r]]≥r+1,0≤r≤k. 6.3 带有限期的作业排序 6.3.5 作业排序算法 ……… ……… k j 第三十页，共四十八页，2022年，8月28日 (3)判断j是否允许添加到部分解向量X中 将作业j按时限的非减次序插入向量X={x[0],x[1]…x[k]}中的某个位置，使得作业j插入后，由k+2个分量组成的部分解向量仍按时限的非减次序排列 假设j被插入于下标r+1处,为了在r+1处插入j作业， x[r+1]…x[k]在向量中的位置都要依次后移一位，形成一个新的部分解向量. 为了保证在添加作业j后的作业子集仍构成可行解，必须满足: a, d[x[j]]j+1(r+1≤j≤k) b, d[j]r+1; 6.3 带有限期的作业排序 6.3.5 作业排序算法 第三十一页，共四十八页，2022年，8月28日 【程序6-4】 带时限的作业排序程序 int JS(int *d, int *x, int n) { //设p0≥p1≥…≥pn?1 int k=0; x[0]=0; for (int j=1; jn; j++) { int r=k; while (r=0 d[x[r]]d[j] d[x[r]]r+1) r--; if((r0 || d[x[r]]=d[j]) d[j]r+1) { for (int i=k; i=r+1; i--) x[i+1]=x[i]; x[r+1]=j; k++; } } return k; } 6.3 带有限期的作业排序 6.3.5 作业排序算法 n-1 //O(n) k+1 k-r 每次迭代的总时间为O(k),若s是k的终值,即s是最后所得解的作业数.则JS所需的总时间是O(sn).由于s=n,因此最坏时间是O(n2)(当di=n-i 0≤i≤n-1时),所以最坏时间是: O(n2) 复杂度分析：对于JS，其复杂度参数有两个：即作业数n和包含在解中的作业数s. 第三十二页，共四十八页，2022年，8月28日 例n=4，P＝(100，20， 15， 10，)和d=(2,1,2,1) 0 1. X[0]