第九章 贪心法.ppt

第九章贪心法
贪心法基本思想
逐步给出解的各部分,
在每一步“贪婪地”选择最好的部分解,但不顾及这样选择对整体的影响,
因此一般地得到的不是最好的解。
但对许多问题它能产生整体最优解。
如单源最短路经问题,最小生成树问题等。
在一些情况下,即使贪心算法不能得到整体最优解,其最终结果却是最优解的很好近似。
Prim算法
贪心法的特点
kruskal算法
Dijkstra算法

Prim算法
设G =(V,E)是无向连通带权图。
E中每条边(v,w)的权重为c[v][w]。
如果G的子图G’是一棵包含G的所有顶点的树,则称G’为G的生成树。
在G的所有生成树中,所有边的权重总和最小的生成树称为G的最小生成树。
图的最小生成树在实际中有广泛应用。
例如,在设计通信网络时,用图的顶点表示城市,用边(v,w)的权c[v][w]表示建立城市v和城市w之间的通信线路所需的费用,则最小生成树就给出了建立通信网络的最经济的方案。
Prim基本思想
设G=(V,E)是连通带权图,V={1,2,…,n}。
首先置S={1}
然后,只要S是V的真子集,就作如下的贪心选择:
选取满足条件iS,jV-S,且c[i][j]最小的边
将顶点j添加到S中。
这个过程一直进行到S=V时为止。
在这个过程中选取到的所有边恰好构成G的一棵最小生成树。
如何有效地找出满足条件iS,jV-S,且权c[i][j]最小的边(i,j)
对每个不在当前树中的顶点,附加两个标记:
(树中最近顶点的名称,相应边的权重)
求出距离标记最小的点
当确定了一个加入树中的顶点u*后
把u*从集合V-S移到树的顶点集合S
更新V-S中各顶点的标记
Prim算法是否总能产生一棵最小生成树?
用数学归纳法证明:
用Ti i=1,……,n表示Prim算法过程中生成的每一棵子树
T1,显然是最小生成树的一部分
设Tk-1 是最小生成树T的一部分
证明通过Prim算法从Tk-1 生成的Tk也是一棵最小生成树的一部分
反证法:
设没有一棵最小生成树包含Tk ,用T表示最小生成树
则有ek=(v,u)权重最小,v属于Tk-1 ,u不属于Tk-1
使Tk-1扩展到Tk
因为ek不属于T
如果把ek加入T中,会形成回路。(为什么?)
该回路必定包含另一边(x,y), x属于Tk-1 ,y不属于Tk-1 。(为什么?)
如果删除该边得到另一棵生成树,权重小于等于T。(为什么?)
和假设矛盾。