05+貪心算法.ppt

第5章 贪心算法;考核方式调整;Content;小样例：背包问题;贪心算法思路;贪心算法; yi = si / vi, i = 1, 2, 3, …, n;void Knapsack(int n, int M, int V[], int S[], int X[], f Y[]){ Sort(n, V, S, Y); //将各种物品按单位体积价值排序 int i; for(i=1; i=n; i++) X[i] = 0; //将解向量初始化为零 int C = M; // 将背包剩余容量初始化为 M for(i=1; i=n; i++){ if( V[i]C ) break; X[i] = 1; C -= V[i]; } if(i=n) X[i] = C/V[i]; };算法正确吗？;单源最短路径问题;实例;Dijkstra 算法的基本思想;“钓鱼”算法;小样例;输入: 含权有向图 G = (V，E) ，V = (1，2， ··· ，n)。 输出: G 中顶点 1 到其他顶点的距离。;10. Y = Y - {y} //将顶点 y 从 Y 中删除;引理;时间复杂度;定理 1;思路：用最小堆数据结构来保持集合Y 中的顶点，使 Y 组中离V-Y 最近的顶点 y 可以在 O(log n) 时间内被选出。;输入: 含权有向图 G = (V，E) ，V = (1，2， ··· ，n)。 输出: G 中顶点 1 到其他顶点的距离，假设已有一个空堆H。;11. for j = 1 to n - 1;运行时间主要取决于堆运算： DELETE: n-1 INSERT: n-1 SIFT-UP: m-n+1 每个堆运算用 Ο(log n) 时间，得到总共需要Ο(m log n) 时间。;堆排序：;堆的运算——上筛 Sift-up(H, i);堆的运算——下筛 Sift-down(H, i);堆的运算——插入 Insert(H, x);堆的运算——删除 Delete(H, i);堆的运算——删除最大值 DeleteMax( );堆的运算——建堆 MakeHeap(A);定理 2——高级论题;最小生成树问题;Kruskal 算法概要;算例;输入: 包含 n 个顶点的加权连通无向图 G ＝(V，E)。 输出: 由 G 生成的最小耗费生成树 T 组成的边的集合。;8. if FIND(x) ≠ FIND(y) then;3. Step 8 中， FIND(x) 与 FIND(y) 的含义是什么？;3. Step 8 中， FIND(x) 与 FIND(y) 的含义： 顺着下标找;边按权重排序如下 （边起点,边终点,边权重）;考察边(1,2,1) (Find(1)=1)≠(Find(2)=2) T={(1,2,1)} Union(1,2);④;④;④;④;④;如何实现 Step 8 中， FIND(x) 与 FIND(y) ？ 讨论尝试如何分支完成？;时间复杂度;定理;Prim 算法;PRIM 算法的基本思想;实例;输入: 含权有向图 G = (V，E) ，V = (1，2， ··· ，n)。 输出: G 中顶点 1 到其他顶点的距离（已有一个空堆H）;12. X ← X ∪ {y} // 将顶点 y 加入 X;定理;输入: 含权连通无向图 G = (V，E) ，V = (1，2， ··· ，n)。 输出: 由 G 生成的最小耗费生成树 T 组成的边的集合。;13. Y ← Y – {y} //从 Y 删除顶点 y ;定理;文件压缩问题;方法1：定长比特数表示每个字符;Prefix Restriction;Huffman 编码;基本原理： 总是选择频度最小的两个节点ci和cj构建一个新节点c，c为ci和cj的父节点，其频度为两个子节点的频度和。;满二叉树： 内部节点都恰好有两个分支，标记为0和1 树叶对应于文件中的字符 从根到叶的每一条路径上的0和1的序列对应相关字符的编码;Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd.;2. V ← C ; T = {};贪心算法特征;影响因素;最优子结构性质 一个问题的最优解包含着它的子问题的最优解，称此问题具有最优子结