第三章 贪心算法 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条边