第7章_贪心算法
2016/6/28
Chapter 7 Greedy Method
4
7.1.1 贪心法的设计思想
什么是贪心算法?
贪心法目光短浅,只根据当前已有的信息做出选择,而 且一旦做出了选择,不管将来有什么结果,这个选择都 不会改变。 贪心算法总是作出在当前看来最好的选择。也就是说贪 心算法并不从整体最优考虑,它所作出的选择只是在某 种意义上的局部最优选择。虽然贪心算法不能对所有问 题都得到整体最优解,但对许多问题它能产生整体最优 解。在一些情况下,即使贪心算法不能得到整体最优解, 其最终结果却是最优解的很好近似。
2016/6/28 Chapter 7 Greedy Method 13
第7章 贪心算法
7.1 概 述
7.2 图问题中的贪心法
7.3 组合问题中的贪心法
阅读材料——贪心法的正确性证明
2016/6/28
Chapter 7 Greedy Method
14
7.2 图问题中的贪心法
7.2.1 TSP问题 7.2.2 图着色问题
Chapter 7 Greedy Method 16
2016/6/28
C=
∞ 3 3 2 6
3 3 2 6 ∞ 7 3 2 7 ∞ 2 5 3 2 ∞ 3 2 5 3 ∞
6 5
1
7.2.1 TSP问题
3 1 2 5 3 2 3 4 3 2
2
4
3
3
(a) 5城市的代价矩阵 1 5 2 5
(b) 城市1→城市4 1
求解:
选出1 张面值 <=4 元 6 角的最大面值的货币,即2 元; 选出1 张面值 <=2 元 6 角的最大面值的货币,即2 元; 选出1 张面值 <=6 角的最大面值的货币,即 5 角; 选出1 张面值 <=1 角的最大面值的货币,即 1 角; 总共付出 4 张货币。
2016/6/28 Chapter 8 Greedy Method 6
2016/6/28 Chapter 7 Greedy Method 8
7.1.1 贪心法的设计思想
与动态规划法的关系
动态规划法把一个复杂问题分解为若干相互重叠的子 问题,通过求解子问题形成的一系列决策得到原问题 的解; 贪心法把一个复杂问题分解为一系列较为简单的局部 最优选择,每一步选择都是对当前解的一个扩展,直 到获得问题的完整解; 动态规划法以自底向上的方式求解各个子问题,而贪 心法则通常以自顶向下的方式做出一系列的贪心选择。
5
4
2
3
(a) 5城市的代价矩阵
(b) 城市1→城市4 1
3 4 (c) 城市5→城市2 1 2 3 2 2
2
2
5 4
5 3 3 2 (f) 城市2回到出发城市1
4
2
4
2
(d) 城市4→城市3
(e) 城市3→城市5
最短链接贪心策略求解TSP问题的过程
2016/6/28 Chapter 7 Greedy Method 18
2016/6/28
2 (c) 城市4→城市3
1 2 5
2 7
3
5
5 4 2
2
2
5
2
3 2
4
2
3
4
2
3
(d) 城市3→城市5
(e) 城市5→城市2
(f) 城市2→城市1
最近邻点贪心策略求解TSP问题的过程
2016/6/28 Chapter 7 Greedy Method 17
7.2.1 TSP问题
C= ∞ 3 3 ∞ 3 7 2 3 6 2 3 7 ∞ 2 5 1 5 2 2 2 3 5 2 5 2 3 2 ∞ 3 6 2 5 3 ∞ 1 1 2 5 2 2 2
增加,这正体现了贪心法的设计思想。
2016/6/28
Chapter 7 Greedy Method
7
7.1.1 贪心法的设计思想
例:求解付款找零问题的贪心法 设货币面值为:3元、1元、8角、5角、1角 找零为:4.6元 求解: 选出1 张面值 <=4 元 6 角的最大面值的货币,即3 元; 选出1 张面值 <=1 元 6 角的最大面值的货币,即1 元; 选出1 张面值 <=6 角的最大面值的货币,即 5 角; 选出1 张面值 <=1 角的最大面值的货币,即 1 角; 总共付出 4 张货币(3元、1元、5角、1角) 但最优解:3张货币(3元、8角、8角) 如果一个问题的最优解只能用蛮力法得到,贪心法不失为 寻找近似解的一个较好方法
2016/6/28
Chapter 7 Greedy Method
9
7.1.2 一个简单的例子——埃及分数
[问题]古埃及人只用分子为1的分数,在表示一个真分数时, 将其分解为若干个埃及分数之和,如7/8表示为 1/2+1/3+1/24。怎么将一个真分数表示为最少的埃及 分数之和的形式? [想法]一个真分数的埃及分数表示不是唯一的,将一个真 分数表示为最少埃及分数之和的形式,其贪心策略是选择 真分数包含的最大埃及分数。如7/8为例,7/8>1/2,则 1/2是第一次贪心选择的结果;7/8-1/2=3/8>1/3,则 1/3是第二次贪心选择的结果;3/8-1/3=1/24,则1/24 是第三次贪心选择的结果。7/8=1/2+1/3+1/24
2016/6/28
Chapter 7 Greedy Method
22
7.2.1 TSP问题
设图G 有n 个顶点, w[n][n] 存储边上的代价,集合E‘存 储是候选集合中未选取的边,集合P 存储经过的边,最短链接 策略求解TSP 问题的算法如下:
算法7.3——最短链接策略求解TSP问题 1.P={ }; 2.E'=E; //候选集合,初始时为图中所有边 3.循环直到集合P中包含n-1条边 3.1 在E'中选取最短边(u, v); 3.2 E'=E'-{(u, v)}; 3.3 如果 (顶点 u 和v 在 P 中不连通 and 不产生分枝) 则P=P+{(u, v)};
2016/6/28
Chapter 7 Greedy Method
10
7.1.2 一个简单的例子——埃及分数
设真分数为A/B,B除以A的整数部分为C,余数为D,则: B=A*C+D (D<A) 即 B/A=C+D/A<C+1
则 A/B>1/(C+1)
即1/(C+1)即为真分数A/B包含的最大埃及分数。设E=C+1,
7.2.1 TSP问题
[算法1]设图G 有 n 个顶点,边上的代价存储在二维数组 w[n][n]中,集合V 存储图的顶点,集合 P 存储经过的边,最 近邻点策略求解 TSP 问题的算法如下:
算法 7.2——最近邻点 策略求解 TSP 问题
1. P={ };
//对应解集合S
2. V=V-{u0}; u=u0; //从顶点u0 出发 3. 循环直到集合P 中包含 n-1 条边 3.1 找与顶点 u 邻接的最小代价边(u, v), 并且v属于集合V; 3.2 P=P+{(u, v)}; 3.3 V=V-{v}; 3.4 u=v; //从顶点v出发继续求解
2016/6/28
Chapter 7 Greedy Method
12
7.1.2 一个简单的例子——埃及分数
void EgyptFraction(int A, int B) { int E,R; cout<<A<<“/”<<B<<“=”; do{ E=B/A+1; cout<<“1/”<<E<<“+”; A=A*E-B; B=B*E; R=CommFractor(B,A); //CommFractor为求最大公约数函数 if( R>1 ){ A=A/R; B=B/R; } }while( A>1); cout<<“1/”<<B<<endl; return; }
125431 代价:13
2016/6/28
Chapter 7 Greedy Method
20
7.2.1 TSP问题
当图中顶点个数较多并且各边的代价值分布比较均匀时, 最近邻点策略可以给出较好的近似解,不过,这个近似 解以何种程度近似于最优解,却难以保证。
例如,在图7.1中,如果增大边(2, 1)的代价,则总 代价只好随之增加,没有选择的余地。
由于
A/B-1/E=((A*E)-B)/(B*E)
这个分数可能存在公因子,所以需要化简,可将分子和分母同 时除以最大公约数。
2016/6/28 Chapter 7 Greedy Method 11
7.1.2 一个简单的例子——埃及分数
[算法]伪代码描述如下: 算法7.1:埃及分数EgyptFraction 输入:真分数的分子A和分母B 输出:最少的埃及分数之和 1. E=B/A+1; //E=C+1 2. 输出1/E; 3. A=A*E-B; B=B*E; 4. 求A和B的最大公约数R,如果R不为1,将A和B同时除以R 5. 如果A等于1,则输出1/B,算法结束;否则转步骤1
2016/6/28
Chapter 7 Greedy Method
19
7.2.1 TSP问题
算法分析1
时间复杂度
算法7.2的时间性能为O(n2),因为共进行n-1次贪心选择, 每一次选择都需要查找满足贪心条件的最短边。