Lecture 11 贪心算法的理论基础-拟阵.ppt

* * * * * * * * * * * * * * * * * * * * * * * * 4.8 贪心算法的理论基础 由【定理4.5】可知，用带权拟阵的贪心算法可以求得最大权(惩罚)独立（及时）任务子集A，以A作为最优时间表中的及时任务子集，即可构造出最优时间表。 * 第三十一页，编辑于星期二：十七点 四十分。 4.8 贪心算法的理论基础 Algorithm Set Greedy-Job (M,W) // 拟阵 M=(S,I) { A=?; 将S中的任务按照惩罚权值W排成非递增序； while (S!=?) { S.removeMax(x); if (A∪{x}?I) A=A∪{x}; } return A } * 第三十二页，编辑于星期二：十七点 四十分。 4.8 贪心算法的理论基础 计算时间复杂性是 。其中f(n)是用于检测任务子集A的独立性所需的时间。用【引理4.6】中的性质(2)容易设计一个 时间算法来检测任务子集的独立性。因此，整个算法的计算时间为 。 greedyJob算法的具体描述P139。 * 第三十三页，编辑于星期二：十七点 四十分。 4.8 贪心算法的理论基础 算法改进 用抽象数据类型并查集UnionFind可对上述算法作进一步改进。加上对权的排序工作量后,改进后的算法fasterJob所需的计算时间为 。 * 第三十四页，编辑于星期二：十七点 四十分。 4.8 贪心算法的理论基础 【引理】设T（m,n）是处理m次FIND和n-1次UNION的混合序列所要求的最坏情况时间(m≥n)，则对于某两个正常数K1和K2有 K1 m α(m,n)≤T(m,n)≤ K2 m α(m,n) 由于阿克曼函数的逆函数α(m,n)是一个增长非常缓慢的函数(理论上没有上界，但在实际应用中，对通常的m、n总有α(m,n)≤3)，所以在忽略K1和K2常数情况下，UNION-FIND序列的时间复杂度几乎与FIND的次数m成线性关系。 * 第三十五页，编辑于星期二：十七点 四十分。 计算时间为 的算法 基本思路：尽可能推迟对作业i的处理。 如果还没有给作业i分配处理时间，则分配给它时间片[α-1, α]，其中α应尽量取大且时间片[α- 1，α]是空的。 * 第三十六页，编辑于星期二：十七点 四十分。 例1： 设n=5,(p1,…p5)=(20,15,10,5,1) (d1…d5)＝(2,2,1,3,3)。 使用上述规则，得最优解是J={1,2,4} J 已分配的时间片 正处理作业 动作 Ф 无 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) //D为期限数组、n作业数、b最大期限、J解向量、k作业个数 1?????????????? integer b,D(n),J(n),F(0:b),P(0:b) 2?????????????? for i←0 to n do 3?????????????? F(i)←i；P(i)←-1 4?????????????? end-for 5?????????????? k←0 6?????????????? for i←1 to n do 7?????????????? j←FIND(min(n,D(i))) 8?????????????? if F(j)≠0 then k←k+1；J(k)←i 9?????????????? L←FIND(F(j)-1)；UNION(L,j) 10?????????? F(j)←F(L) 11?????????? endif 12?????????? end-for 13?????????? end FJS For循环中含n次查找和小于n次的合并,总时间与n近似成线性关系 * 第三十八页，编辑于星期二：十七点 四十分。 算法 procedure FIND(i) //查找含有元素i的树根，使用压缩规则压缩由i到根j的所有结点 1???j=i 2???while PARENT(j)0 do //找根 3??? ?j =PARENT(j)? 4????r