Algorithm 版 (精华区)

发信人: Lerry (戒网·学习), 信区: Algorithm
标  题: 贪心算法 
发信站: 哈工大紫丁香 (2001年11月20日21:16:31 星期二), 站内信件

贪心算法
相关知识： 一维数组 | 多维数组 | 栈 | 队列 | 串
一、算法思想
贪心法的基本思路：
——从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。
当达到某算法中的某一步不能再继续前进时，算法停止。
该算法存在问题：
1. 不能保证求得的最后解是最佳的；
2. 不能用来求最大或最小解问题；
3. 只能求满足某些约束条件的可行解的范围。
实现该算法的过程：
从问题的某一初始解出发；
while 能朝给定总目标前进一步 do
　　求出可行解的一个解元素；
由所有解元素组合成问题的一个可行解；
二、例题分析
1、[背包问题]有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。

要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。
物品 A
 B
 C
 D
 E
 F
 G
重量
 35
 30
 60
 50
 40
 10
 25
价值
 10
 40
 30
 50
 35
 40
 30
分析：
目标函数： ∑pi最大
约束条件是装入的物品总重量不超过背包容量：∑wi<=M( M=150)
（1）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？
（2）每次挑选所占空间最小的物品装入是否能得到最优解？
（3）每次选取单位容量价值最大的物品，成为解本题的策略。
源程序
2、[单源最短路径]一个有向图G，它的每条边都有一个非负的权值c[i,j]，“路径长度
”就是所经过的所有边的权值之和。对于源点需要找出从源点出发到达其他所有结点的
最短路径。
　　E.Dijkstra发明的贪婪算法可以解决最短路径问题。算法的主要思想是：分步求出
最短路径，每一步产生一个到达新目的顶点的最短路径。下一步所能达到的目的顶点通
过如下贪婪准则选取：在未产生最短路径的顶点中，选择路径最短的目的顶点。
　　设置顶点集合S并不断作贪心选择来扩充这个集合。当且仅当顶点到该顶点的最短路
径已知时该顶点属于集合S。初始时S中只含源。
　　设u为G中一顶点，我们把从源点到u且中间仅经过集合S中的顶点的路称为从源到u特
殊路径，并把这个特殊路径记录下来（例如程序中的dist[i，j]）。
　　每次从V-S选出具有最短特殊路径长度的顶点u，将u添加到S中，同时对特殊路径长
度进行必要的修改。一旦V=S，就得到从源到其他所有顶点的最短路径，也就得到问题的
解 。
Dijkstra.pas
3、[机器调度]现有N项任务和无限多台机器。任务可以在机器上处理。每件任务开始时
间和完成时间有下表：
任务 a b c d e f g
开始(si) 0 3 4 9 7 1 6
完成(fi) 2 7 7 11 10 5 8
　　在可行分配中每台机器在任何时刻最多处理一个任务。最优分配是指使用的机器最
少的可行分配方案。请就本题给出的条件，求出最优分配。
三、练习题：
已知5个城市之间有班机传递邮件，目的是为了寻找一条耗油量较少的飞行路线。5个城
市的联系网络如图所示。图中编号的结点表示城市，两个城市之间的连线上的值表示班
机沿该航线已行的耗油量，并假定从城市i到j和城市j到i之间的耗油量是相同的。
分析：
1. 运用贪心思想：
在每一步前进的选择上，选取相对当前城市耗油量最小的航线；
2. 图解：若从1出发，有图：
总耗油量=14 1-2-5-3-4-1
但若路线改为：1-5-3-4-2-1，则总耗油量=13
所以，这样的贪心法并不能得出最佳解。
3. 改善方案：
从所有城市出发的信心过程，求最优的。
编程：
1. 数据结构：
城市联系网络图的描述(图的邻接矩阵的描述)：
const
c=array[1..5,1..5] of integer=((0,1,2,7,5),
(1,0,4,4,3),
(2,4,0,1,2),
(7,4,1,0,3));
2. 贪心过程：
begin
初始化所有城市的算途径标志；
设置出发城市V；
for i:=1 to n-1 do {n-1个城市}
begin
s:=从V至所有未曾到过的城市的边集中耗油量最少的那个城市；
累加耗油量；
V:=s；
设V城市的访问标志；
end;
最后一个城市返回第一个城市，累加耗油量；
end;
3. 主过程：实现改善方案
begin
for i:=1 to n do
begin
cost1:=maxint; {初始化}
调用贪心过程，返回本次搜索耗油量cost；
if cost<cost1 then 替换；
end;
输出；
end.

--
　　不在乎天长地久，就怕你从来没有！

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]