第三章 贪心算法 2021-2-21 计算机算法设计与分析
2021-2-21 计算机算法设计与分析 1 第三章 贪心算法
贪心算法的特点 ■贪心算法总是作出在当前来看是最好的选择。 ■就是说,贪心算法并不从整体最优上来考虑, 所作出的选择只是某种意义上的局部最优选择 ■当然希望贪心算法得到的最终结果是最优的。 ■可是贪心算法并不能保证最终结果是最优的。 ■不过,在许多的情况下,应用贪心算法能够得 到整体最优解;并且在一些情况下,即使得到 的不是最优解,也是一个很好的近似解。 20212-21 计算机算法设计与分析
2021-2-21 计算机算法设计与分析 2 贪心算法的特点 n 贪心算法总是作出在当前来看是最好的选择。 n 就是说，贪心算法并不从整体最优上来考虑， 所作出的选择只是某种意义上的局部最优选择。 n 当然希望贪心算法得到的最终结果是最优的。 n 可是贪心算法并不能保证最终结果是最优的。 n 不过，在许多的情况下，应用贪心算法能够得 到整体最优解；并且在一些情况下，即使得到 的不是最优解，也是一个很好的近似解
贪心算法的一般框架 a Greedy algorithm(parameters)i ■初始化; ■重复执行以下的操作 选择当前可以选择的(相容)最优解: 将所选择的当前解加入到问题的解中 直至满足问题求解的结束条件。 2021-2-21 计算机算法设计与分析
2021-2-21 计算机算法设计与分析 3 贪心算法的一般框架 n GreedyAlgorithm(parameters){ n 初始化； n 重复执行以下的操作： n 选择当前可以选择的(相容)最优解； n 将所选择的当前解加入到问题的解中； n 直至满足问题求解的结束条件。 n }
最小生成树 设G=(V,E)是一个无向连通带权图,即一个网 络。E的每条边(v,w)的权为cv]w ■如果G的一个子图G是一棵包含G的所有顶点 的树,则称G为G的生成树 ■生成树的各边的权的总和称为该生成树的耗费。 ■在G的所有生成树中,耗费最小的生成树称为 G的最小(优)生成树 20212-21 计算机算法设计与分析
2021-2-21 计算机算法设计与分析 4 最小生成树 n 设G = (V, E)是一个无向连通带权图，即一个网 络。E的每条边(v, w)的权为c[v][w]。 n 如果G的一个子图G’是一棵包含G的所有顶点 的树，则称G’为G的生成树。 n 生成树的各边的权的总和称为该生成树的耗费。 n 在G的所有生成树中，耗费最小的生成树称为 G的最小(优)生成树
树的基本性质 ■连通无回路的图G称为树。 ■树是点比边多一的连通图,G连通且q=p ■树是点比边多一的无回路图:G无回路且q=p-1。 ■树若添条边就有回路:G无回路,但对任意的u v∈V(G,若uvEE(G),则G+uv中恰有一条回路 树若减条边就不连通:G连通,但对∨e∈E(G), Ge不连通。 ■n个顶点的连通图的生成树含有n-1条边。 2021-2-21 计算机算法设计与分析 5
2021-2-21 计算机算法设计与分析 5 树的基本性质 n 连通无回路的图G称为树。 n 树是点比边多一的连通图，G连通且q=p–1 。 n 树是点比边多一的无回路图：G无回路且q=p–1。 n 树若添条边就有回路：G无回路，但对任意的u, v∈V(G)，若uvE(G)，则G+uv中恰有一条回路。 n 树若减条边就不连通：G连通，但对e∈E(G), G–e不连通。 n n个顶点的连通图的生成树含有n – 1条边
最小生成树的贪心选择性质 令G中权最小的边为e1。首先必定有图G的一棵 最小生成树包含了e1。 ˉ糍毹何住城树報有饉怿策条边幌? Pim算法的做法:在保证连通的前提下依次选 出权重较小的n-1条边(在实现中体现为n个 顶点的选择) Kruskal算法的做法:在保证无回路的前提下依 次选择权重较小的n-1条边。 2021-2-21 计算机算法设计与分析
2021-2-21 计算机算法设计与分析 6 最小生成树的贪心选择性质 n 令G中权最小的边为e1。首先必定有图G的一棵 最小生成树包含了e1。 若G的任何最小生成树都不包含e1。设T为G的 最小生成树，e1T。于是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。 n 选定第一条边e1以后，该如何选择第二条边呢？ n 依据各条边的权重，依次选出权重较轻的n – 1 条边。这n – 1条边必定包括了G的n个顶点。这 样就得到了G的一棵最小生成树。 n 不要这行保样！证做因这是为n否–不1可能条以保边证构呢这成？n树–，1条必边须构使成这树n –？1条边 是连通的或者是无回路的。 n Prim算法的做法：在保证连通的前提下依次选 出权重较小的n – 1条边（在实现中体现为n个 顶点的选择）。 n Kruskal算法的做法：在保证无回路的前提下依 次选择权重较小的n – 1条边
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为空。 20212-21 计算机算法设计与分析
2021-2-21 计算机算法设计与分析 7 Prim算法 n 基本思想：在保证连通的前提下依次选出权重 较小的n – 1条边。 n G=(V, E)为无向连通带权图，令V={1, 2, …, n}。 n 设置一个集合S ，初始化S = {1}，T = Φ。 n 贪心策略：如果V–S中的顶点j与S中的某个点i 连接且(i, j)是E中的权重最小的边，于是就选择 j(将j加入S)，并将(i, j) 加入T中 。 n 重复执行贪心策略，直至V–S为空
Prim算法中的数据结构 图用连接矩阵C[给出,即C[]i为结点i到 结点的权重。 为了有效地找出V-S中满足与S中的某个点i连 接且Gj)权重最小的顶点j,对其中的每个顶点 j设立两个数组 closest和 lowcostliI closest[il是s中与最近的顶点,( closest[il,j)即 为选中的边,而 lowcost是相应边的权重。 20212-21 计算机算法设计与分析
2021-2-21 计算机算法设计与分析 8 Prim算法中的数据结构 n 图用连接矩阵C[i][j]给出，即C[i][j]为结点i到 结点j的权重。 n 为了有效地找出V–S中满足与S中的某个点i连 接且(i, j) 权重最小的顶点j，对其中的每个顶点 j设立两个数组closest[j]和lowcost[j]： n closest[j]是s中与j最近的顶点，(closest[j], j)即 为选中的边，而lowcost[j]是相应边的权重
Prim算法的实现 Prim(int n, Type **c)i intj=l; slil=true for (int 1=2; i<=n;1++)i closest=1; lowcost[=cli]; si=false; for(int i=1; i<n; 1++)min= inf for (int k=2 k<=n; k++i if (lowcost[k]min&&!s[k]) imin=lowcost];j=k) sLI=true; for (int k=2; k k++){ if (clink] lowcost[ k]&&Iskd lowcost[k]=cllk]; closest[k]=j)) 20212-21 计算机算法设计与分析
2021-2-21 计算机算法设计与分析 9 Prim算法的实现 n 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= inf; for (int k = 2; k <= n; k++) { if (lowcost[k]<min&&!s[k]) {min = lowcost[k]; j = k} s[j] = true; s中仅加入了一个新成员j，因此只需要 依据结点j调整lowcost[]和closest[]； for (int k = 2; k <= n; k++) { if (c[j][k]< lowcost[k]&&!s[k]) {lowcost[k] = c[j][k]; closest[k] = j}}}
Prim算法的示例 给定一个连通带权图如下 初始时S={1},T=Φ; 第五次选择: ④∵(5,2)权最小 S={1,3,6,4,2,5}, T={(1,3),(3,6),(6,4 (3,2)(2,5)} 2021-2-21 计算机算法设计与分析 10
2021-2-21 计算机算法设计与分析 10 Prim算法的示例 n 给定一个连通带权图如下： 1 2 3 4 5 6 1 6 5 5 5 3 6 6 4 2 n 初始时S={1}，T= Φ； 1 n 第一次选择： ∵(1, 3)权最小 ∴ S={1, 3} T= {(1, 3)} ； 3 n 第二次选择： ∵(3, 6)权最小 ∴ S={1, 3, 6}， 6 T= {(1, 3), (3, 6)} ； n 第三次选择： ∵(6, 4)权最小 ∴ S={1, 3, 6, 4}， T= {(1, 3), (3, 6), (6, 4)} ； 4 n 第四次选择： ∵(2, 3)权最小 ∴ S={1, 3, 6, 4, 2}， T= {(1, 3), (3, 6), (6, 4), (2, 3)} ； 2 n 第五次选择： ∵(5, 2)权最小 ∴ S={1, 3, 6, 4, 2, 5}， T= {(1, 3), (3, 6), (6, 4), (3, 2) (2, 5)} ； 5