贪心算法.ppt

第三章贪心算法
7/5/2018
1
计算机算法设计与分析
贪心算法的特点
贪心算法总是作出在当前来看是最好的选择。
就是说,贪心算法并不从整体最优上来考虑,所作出的选择只是某种意义上的局部最优选择。
当然希望贪心算法得到的最终结果是最优的。
可是贪心算法并不能保证最终结果是最优的。
不过,在许多的情况下,应用贪心算法能够得到整体最优解;并且在一些情况下,即使得到的不是最优解,也是一个很好的近似解。
7/5/2018
2
计算机算法设计与分析
贪心算法的一般框架
GreedyAlgorithm(parameters){
初始化;
重复执行以下的操作:
选择当前可以选择的(相容)最优解;
将所选择的当前解加入到问题的解中;
直至满足问题求解的结束条件。
}
7/5/2018
3
计算机算法设计与分析
最小生成树
设G = (V, E)是一个无向连通带权图,即一个网络。E的每条边(v, w)的权为c[v][w]。
如果G的一个子图G’是一棵包含G的所有顶点的树,则称G’为G的生成树。
生成树的各边的权的总和称为该生成树的耗费。
在G的所有生成树中,耗费最小的生成树称为G的最小(优)生成树。
7/5/2018
4
计算机算法设计与分析
树的基本性质
连通无回路的图G称为树。
树是点比边多一的连通图,G连通且q=p–1 。
树是点比边多一的无回路图:G无回路且q=p–1。
树若添条边就有回路:G无回路,但对任意的u, v∈V(G),若uvE(G),则G+uv中恰有一条回路。
树若减条边就不连通:G连通,但对e∈E(G), G–e不连通。
n个顶点的连通图的生成树含有n – 1条边。
7/5/2018
5
计算机算法设计与分析
最小生成树的贪心选择性质
令G中权最小的边为e1。首先必定有图G的一棵最小生成树包含了e1。
若G的任何最小生成树都不包含e1。设T为G的最小生成树,e1T。于是T+e1是一个有回路的图且该回路中包含e1。该回路中必有条不是e的边ei。令T’={T+e1}–ei。T’也是G的生成树。又c(T’) = c(T) + c(e1) – c(e1),c(e1) ≤ c(ei),从而 c(T’)≤c(T),T’是G的最小生成树且含有边e1。矛盾。故必定有图G的最小生成树包含了e1。
选定第一条边e1以后,该如何选择第二条边呢?
依据各条边的权重,依次选出权重较轻的n – 1条边。这n – 1条边必定包括了G的n个顶点。这样就得到了G的一棵最小生成树。
这样做是否可以呢?
不行!因为不能保证这n – 1条边构成树?
要保证这n – 1条边构成树,必须使这n – 1条边是连通的或者是无回路的。
Prim算法的做法:在保证连通的前提下依次选出权重较小的n – 1条边(在实现中体现为n个顶点的选择)。
Kruskal算法的做法:在保证无回路的前提下依次选择权重较小的n – 1条边。
7/5/2018
6
计算机算法设计与分析
Prim算法
基本思想:在保证连通的前提下依次选出权重较小的n – 1条边。
G=(V, E)为无向连通带权图,令V={1, 2, …, n}。
设置一个集合S ,初始化S = {1},T = Φ。
贪心策略:如果V–S中的顶点j与S中的某个点i连接且(i, j)是E中的权重最小的边,于是就选择j(将j加入S),并将(i, j) 加入T中。
重复执行贪心策略,直至V–S为空。
7/5/2018
7
计算机算法设计与分析
Prim算法中的数据结构
图用连接矩阵C[i][j]给出,即C[i][j]为结点i到结点j的权重。
为了有效地找出V–S中满足与S中的某个点i连接且(i, j) 权重最小的顶点j,对其中的每个顶点j设立两个数组closest[j]和lowcost[j]:
closest[j]是s中与j最近的顶点,(closest[j], j)即为选中的边,而lowcost[j]是相应边的权重。
7/5/2018
8
计算机算法设计与分析
Prim算法的实现
Prim(int n, Type **c) {
初始化:结点1放入S;并初始化lowcost[]和
closest[];
执行以下操作n–1次:
依据lowcost[]找出与S最近的点j并放入S;

调整lowcost[]和closest[];}
int j = 1; s[j] = true;
for (int i = 2; i <= n; i++) {
closest[i] = 1; lowcost[i]=c[1][i]; s[i]=false;}
for (int i = 1; i < n; i++) {min= in