算法贪心.ppt

问题3最小生成树 设G = (V, E)是一个无向连通带权图，即一个网络。E的每条边(v, w)的权为c[v][w]。 如果G的一个子图G’是一棵包含G的所有顶点的树，则称G’为G的生成树。 生成树的各边的权的总和称为该生成树的耗费。 在G的所有生成树中，耗费最小的生成树称为G的最小生成树。 树的基本性质 连通无回路的图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条边。 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为空。 Prim算法示例 给定一个连通带权图如下： 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]是相应边的权重。 Kruskal算法 基本思想：在保证无回路的前提下依次选出权重较小的n – 1条边。 贪心策略：如果(i, j)是E中尚未被选中的边中权重最小的，并且(i, j)不会与已经选择的边构成回路，于是就选择 (i, j)。 Kruskal算法的例子 Kruskal算法的数据结构 数组e[][]表示图的边，e[i][u]、e[i][v]和e[i][w]分别表示边i的两个端点及其权重。 函数Sort(e, w)将数组e按权重w从小到大排序。 一个连通分支中的顶点表示为一个集合。 函数Initialize(n)将每个顶点初始化为一个集合。 函数Find(u)给出顶点u所在的集合。 函数Union(a, b)给出集合a和集合b的并集。 重载算符!=判断集合的不相等。 Kruskal算法的实现 Kruskal(int n, **e) { Sort(e, w); //将边按权重从小到大排序 initialize(n); //初始时每个顶点为一个集合 k = 1; //k累计已选边的数目， j = 1; //j为所选的边在e中的序号 while (k n) //选择n – 1条边 {a = Find(e[j][u]); b = Find(e[j][v]); //找出第j条边两个端点所在的集合 if (a != b) {t[k++] = j; Union(a, b)} //若不同，第j条边放入树中并合并这两个集合 j++ }} //继续考察下一条边 破圈算法的例子 归并模式的概念 给出n个文件，则由许多种把这些文件成对地归并成一个单一分类文件的方法。 不同的配对方法要求不同的计算时间 问题的关键是：确定一个把n个已分类文件归并在一起的最优方法（即需要最少的比较次数的方法） 例 ：X1，X2和X3是各自有30个记录、20个记录和10个记录的三个已分类文件，归并X1和X2需要50次记录移动，再与X3归并则还要60次移动，其所需要的记录移动次数总量为110。 如果首先归并X2和X3，需要30次移动，然后再归并X1，需要60次移动，则所要移动记录的总量为90。 因此，第二个归并模式比第一个要好。 最优归并模式的实现 由于归并一个具有n个记录的文件和一个具有m个记录的文件可能需要m+n次记录移动，因此对于量度标准的一种很明显的贪心选择是：每一步都归并尺寸最小的两个文件 例如有五个文件长度分别是(F1,…,F5)=(20,30,10,5,30) 二路归并模式 此种归并模式称为二路归并模式。二路归并模式可以用二元归并树来表示。 二元归并树中叶结点被画成方块，表示五个已知的文件。这些结点称为外部结点。 最优归并模式的实现 带权外部路径长度 如果di表示从根到代表文件Fi的外部节点的距离，qi表示Fi的长度，则这棵二元归并树的记录移动总量是： ∑diqi 这个和数叫做这棵树的带权外部路径长度 一个最优二路归并模式与