贪心算法PPT学习教案

1、会计学1 贪心算法贪心算法 将问题的求解过程看作是一系列选择将问题的求解过程看作是一系列选择, ,每次选择一个每次选择一个 输入输入, ,每次选择都是当前状态下的最好选择每次选择都是当前状态下的最好选择( (局部最优解局部最优解 ).).每作一次选择后每作一次选择后, ,所求问题会简化为一个规模更小的子所求问题会简化为一个规模更小的子 问题问题. .从而通过每一步的最优解逐步达到整体的最优解。从而通过每一步的最优解逐步达到整体的最优解。 4.1 基本思想 算法优点算法优点求解速度快,时间复杂性有较低的阶. 算法缺点算法缺点需证明是最优解. 常见应用背包问题,最小生成树,最短路径,作业调度等等

2、第1页/共77页 适用问题适用问题 具备具备贪心选择贪心选择和和最优子结构最优子结构性质的最优化问题性质的最优化问题 贪心选择贪心选择性质：性质：整体的最优解可通过一系列局部最优解达到，即整体的最优解可通过一系列局部最优解达到，即 贪心选择到达。贪心选择到达。 贪心算法通常以自顶向下的方式进行，以迭代的方式作出相贪心算法通常以自顶向下的方式进行，以迭代的方式作出相 继的贪心选择，每做一次贪心选择就将所求解的问题化简为规模继的贪心选择，每做一次贪心选择就将所求解的问题化简为规模 更小的问题更小的问题 对于一个具体问题，要确定它是否具有贪心选择的性质，我对于一个具体问题，要确定它是否具有贪心选择的

3、性质，我 们必须证明每一步所作的贪心选择最终导致问题的最优解。通常们必须证明每一步所作的贪心选择最终导致问题的最优解。通常 可以首先证明问题的一个整体最优解，是从可以首先证明问题的一个整体最优解，是从 贪心选择开始的，而贪心选择开始的，而 且作了贪心选择后，原问题简化为一个规模更小的类似子问题。且作了贪心选择后，原问题简化为一个规模更小的类似子问题。 然后，用数学归纳法证明，通过每一步作贪心选择，最终可得到然后，用数学归纳法证明，通过每一步作贪心选择，最终可得到 问题的一个整体问题的一个整体 最优解。最优解。 最优子结构性质最优子结构性质：当一个问题的最优解包含其子问题的最优解时当一个问题的最

4、优解包含其子问题的最优解时 ，称此问题具有最优子结构性质。，称此问题具有最优子结构性质。 第2页/共77页 A(1)A(2) A(n- 1) A(n) 某一问题的n个输入 B1(1)B1(2)B1(m) 该问题的一种解（ 可行解） 是A的一 个子集 满足一定 的条件 约束条件 Bk(1) Bk(2)Bk(m) 目标函数 取极值 最优解 算法设计与分析算法设计与分析 贪心算法贪心算法 第3页/共77页 4.2.活动安排问题 算法设计与分析算法设计与分析 贪心算法贪心算法 活动安排问题就是要在所给的活动集合中选出最大 的相容活动子集合，是可以用贪心算法有效求解的很好例 子。该问题要求高效地安排一系

5、列争用某一公共资源的活 动。贪心算法提供了一个简单、漂亮的方法使得尽可能多 的活动能兼容地使用公共资源。 问题陈述问题陈述 设有n个活动的集合E=1,2,n，其中每 个活动都要求使用同一资源，如演讲会场等，而在同一时 间内只有一个活动能使用这一资源。每个活动i都有一个 要求使用该资源的起始时间si和一个结束时间fi,且si fi 。如果选择了活动i，则它在半开时间区间si, fi)内占用 资源。若区间si, fi)与区间sj, fj)不相交，则称活动i 与活动j是相容的。也就是说，当sifj或sjfi时，活动 i与活动j相容。 第4页/共77页 1 2 3 4 5 6 7 8 9 10 11

6、例 例 1 3 0 5 3 5 6 8 8 2 12 4 5 6 7 8 9 10 11 12 13 14 i si fi 设待安排的设待安排的1111个活动起止时间按结束时间的非减序排列个活动起止时间按结束时间的非减序排列 最大相容活动子集(1, 4, 8, 111, 4, 8, 11), 也可表示为等长n元数组:(1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1) 算法思路算法思路将将n个活动按结束时间非减序排列个活动按结束时间非减序排列,依次考虑活动依次考虑活动i, 若若i 与已选择的活动相容与已选择的活动相容,则添加此活动到相容活动子集则添加此活动到相容活动子集. 第5页

7、/共77页 活动安排问题贪心算法 template void GreedySelector(int n, Type s , Type f , bool A ) A 1 = true; int j = 1; /从第二个活动开始检查是否与前一个相容 for (int i=2;i=fj) Ai = true; j=i; else A i = false; 算法设计与分析算法设计与分析 贪心算法贪心算法 各活动的起始时间和结束时间存储于数组各活动的起始时间和结束时间存储于数组s s和和f f中且按结束时间的非减序排列中且按结束时间的非减序排列 第6页/共77页 第7页/共77页 T(n)=O(nlog

8、n) (未排序时) 算法分析 T(n)=O(n) (排序时) 算法证明 算法达到最优解. 第8页/共77页 问题描述问题描述 输入输入:(x1,x2,.xn), xi=0,货箱货箱i不装船不装船; xi=1,货箱货箱i装船装船 可行解可行解: 满足约束条件满足约束条件 c 的输入的输入 优化函数优化函数: 最优解最优解:使优化函数达到最大值的一种输入使优化函数达到最大值的一种输入. i n i ix w 1 n i i x 1 4.3 最优装载 算法设计与分析算法设计与分析 贪心算法贪心算法 算法思路算法思路 将装船过程划为多步选择，每步装一个货箱，每次从将装船过程划为多步选择，每步装一个货箱

9、，每次从 剩下的货箱中选择重量最轻的货箱剩下的货箱中选择重量最轻的货箱.如此下去直到所有货箱均装上如此下去直到所有货箱均装上 船或船上不能再容纳其他任何一个货箱。船或船上不能再容纳其他任何一个货箱。 例 设n=8，w1，w8=100, 200, 50, 90, 150, 50, 20, 80，c=400。 所考察货箱的次序为 :7, 3, 6, 8, 4, 1, 5, 2。货箱7, 3, 6, 8, 4, 1的 总重量为390个单位且已被装载, 剩下的装载能力为10 ,小于任意 货箱.所以得到解x1,.x8= 1, 0, 1, 1, 0, 1, 1, 1 第9页/共77页 1、最优装载的贪心算

10、法 算法设计与分析算法设计与分析 贪心算法贪心算法 template void Loading(int x, Type w, Type c, int n ) int *t = new int n + 1; Sort(w, t, n) ; /按货箱重量排序/ for (int i = 1; i = n; i +) xi = 0; for (int i = 1;i= n /按单位价值排序/ int i; for (i =1;i = n;i+) xi = 0; float c = M; /c为背包剩余空间/ for (i =1;i c) break; xti= 1; c-= wti; if(i 贪心

11、算法贪心算法 第18页/共77页 算法分析算法分析: : 排序为主要算法时间,所以 T(n)=O(nlogn) 背包问题中的物体不能分拆背包问题中的物体不能分拆, ,只能整个装入称为只能整个装入称为0-10-1背背 包问题包问题. . 算法证明算法证明: :该算法能得到在最优解 用贪心算法能得到用贪心算法能得到0-10-1背包的最优解吗背包的最优解吗? ? 第19页/共77页 算法算法knapsackknapsack的主要计算时间在于将各种物品依其单位重量的价值从大到小排序。因此，算法的计算时间上界为的主要计算时间在于将各种物品依其单位重量的价值从大到小排序。因此，算法的计算时间上界为 O O

12、（nlognnlogn）。）。 为了证明算法的正确性，还必须证明背包问题具有贪心选择性质为了证明算法的正确性，还必须证明背包问题具有贪心选择性质。 第20页/共77页 第21页/共77页 算法设计与分析算法设计与分析 贪心算法贪心算法 第22页/共77页 算法设计与分析算法设计与分析 贪心算法贪心算法 第23页/共77页 问题问题: :通讯过程中需将传输的信息转换为二进制码通讯过程中需将传输的信息转换为二进制码. .由于英文由于英文 字母使用频率不同字母使用频率不同, ,若频率高的字母对应短的编码若频率高的字母对应短的编码, ,频率低的频率低的 字母对应长的编码字母对应长的编码, ,传输的数据

13、总量就会降低传输的数据总量就会降低. .要求找到一个要求找到一个 编码方案编码方案, ,使传输的数据量最少使传输的数据量最少. . 见见P109-P109-表表4-14-1 算法设计与分析算法设计与分析 贪心算法贪心算法 1、前缀码、前缀码 为能正确译码为能正确译码,编码需采用编码需采用前缀码前缀码, , 对每一个字符规定一个对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码串作为其代码，并要求任一字符的代码 都不是其它字符代码的前缀。这种编码称为前缀码。都不是其它字符代码的前缀。这种编码称为前缀码。 表示最优前缀码的二叉树总是一棵完全二叉树，即树中任一表示最优前缀码的二叉树总是一棵

14、完全二叉树，即树中任一 结点都有结点都有2个儿子结点。个儿子结点。 平均码长定义为：平均码长定义为： 使平均码长达到最小的前缀码编码方案称为给定编码字符集使平均码长达到最小的前缀码编码方案称为给定编码字符集 C的最优前缀码。的最优前缀码。 4.4 哈夫曼编码 )()()(cdcfTB T Cc 第24页/共77页 算法思路：算法思路： 1)以以n个字母为结点构成个字母为结点构成n棵仅含一个点的二叉树集合棵仅含一个点的二叉树集合,字母的频字母的频 率率 即为结点的权即为结点的权 2)每次从二叉树集合中找出两个权最小者合并为一棵二叉树每次从二叉树集合中找出两个权最小者合并为一棵二叉树:增增 加一个

15、根结点将这两棵树作为左右子树加一个根结点将这两棵树作为左右子树.新树的权为两棵子树的新树的权为两棵子树的 权之和权之和. 3) 反复进行步骤反复进行步骤2)直到只剩一棵树为止直到只剩一棵树为止. 第25页/共77页 算法设计与分析算法设计与分析 贪心算法贪心算法 哈夫曼编码哈夫曼编码 第26页/共77页 template BinaryTreeHuffmanTree(T f, int n) /根据权f1:n构造霍夫曼树 /创建一个单节点树的数组 Huffman *W=newHuffman n+1； BinaryTree z,zero； for(int i=1；i=n；i+) z.MakeTree

16、(i, zero, zero)； Wi.weight=fi； Wi.tree=z: /数组变成个最小堆 MinHeapHuffmanQ(1)； Q.Initialize(w,n,n)； /将堆中的树不断合并 Huffman x, y for(i=1;i 贪心算法贪心算法 哈夫曼编码哈夫曼编码 第27页/共77页 第28页/共77页 最优子结构: 设T为带权w1w2. wt的最优树,若将以带 权w1和w2的树叶为儿子的分枝点改为带权w1+w2的树叶,得到 一棵新树T, 则T也是最优树。 贪心选择性 : 设T为带权w1w2. wt的最优树, a).带权w1和w2的树叶vw1和vw2是兄弟. b).

17、以vw1和vw2为儿子的分枝点,其通路长度最长. 算法证明算法证明 算法分析算法分析 HuffmanTree初始化优先队列Q需要O(n) DeleteMin和Insert需O(logn). n-1次的合并总共需要O(nlogn) 所以n个字符的哈夫曼算法的计算时间为O(nlogn) 算法设计与分析算法设计与分析 贪心算法贪心算法 哈夫曼编码哈夫曼编码 第29页/共77页 4.5 单源最短路径 问题: 给定带权有向图G=(V,E), 其中每条边的权是一个非负实数. 要计算从V的一点v0(源)到所有其他各顶点的最短路长度. 路长指 路上各边权之和。 算法设计与分析算法设计与分析 贪心算法贪心算法

18、算法思路(Dijkstra) :设最短路长已知的终点集合为S,初始时v0S, 其 最短路长为0,然后用贪心选择贪心选择逐步扩充S :每次在V-S中,选择路径长路径长 度值最小的一条最短路径度值最小的一条最短路径的终点终点x加入S. 例例 题题 构造路长最短的最短路径构造路长最短的最短路径:设已构造i条最短路径,则下一个加入S的终 点u必是V-S中具有最小路径长度的终点, 其长度或者是弧(v0,u), 或者 是中间只经过S中的顶点而最后到达顶点u的路径. 例例 题题 第30页/共77页 v0 v2 v1 v3 v4 v5 20 45 50 10 15 15 20 10 35 30 3 路径长度

19、(1)v0v210 (2)v0v2v325 (3)v0v2v3v145 (4)v0v445 算法设计与分析算法设计与分析 贪心算法贪心算法 第31页/共77页 算法设计与分析算法设计与分析 贪心算法贪心算法 第32页/共77页 算法设计与分析算法设计与分析 贪心算法贪心算法 第33页/共77页 算法设计与分析算法设计与分析 贪心算法贪心算法 第34页/共77页 算法设计与分析算法设计与分析 贪心算法贪心算法 算法描述算法描述： (1) 用带权的邻接矩阵c来表示带权有向图, cij表示弧 上的权值. 若 V,则置cij为 设S为已知最短路径的终点的集合,它的初始状态为空集. 从源点v到图上其余各

20、点vi的当前最短路径长度的初值为： disti=cvi ，viV (2) 选择vj, 使得distj=Mindisti | viV-S vj就是长度最短的最短路径的终点。令S=SUj/更新S (3) 修改从v到集合V-S上任一顶点vk的当前最短路径长度: 如果 distj+cjk 贪心算法贪心算法 单源最短路径单源最短路径 例例 题题 迭代 Svid2d3d4d5 初始 1 10 30100 1 1,2 2 10 60 30100 2 1,2,4 4 10 50 30 90 3 1,2,3,4 3 10 50 30 60 41,2,3,4,5 5 10 50 30 60 1) v1 v2: 1

21、0 2) v1 v3: 50 3) v1 v4: 30 4) v1 v5: 60 1030100 50 10 2060 第36页/共77页 算法设计与分析算法设计与分析 贪心算法贪心算法 voidDijkstra(int n, int v,Type dist, int prev, Type *c) bool smaxint； for (int i=1;i=n; i+) disti=cvi； si=false； if(disti= =maxint) previ=0； else previ=v ; distv=0；sv=true； for (int i=1;in；i+) int temp=maxi

22、nt； int u= v； for (int j = 1；j=n；j+) if (!sj)j+) ； if(!sj)(cujmaxint) Type newdist=distu)+cuj; if (newdist 贪心算法贪心算法 单源最短路径单源最短路径 例例 题题 迭代 Svid2d3d4d5 初始 1 10 30100 1 1,2 2 10 60 30100 2 1,2,4 4 10 50 30 90 3 1,2,3,4 3 10 50 30 60 41,2,3,4,5 5 10 50 30 60 1) v1 v2: 10 2) v1 v3: 50 3) v1 v4: 30 4) v1

23、v5: 60 1030100 50 10 2060 第38页/共77页 v1 v4 v2 v3 v6v7 v5 20 30 50 40 55 25 70 50 25 10 70 50 0 20 50 30 0 25 70 0 40 25 50 0 55 0 10 70 0 50 0 算法设计与分析算法设计与分析 贪心算法贪心算法 第39页/共77页 迭代迭代 选取选取 结点结点 S DIST (1)(2)(3)(4)(5)(6)(7) 置初值置初值-10205030 121,2020453090 231,2,402045308590 341,2,4,302045307090 451,2,4,3

24、,502045307080140 561,2,4,3,5,602045307080130 SHORTEST-PATHS执行踪迹执行踪迹 算法设计与分析算法设计与分析 贪心算法贪心算法 第40页/共77页 算法设计与分析算法设计与分析 贪心算法贪心算法 最小生成树最小生成树 问题陈述问题陈述:设G(V,E)是一个无向连通带权图。E中每条边(v, w)的 权为cvw,若G的一个子图G是一棵包含G的所有顶点的树， 则称G为G的生成树。 生成树各边权的总和称为该生成树的耗费。 在G的所有生成树中,耗费最小的生成树称为G的最小 生成树. 抽象描述: 输入:任一连通生成子图 (该子图的边集合) 可行解:图

25、的生成树, 优化函数:生成树的各边权值之和 最优解:使优化函数达到最小的生成树. 4. 6 最小生成树最小生成树 第41页/共77页 算法设计与分析算法设计与分析 贪心算法贪心算法 最小生成树最小生成树 应用领域与图模型 第42页/共77页 算法思路算法思路: 首先置S=1, T= .若SV, 就作如下的贪心选择： 选取满足条件iS, jV-S,且cij最小的边(i, j),将顶点j添加到S中 边(i, j)添加到T中.这个过程一直进行到S=V时为止. T中的所有边构 成G的一棵最小生成树。 void Prim(int n, Type * * c) T= ; S =1; while (S!=

26、V) (i, j) = i S且 jV- S的最小权边; T=TU(i,j); S= S Uj; 算法描述算法描述 Prim算法算法 设G=(V,E)是一个连通带权图, y=l, 2, , n。 例例 题题 算法设计与分析算法设计与分析 贪心算法贪心算法 最小生成树最小生成树 第43页/共77页 第44页/共77页 图 Prim算法的执行过程 9 7 2 4 8 8 11 2 7 6 4 14 10 4 8 0 1 d a (b) ei c aEXTRACT-MIN(Q ) Q b,c, d, e, f, g, h, i V Q a Adj a b,h b a, key b4 h a, key

27、 h8 fg b h 9 7 2 4 8 8 11 2 7 6 4 14 10 0 1 d a (a) ei c fg b h 注：灰色部分表示集合S 每个结点的上的数 字表示S中的结点到该结 点的最小消耗，即 lowcost 用图示的边的连接 表示closest 第45页/共77页 图 Prim算法的执行过程 9 7 2 4 8 8 11 2 7 6 4 14 10 48 81 7 0 1 h db a (d) ei c h EXTRACT-MIN(Q ) Q c, d, e, f, g,i V Q a, b, h A dj h a, b, i, g i h, key i7 g h, key

28、 g1 fg 9 7 2 4 8 8 11 2 7 6 4 14 10 4 8 0 1 h db a (c) ei c bEXTRACT-MIN(Q ) Q c, d, e, f, g, h,i V Q a, b A dj b a, c, h c b, key c8 key h值不变 fg 8 第46页/共77页 图 Prim算法的执行过程 9 7 2 4 8 8 11 2 7 6 4 14 10 48 81 2 6 0 g 1 h db a (e ) ei cg EXTRACT-MIN(Q ) Q c , d , e , f, i V Q a , b , h , g A dj g f, h

29、, i f g , key f 2 i g , key i6f 第47页/共77页 图 Prim算法的执行过程 9 7 2 4 8 8 11 2 7 6 4 14 10 7 10 44 81 2 2 0 fg 1 h cdb a (g) cEXTRACT-MIN(Q ) Q d, e, i V Q a, b, c, h, g, f Adj c b, d, f, i d c, key d 7 i c, key i2 ei 9 7 2 4 8 8 11 2 7 6 4 14 10 14 10 44 812 6 0 gh db a (f ) ei c fEXTRACT-MIN(Q ) Q c, d,

30、 e, i V Q a, b, h, g, f Adj f c, d, e, g c f, key c4 d f, key d 14 e f, key e10 f 1 第48页/共77页 图 4-16Prim算法的执行过 程 9 7 2 4 8 8 11 2 7 6 4 14 10 7 10 44 812 2 0 fg 1 h i cdb a (h) iEXTRACT-MIN(Q ) Q d, e V Q a, b, c, d, h, i, g, f A dj d c, e, f e 9 7 2 4 8 8 11 2 7 6 4 14 10 7 9 44 81 2 2 0 dEXTRACT-M

31、IN(Q ) Q e V Q a, b, c, d, h, i, g, f A dj d c, e, f e d, key e9 g 1 h i c e b a (i ) d f 2 第49页/共77页 图 4-16Prim算法的执行过 程 9 7 2 4 8 8 11 2 7 6 4 14 10 7 9 44 812 2 0 eEXTRACT-MIN(Q) Q V Qa, b, c, d, h, i, g, f, e Adje d, f g 1 h i c e b a ( j ) d f 第50页/共77页 template void Prim(int n, Type * * c) Type

32、 lowcostmaxint; int closest maxim; bool smaxint; s1 = true; for(int i = 2;i= n; i+) lowcosti = cli; closest i = 1; si= false; for (int i = 1; i n; i+) Type min = inf; int j = 1; for (int k = 2;k= n; k+) if (lowcostk min) j=k; cout j closestj end; sj = true; for(intk= 2; k= n; k+) if (cjk 贪心算法贪心算法 最小

33、生成树最小生成树 第51页/共77页 算法思路算法思路:首先将G的n个顶点看成n个孤立的连通分支, 将所有的边 按权从小到大排序, 然后从第一条边开始, 依边权递增的顺序查看每一条边， 并按下述方法连接两个通分支： 当查看到第k条边(v,w)时, 如果端点u和w分别是当前两个 不同的连通分支T1, T2中的顶点时,就用边(u,w)将TI和T2连接成一个 连通分支，然后继续查看第k+1条边; 如果端点v和w在当前的同一个连通分支中，就直接再查 看第k十1条边。直到只剩下一个连通分支为止。 此时，这个连通分枝就是G的一颗最小生成树 Kruskal算法算法 G=(V, E), V= 贪心算法贪心算法

34、 最小生成树最小生成树 第52页/共77页 e1(1)e2(6) e8(9) e6 (2) e9(4)e5(5) e4(7) e10(8)e11(3) e7(10) e3(11) 1) 以以G 中全部点为点作图中全部点为点作图 2) 按权的大小次序依次添加按权的大小次序依次添加 各边各边,若出若出 现回路则忽略此边现回路则忽略此边. 3) 加入加入n-1条边后就得到最小条边后就得到最小 生成树生成树. 1 2 5 3 7 求最小生成树求最小生成树( (Kruscal) ) 最优解最优解: (e1, e6, e11, e5, e4) 第53页/共77页 例例 题题 算法设计与分析算法设计与分析

35、贪心算法贪心算法 最小生成树最小生成树 第54页/共77页 第55页/共77页 第56页/共77页 第57页/共77页 第58页/共77页 template bool Kruskal(int n, int e, EdgeNode E , EdgeNode t ) MinHeap EdgeNode H(1); H. Initialize(E, e, e); UnionFind U(n); iht k = 0; while (e x.u = 2; x.v = 1; x. weight = 5; H. DeleteMin(x); e-; int a = U.Find(x.u); int b = U.

36、Eind(x.v); if (a! = b) tk + = x; U. Union(a, b); H. Deactivate( ) renturn (k = = n-1) Kruska算法算法 算法设计与分析算法设计与分析 贪心算法贪心算法 最小生成树最小生成树 第59页/共77页 A=（选出的边） E =(h,g,1),(g,f,2),(c,i,2),(a,b,4),(c,f,4),(g,I,6),(c,d,7),(a,h,8),(b,c,8), (d,e,9), (e,f,10),(b,h,11),(d,f,14)（原图中的边） 初始状态初始状态 森林由森林由9棵树组成棵树组成 A=(h,

37、g) E =(g,f,2),(c,i,2),(a,b,4),(c,f,4),(g,I,6),(c,d,7),(a,h,8),(b,c,8), (d,e,9), (e,f,10),(b,h,11),(d,f,14) 接受边接受边(h,g) UNION(g,h) 森林由森林由8棵树组成棵树组成 （a） （b） 第60页/共77页 图 Kruskal算法的执行过程 E =(c,i,2),(a,b,4),(c,f,4),(g,I,6),(c,d,7),(a,h,8),(b,c,8), (d,e,9), (e,f,10), (b,h,11),(d,f,14) （c） E =(c,i,2),(a,b,4)

38、,(c,f,4),(g,I,6),(c,d,7),(a,h,8),(b,c,8), (d,e,9), (e,f,10), (b,h,11),(d,f,14) （d） 接受边接受边(c,i) UNION(c,i) 森林由森林由6棵树组成棵树组成 接受边接受边(g,f) UNION(g,f) 森林由森林由7棵树组成棵树组成 第61页/共77页 图 Kruskal算法的执行过程 4 2 2 1 a h b i gf cd e ( e ) 接受边(a, b ) UNION(a, b ) 森林由5棵树组 成 A (h, g), ( g, f ), ( c, i), ( a, b) E (c, f, 4)

39、, ( g, i, 6), ( c, d, 7), ( h, i, 7), ( a, h, 8), ( b, c, 8), ( d, e, 9), ( e, f, 10), ( b, h, 11), ( d, f, 14) E =(c,f,4),(g,I,6),(c,d,7),(a,h,8),(b,c,8), (d,e,9), (e,f,10), (b,h,11),(d,f,14) 接受边接受边(a,b) UNION(a,b) 森林由森林由5棵树组成棵树组成 第62页/共77页 图 Kruskal算法的执行过程 4 2 2 1 4 7 a h b i gf cd e ( g ) 拒绝边(g,

40、i ), 接受边( c, d) UNION(c, d) 森林由3棵树组 成 A (h, g), ( g, f ), ( c, i), ( a, b), ( c, f ), ( c, d) E (h, i, 7), ( a, h, 8), ( b, c, 8), ( d, e, 9), ( e, f, 10), ( b, h, 11), ( d, f, 14) 4 2 2 1 4 a h b i gf cd e ( f ) 接受边(c, f ) UNION(c, f ) 森林由4棵树组 成 A (h, g), ( g, f ), ( c, i), ( a, b), ( c, f ) E (g,

41、i, 6), ( c, d,7), ( h, i, 7), ( a, h, 8), ( b, c, 8), ( d, e, 9), ( e, f, 10), ( b, h, 11), ( d, f, 14) E =(g,I,6),(c,d,7),(a,h,8),(b,c,8), (d,e,9), (e,f,10), (b,h,11),(d,f,14) E =(a,h,8),(b,c,8), (d,e,9), (e,f,10), (b,h,11),(d,f,14) 接受边接受边(c,f) UNION(c,f) 森林由森林由4棵树组成棵树组成 选取边（选取边（g,I,6）但因为）但因为g和和i在一

42、个连通子图中，即在一个连通子图中，即U.Find(g)和和U.Find(i)相同，所以拒绝边相同，所以拒绝边(g,i) 接受边接受边(c,d) UNION(c,d) 森林由森林由3棵树组成棵树组成 第63页/共77页 图 Kruskal算法的执行过程(续) 9 4 2 2 1 4 7 8 a h b i gf cd e ( i ) 拒绝边(b, c ), 接受边( d, e) UNION(d, e) 森林由1棵树组 成 A (h, g), ( g, f ), ( c, i), ( a, b), ( c, f ), ( c, d), ( a,h), ( d,e) E (e, f, 10), (

43、b, h,11 ), ( d, f,14) 4 2 2 1 4 7 8 a h b i gf cd e ( h ) 拒绝边(h, i ), 接受边( a, h) UNION(a, h) 森林由2棵树组 成 A (h, g), ( g, f ), ( c, i), ( a, b), ( c, f ), ( c, d), ( a,h) E (b, c, 8), ( d, e,9), ( e, f, 10), ( b, h, 11), ( d, f, 14) 拒绝边拒绝边(h,i) 接受边接受边(a,h) UNION(a,h) 森林由森林由2棵树组成棵树组成 拒绝边拒绝边(b,c) 接受边接受边(d

44、,e) UNION(d,e) 森林由森林由1棵树组成棵树组成 第64页/共77页 图 Kruskal算法的执行过程(续) 9 4 2 2 1 4 7 8 a h b i gf cd e ( j ) E 边(e, f ), ( b, h), ( d, f )均被拒绝集合 E变为空 A (h, g), ( g, f ), ( c, i), ( a, b), ( c, f ), ( c, d), ( a,h), ( d,e) 第65页/共77页 第66页/共77页 第67页/共77页 第68页/共77页 最小代价通讯网络 在N城市之间架设通讯线路,要求造价最低. 城市之间所有可能的通讯连接视作一个无

45、向图G,G中每边的权值 表示建成这段线路的代价. 问题转化为求一棵最小生成树. 问题描述: 输入:任一连通图G (该图的边集合) 可行解:图G的生成树 优化函数:生成树的各边权值之和 最优解:使优化函数达到最小值的生成树. 最优化问题(optimization problem): 问题可描述为有n个输入(x1,x2,.xn),一组约束条件和一个优化 (目标)函数。满足约束条件的输入称为可行解可行解,它它是输入的一个子 集.使优化函数取得极值的可行解称为最优解最优解. 算法设计与分析算法设计与分析 贪心算法贪心算法 例例1 1 第69页/共77页 *旅行商问题(货郎担问题) 问题: 设一个由N个

46、城市v1,v2,vn组成的网络, ci,j 为从vi 到vj的代价 不妨设ci,j = cj,i ,且ci,i= .一推销员要从某城市出发经过每城市一次 且仅一次后返回出发地问如何选择路线使代价最小。 51 4 3 1 7 3 4 2 2 1275 1443 2412 7413 5323 算法设计与分析算法设计与分析 贪心算法贪心算法 抽象描述抽象描述:将城市以及之间的道路抽象为一个无向图G, G中每边的 权值表示这段线路的代价. 问题转化为求一条最佳周游路线:从一点 出发,经过每点一次且仅一次并返回原点,且该路线的总代价最小. v1 v5 v2 v4v3 C= 第70页/共77页 输入:城市的数目n,代价矩阵c=c(1.n,1.n). 输出: 最小代价路线 1. tour:=0; / tour 纪录路线/ 2. cost:=0; / cost 纪录到目前为止的花费/ 3. v:=N; / N为起点城市, v为当前出发城市/ 4. for k:=1 to N-1 do 5. tour:= tour+(v,w) /(v,w)为从v到其余城市代价中值