文档介绍：第2章贪婪法
第1页，共31页，编辑于2022年，星期五
贪婪法设计思想
贪婪法（Greedy algorithms）设计思想
贪婪法常用来解决最优化问题。犹如登山一样，一步一步向前推进。
从某个初始点出发，根据当前局前物品是否超重
// 当前物品完整的装入背包即xi = 1
// 背包当前承重量减小
// 当前放入物品的价值记入总价值
// 当前物品超重，放入一部分，装满背包
问：当前物品超重时，为什么不取后面的物品，
而是取当前物品的一部分装入背包？
第6页，共31页，编辑于2022年，星期五
有限期的计算机作业调度
给定n个作业j1,j2,…,jn。对于每一个作业ji，有一个与联系的限期di>0和收益p≥0，di，pi 均为整数，1≤i≤n。对于作业ji，只有在限期di内完成，才能得到收益pi。
假定只有一台处理机为这批作业服务，处理机每次只能处理一个作业，并且完成任一作业需一个单位时间。
可行解：这批作业的一个子集J，且J中每一作业均能在限期内完成，调度的总收益是该子集J中各作业收益的和。
最优解：具有最大收益的可行解称为最优解。
第7页，共31页，编辑于2022年，星期五
本问题的目标函数∑pi可以作为最优测度。根据这个测度使用贪婪法时，对任一局部最优解J，若{j1,j2,…,jn}-J中有若干作业可以分别加入J中成为可行解时，选择其中收益最大的一个添加到J中，作为新的局部最优解。这就表明应当按pi的递减序来选择下一个合适的作业加入J中。
现在的问题是，设子集J中已 k-1个作业ji1,ji2,…,jik-1,它们都能在各自的限期内完成，加入下一个作业jik后，如何判定它们是不是构成一个可行解呢？一种方法是分别测 试这k个作业的所有可能排序，对k!种排列，只要有一种排列方法可以使作业在各自限期内完成，它就是一个可行解。但这样做可能付出太大的代价，在最坏情况下，它要测试k!次。
第8页，共31页，编辑于2022年，星期五
下面的方法将使求解过程简化。
对于子集J中的作业，按时序的非递减顺序排列，使得dI1≤dI2≤…≤dik，然后测试dij，只要dij≥j，J一定是可行解。
有限期的作业调度算法。
输入：按p1≥p2≥…≥pn的顺序输入D[1],D[2], …,D[n]，其中D[i]为第i个作业的限期，pi为相应的收益。D[i] ≥1,1≤i≤n。
输出：J[1…k]，J[i]是最优解中的第i个作业，且满足D[J[i]] ≤D[J[i+1]], 1≤i≤n。
。-。
第9页，共31页，编辑于2022年，星期五
Procdure JS(D,J,n,k);
Begin
D[0]←0;J[0] ←0;/初始化/
k←1;J[1] ←1;/计入作业/
for i←2 to n do
/按P的非增序考虑作业，找i的位置，并检查插入的可能性/
Begin
r←k;
while D[J[r]]>D[i] and D[J[r]]<>r do
r←r-1;
if D[J[r]]<=D[i] and D[J[r]]>r then /把i插入到J中/
begin
for l←k step -1 until r+1 do
J[l+1] ←J[l];
J[r+1] ←i;
k←k+1;
End;
End;
Endp;
第10页，共31页，编辑于2022年，星期五
最小生成树(MST)问题
最小生成树 (MST) 问题 Minimum Spanning Tree
生成树：包含连通图全部顶点的连通无环子图（树），或称支撑树。
最小生成树：带权连通图的一棵权重最小的生成树。
树的权重：所有边的权重总和。
最小生成树问题：求带权连通图的最小生成树的问题。
应用举例：建造城市间交通道路网或者通信线路网的花费最低。
生成树、最小生成树图例：
A
D
C
B
1
2
3
5
A
D
C
B
1
2
3
有环连通图 w(T1)=6 w(T2)=9 w(T3)=8
T1 是该图的最小生成树MST
A
D
C
B
1
3
5
A
D
C
B
1
2
5
第11页，共31页，编辑