013贪婪算法2.ppt

* * 例 山东大学计算机科学与技术学院 数据结构 第13章 贪婪算法 * Sollin算法示例 1 2 5 3 6 4 7 10 12 14 22 山东大学计算机科学与技术学院 数据结构 第13章 贪婪算法 * Sollin算法示例 1 2 5 3 6 4 7 10 12 14 22 25 16 山东大学计算机科学与技术学院 数据结构 第13章 贪婪算法 * 练习 1、描述图的普里姆算法和克鲁斯卡尔算法；分别用普里姆算法和克鲁斯卡尔算法求出下图的一棵最小代价生成树。给出构造最小生成树的过程. 1 3 5 7 2 4 6 8 2 4 6 3 8 10 14 12 7 9 山东大学计算机科学与技术学院 数据结构 第13章 贪婪算法 * 练习 2、描述图的普里姆算法和克鲁斯卡尔算法；分别用普里姆算法和克鲁斯卡尔算法求出下图的一棵最小代价生成树。给出构造最小生成树的过程. 1 2 4 3 5 6 1 5 3 6 2 6 5 5 5 5 7 4 山东大学计算机科学与技术学院 数据结构 第13章 贪婪算法 * 练习 3、有如下的网络邻接矩阵，画出该图；给出图的邻接链表表示；画出一棵最小生成树。 ∞ 17 ∞ ∞ 20 22 17 ∞ 6 7 ∞ 12 ∞ 6 ∞ 11 ∞ ∞ ∞ 7 11 ∞ 19 15 20 ∞ ∞ 19 ∞ 34 22 12 ∞ 15 34 ∞  山东大学计算机科学与技术学院 数据结构 第13章 贪婪算法 * 第13章 贪婪算法(The Greedy Method) 山东大学计算机科学与技术学院 数据结构 第13章 贪婪算法 * 本章内容 最优化问题 贪婪算法(greedy method) 山东大学计算机科学与技术学院 数据结构 第13章 贪婪算法 * 13.3.6 最小耗费生成树 例[最小代价通讯网络] 若图是连通的无向图或强连通的有向图，则从其中任何一个顶点出发都可以系统地访问到图中所有的顶点。 城市之间所有可能的通信连接可被视作一个无向图。 图的每条边都被赋予一个权值，权值表示建成由这条边所表示的通信连接所要付出的代价。 包含图中所有顶点（城市）的连通子图都是一个可行解。 图的所有顶点加上遍历过程中经过的边构成图的生成树。 最优解是其中具有最小代价的生成树。 优化函数是子集中所有边的权值之和。 山东大学计算机科学与技术学院 数据结构 第13章 贪婪算法 * 最小耗费生成树(最小代价生成树/最小生成树 ) 具有n个顶点的无向(连通)网络G的每个生成树刚好具有n-1条边。 最小耗费生成树问题是用某种方法选择n-1条边使它们形成G的最小生成树。 三种求解最小生成树的贪婪策略是： Kruskal (克鲁斯卡尔)算法 Prim(普里姆)算法 Sollin算法 13.3.6 最小耗费生成树 山东大学计算机科学与技术学院 数据结构 第13章 贪婪算法 * Kruskal(克鲁斯卡尔)算法 Kruskal算法思想 ： 开始，初始化含有 n个顶点 0条边的森林. Kruskal算法所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。 Kruskal算法分e步(e是网络中边的数目)。 按耗费递增的顺序来考虑这e条边，每次考虑一条边。 当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。 * * 例 * * 例 * * 例 * * 例 * * / /在一个具有n 个顶点的网络中找到一棵最小生成树 令T为所选边的集合，初始化T=? 令E 为网络中边的集合 while(E≠? )(| T