gusucode.com > 十大算法matlab程序说明 > 十大算法matlab程序说明/贪婪算法/贪心算法.txt
贪心算法一、算法思想 贪心法的基本思路: ——从问题的某一个初始解出发逐步逼近给定的目标,以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时,算法停止。 该算法存在问题: 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; 输出;