贪心算法 - 贪心算法83064584.ppt

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