一、算法思想
贪心法的基本思路:
——从问题的某一个初始解出发逐步逼近给定的目标,以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时,算法停止。
该算法存在问题:
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,就得到从源到其他所有顶点的最短路径,也就得到问题的解 。
stra.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.eed.pas
五年级上册解方程练… | 255457 |
九连环图解解法 | 226893 |
wifi万能钥匙破解的… | 177863 |
纸飞机Skyking(空… | 170844 |
小学语文知识大全(… | 152076 |
各种鱼钩鱼线绑法与… | 117014 |
课题研究的方法有哪些 | 113473 |
人教版pep小学英语… | 104571 |
小学语文知识大全(… | 96818 |
人教版pep小学英语… | 96209 |
小学数学五年级上册… | 93451 |
人教版pep小学英语… | 82587 |
小学语文知识大全(… | 80413 |
笔记本电脑如何关闭… | 79825 |
小学生六一搞笑小品… | 78892 |
不打结的红领巾系法… | 78083 |