第第4 4章章 贪心算法贪心算法 4.1 4.1 贪心算法的基本要素贪心算法的基本要素 4.2 4.2 活动安排问题活动安排问题 4.3 4.3 最优装载最优装载 4.4 4.4 单源最短路径单源最短路径 4.5 4.5 哈夫曼编码哈夫曼编码 4.6 4.6 多机调度问题多机调度问题2021/5/211贪心算法贪心算法n顾名思义，贪心算法总是作出在当前看来最好顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的虑，它所作出的选择只是在某种意义上的局部局部最优最优选择。当然，希望贪心算法得到的最终结选择。当然，希望贪心算法得到的最终结果也是整体最优的。果也是整体最优的。n虽然贪心算法不能对所有问题都得到整体最优虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。其最终结果却是最优解的很好近似。2021/5/212例：用贪心法求解付款问题。例：用贪心法求解付款问题。假设有面值为假设有面值为5元、元、2元、元、1元、元、5角、角、2角、角、1角的角的货币，需要找给顾客货币，需要找给顾客4元元6角现金，为使付出的货角现金，为使付出的货币的数量最少，首先选出币的数量最少，首先选出1张面值不超过张面值不超过4元元6角的角的最大面值的货币，即最大面值的货币，即2元，再选出元，再选出1张面值不超过张面值不超过2元元6角的最大面值的货币，即角的最大面值的货币，即2元，再选出元，再选出1张面值张面值不超过不超过6角的最大面值的货币，即角的最大面值的货币，即5角，再选出角，再选出1张张面值不超过面值不超过1角的最大面值的货币，即角的最大面值的货币，即1角，总共角，总共付出付出4张货币。张货币。2021/5/213 在付款问题每一步的贪心选择中，在不超在付款问题每一步的贪心选择中，在不超过应付款金额的条件下，只选择面值最大过应付款金额的条件下，只选择面值最大的货币，而不去考虑在后面看来这种选择的货币，而不去考虑在后面看来这种选择是否合理，而且它还不会改变决定：一旦是否合理，而且它还不会改变决定：一旦选出了一张货币，就永远选定。付款问题选出了一张货币，就永远选定。付款问题的贪心选择策略是尽可能使付出的货币最的贪心选择策略是尽可能使付出的货币最快地满足支付要求，其目的是使付出的货快地满足支付要求，其目的是使付出的货币张数最慢地增加，这正体现了贪心法的币张数最慢地增加，这正体现了贪心法的设计思想。设计思想。2021/5/214贪心算法的设计思路贪心算法的设计思路 贪心算法的设计思路是：总是做出贪心算法的设计思路是：总是做出在当前看来最好的选择，即在当前看来最好的选择，即贪心算贪心算法并不是从整体最优考虑法并不是从整体最优考虑，它所做，它所做的选择只是在某种意义上的的选择只是在某种意义上的局部最局部最优选择优选择。2021/5/215贪心算法框架贪心算法框架Greedy(A,n) /A为输入集合为输入集合 solution = ; / 解空间初始化为空解空间初始化为空 for (i = 1; i =n; i+) /对每个输入进行检测对每个输入进行检测 x = select(A); / 选择一个输入选择一个输入 if (feasible(solution,x) / 如果可行如果可行 solution = union(solution,x); / 添至解空间添至解空间 return solution; 2021/5/2164.1 4.1 贪心算法的基本要素贪心算法的基本要素 利用贪心算法求解最优解的两个前提条件利用贪心算法求解最优解的两个前提条件: : 贪心选择性质贪心选择性质和和最优子结构性质最优子结构性质。 1.1.贪心选择性质贪心选择性质 所谓所谓贪心选择性质贪心选择性质是指所求问题的是指所求问题的整体最优解整体最优解可以通过一系列可以通过一系列局部最优局部最优的选择，即贪心选择的选择，即贪心选择来达到。这是利用贪心算法求解最优解的第一来达到。这是利用贪心算法求解最优解的第一个基本要素，也是贪心算法与动态规划算法的个基本要素，也是贪心算法与动态规划算法的主要区别。主要区别。 2021/5/217 2.2.最优子结构性质最优子结构性质 当一个问题的最优解包含其子问题的最优解时，当一个问题的最优解包含其子问题的最优解时，称此问题具有称此问题具有最优子结构性质最优子结构性质。问题的最优子。问题的最优子结构性质是该问题可用动态规划算法或贪心算结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。法求解的关键特征。2021/5/218 3.3.贪心算法与动态规划算法的差异贪心算法与动态规划算法的差异 共同点共同点：求解的问题都具有最优子结构性质：求解的问题都具有最优子结构性质差异点差异点：动态规划算法通常以动态规划算法通常以自底向上自底向上的方式的方式解各子问题，而贪心算法则通常以解各子问题，而贪心算法则通常以自顶向下自顶向下的的方式进行，以迭代的方式作出相继的贪心选择，方式进行，以迭代的方式作出相继的贪心选择，每做一次贪心选择就将所求问题简化为规模更每做一次贪心选择就将所求问题简化为规模更小的子问题。小的子问题。2021/5/219 0-10-1背包问题：背包问题： 给定给定n n种物品和一个背包。物品种物品和一个背包。物品i i的重量是的重量是W Wi i，其价值为，其价值为V Vi i，背包最大承载重量为，背包最大承载重量为C C。应如何选择装入背包的物品，。应如何选择装入背包的物品，使得装入背包中物品的总价值最大使得装入背包中物品的总价值最大? ?在选择装入背包的物品时，对每种物品在选择装入背包的物品时，对每种物品i i只有只有2 2种选择，种选择，即装入背包或不装入背包。不能将物品即装入背包或不装入背包。不能将物品i i装入背包多次装入背包多次，也不能只装入部分的物品，也不能只装入部分的物品i i。 背包问题背包问题： 与与0-10-1背包问题类似，所不同的是在选择物品背包问题类似，所不同的是在选择物品i i装入背包装入背包时，时，可以选择物品可以选择物品i i的一部分的一部分，而不一定要全部装入背，而不一定要全部装入背包，包，1in1in。2021/5/21100-1背包与背包问题都具有最优子结构背包与背包问题都具有最优子结构 已知背包最大承载重量为已知背包最大承载重量为C，共有，共有n个物品，个物品，每个物品的重量分别为每个物品的重量分别为Wi(i=1,2,.,n)，价值，价值为为Vi(i=1,2,.n)。 证明证明： 假设第假设第k个物品是最优解中的一个物品个物品是最优解中的一个物品，则，则 从中拿出从中拿出W Wk k对应的物品后所对应的解一定是对应的物品后所对应的解一定是其余其余n-1n-1个物品，装入背包最大承载重量为个物品，装入背包最大承载重量为C-WC-Wk k的最优解，否则与假设矛盾。的最优解，否则与假设矛盾。2021/5/2111l0-10-1背包问题不具有贪心选择性质背包问题不具有贪心选择性质。原因是无法保证能够将背包装满，原因是无法保证能够将背包装满，而所剩空间将会降低总价值。而所剩空间将会降低总价值。l背包问题具有贪心选择性质背包问题具有贪心选择性质。2021/5/21120-10-1背包问题不具有贪心选择特性背包问题不具有贪心选择特性物品物品1 11010公斤，价值公斤，价值6060元元物品物品2 22020公斤，价值公斤，价值100100元元物品物品3 33030公斤，价值公斤，价值120120元元单位价值单位价值6元元单位价值单位价值5元元单位价值单位价值4元元背包容量：背包容量：5050公斤公斤物品物品1 1物品物品2 2= =￥60+10060+100贪心算法贪心算法物品物品2 2物品物品3 3= =￥100+120100+120最优解最优解2021/5/2113背包问题具有贪心选择特性背包问题具有贪心选择特性物品物品1 11010公斤，价值公斤，价值6060元元物品物品2 22020公斤，价值公斤，价值100100元元物品物品3 33030公斤，价值公斤，价值120120元元单位价值单位价值6元元单位价值单位价值5元元单位价值单位价值4元元背包容量：背包容量：5050公斤公斤物品物品1 1物品物品2 2物品物品3 3= =￥60+100+8060+100+80贪心算法贪心算法1010公斤公斤2020公斤公斤2020公斤公斤2021/5/2114用贪心算法解背包问题的基本步骤：用贪心算法解背包问题的基本步骤： 1.1.计算每种物品单位重量的价值计算每种物品单位重量的价值V Vi i/W/Wi i；2.2.按照单位重量的价值从高到低的顺序排序；按照单位重量的价值从高到低的顺序排序；3.3.依据贪心选择策略，按照单位价值从高到低依据贪心选择策略，按照单位价值从高到低的顺序，依次将尽可能多的物品装入背包中。的顺序，依次将尽可能多的物品装入背包中。 直到背包装满为止。直到背包装满为止。 是否可以将物品装入背包的条件是：是否可以将物品装入背包的条件是： 有空间有空间2021/5/2115背包问题的贪心算法背包问题的贪心算法void knapsack(float c,float w, float v,float x,int n) 将各种物品依其单位重量的价值从高到低排序将各种物品依其单位重量的价值从高到低排序 初始化初始化 xi=0; for (i=0;in;i+) /贪心选择贪心选择 if (不能放不能放) break; 放入背包中放入背包中 if (背包没满背包没满&还有物品还有物品) 装满装满; return opt;wiwi重量重量vivi单位价值单位价值xixi结果结果2021/5/2116背包问题的贪心算法背包问题的贪心算法float knapsack(float c,float w, float v,float x,int n) ITEMTYPE dn; for (int i = 0; i n; i+) di = (wi,vi,i); mergeSort(d); /按照单价高低排序按照单价高低排序 int i; float opt=0; for (i=0;in;i+) xi=0; for (i=0;ic) break; xdi.i=1; opt+=di.v; c-=di.w; if (c0& in) /零碎空间零碎空间 xdi.i = c/di.w; opt += xdi.i*di.v; return opt;wvi单价10601620100253012034112/3x算法算法knapsackknapsack的的主要计算时间是主要计算时间是将各种物品依其将各种物品依其单位重量的价值单位重量的价值从大到小排序。从大到小排序。因此，算法的计因此，算法的计算时间上界为算时间上界为O O（nlognnlogn）。）。typedef struct float w,v; int i; ITEMTYPE;D :2021/5/21174.2 4.2 活动安排问题活动安排问题 设有设有n n个活动的集合个活动的集合E=1,2,E=1,2,n,n，其中每个活，其中每个活动都要求使用同一资源，如演讲会场等，而动都要求使用同一资源，如演讲会场等，而在在同一时间内只有一个活动能使用这一资源同一时间内只有一个活动能使用这一资源。每。每个活动个活动i i都有一个要求使用该资源的都有一个要求使用该资源的起始时间起始时间s si i和一个结束时间和一个结束时间f fi i, ,且且s si i f |Aik|+1+|Akj|=|Aij| 与假设矛盾！与假设矛盾！2021/5/2120 令子问题令子问题Sij 且且a1为子问题为子问题Sij中具有最中具有最早完成时间的任务，则早完成时间的任务，则a1一定包含在子问一定包含在子问题题Sij中某个任务相互兼容的最大子集中。中某个任务相互兼容的最大子集中。 结论：结论：具有贪心选择特性。具有贪心选择特性。（2）活动安排具有贪心选择特性）活动安排具有贪心选择特性2021/5/2121证明：明： 假假设子子问题Sij的最的最优解解为Aij，其中的任，其中的任务按照完成按照完成时间由小到大排列；且第一个由小到大排列；且第一个任任务为ak。如果。如果ak = a1，成立。，成立。如果如果ak a1 ，由于，由于a1完成完成时间较ak早，所早，所以，可以将以，可以将ak去掉，去掉，换成成a1，仍然相容，仍然相容，所含任所含任务数量一数量一样。2021/5/2122活动安排问题举例活动安排问题举例 假设待安排的假设待安排的1111个活动的开始时间和结束时个活动的开始时间和结束时间按结束时间的非减序排列如下：间按结束时间的非减序排列如下：i1234567891011Si130535688212fi4567891011121314若被检查的活动若被检查的活动i i的开始时间的开始时间S Si i小于最近小于最近选择的活动选择的活动j j的结束时间的结束时间f fi i，则不选择活，则不选择活动动i i，否则选择活动，否则选择活动i i加入集合加入集合A A中中2021/5/2123 图中每行相应于算法图中每行相应于算法的一次迭代。的一次迭代。阴影长阴影长条条表示的活动是已选表示的活动是已选入集合入集合A A的活动，而的活动，而空白长条空白长条表示的活动表示的活动是当前正在检查相容是当前正在检查相容性的活动。性的活动。i1234567891011Si130535688212fi45678910111213142021/5/2124isifi11423530645753865976108811981210213111214012345678910 1112 13 14结果：选中的任务为：结果：选中的任务为：1 1、4 4、8 8、11112021/5/2125解活动安排问题的贪心算法解活动安排问题的贪心算法int greedySelector(int s, int f, boolean a,int n) a1=true; / 初始化初始化 int j = 1, count = 1; for (int i = 2; i = fj) ai = true; j = i; count+; else ai = false; return count;各活动的起始时间和各活动的起始时间和结束时间存储于数组结束时间存储于数组s s和和f f中且按结束时间的中且按结束时间的非减序排列非减序排列 2021/5/2126 假设输入的活动以其完成时间的假设输入的活动以其完成时间的非减序非减序排列，排列，则算法则算法greedySelectorgreedySelector总选择总选择最早完成时间最早完成时间的相容活动加入集合的相容活动加入集合A A中。该算法的贪心选择中。该算法的贪心选择的意义是的意义是使剩余的可安排时间段极大化使剩余的可安排时间段极大化，以，以便安排尽可能多的相容活动。便安排尽可能多的相容活动。 算法算法greedySelectorgreedySelector的效率极高。当输入的的效率极高。当输入的活动已按结束时间的非减序排列，算法只需活动已按结束时间的非减序排列，算法只需O(n)O(n)的时间安排的时间安排n n个活动，使最多的活动能相个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按容地使用公共资源。如果所给出的活动未按非减序排列，可以用非减序排列，可以用O(nlogn)O(nlogn)的时间重排。的时间重排。 2021/5/21274.3 4.3 最优装载最优装载 有一批集装箱要装上一艘载重量为有一批集装箱要装上一艘载重量为c c的的轮船。其中，集装箱轮船。其中，集装箱i i的重量为的重量为W Wi i。最。最优装载问题要求确定优装载问题要求确定在装载体积不受限在装载体积不受限制的情况下制的情况下，将，将尽可能多尽可能多的集装箱装上的集装箱装上轮船。轮船。2021/5/2128 最优装载问题可用贪心算法求解。采用重最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略，可产生最量最轻者先装的贪心选择策略，可产生最优装载问题的最优解。优装载问题的最优解。2021/5/2129(1)(1)最优子结构的性质最优子结构的性质 设设 (x(x1 1,x,x2 2,.,x,.,xn n) )是最优装载问题满足贪是最优装载问题满足贪心选择的最优解，则可知，心选择的最优解，则可知， x x1 1=1=1，且，且(x(x2 2,.,x,.,xn n) )是轮船重量为是轮船重量为c-wc-w1 1, ,待待装船集装箱为装船集装箱为2,3,.,n2,3,.,n时相应最优装载时相应最优装载问题的最优解。问题的最优解。 利用反证法证明。利用反证法证明。2021/5/2130(2)(2)贪心选择性质贪心选择性质 设集装箱依重量从小到大排序，设集装箱依重量从小到大排序，(x(x1 1,x,x2 2,.,x,.,xn n) )是最优装载问题的一个最优解。是最优装载问题的一个最优解。设设x:(0x:(0，0 0，1 1，1 1，1 1，0 0，0 0，0 0） k = 3k = 3y:(y:(1 1，0 0，0 0，1 1，1 1，0 0，0 0，0 0） 2021/5/2131最优装载贪心算法最优装载贪心算法float loading(float c, float w, int x,int n) ITREMTYPE dn; for (int i = 0; i n; i+) di = (wi,i); mergeSort(d); / 排序排序 O(nlogn) float opt=0; for (int i = 0; i n; i+) xi = 0; for (int i = 0; i n & di.w = c; i+) /贪心选择贪心选择 xdi.i = 1; opt+=di.w; c -= di.w; return opt;typedef struct float w; int i; ITEMTYPE;2021/5/21322021/5/21334.4 4.4 单源最短路径单源最短路径问题提出问题提出: :给定带权有向图给定带权有向图G =(V,E)G =(V,E)，其中每，其中每条边的权是非负实数。另外，还给定条边的权是非负实数。另外，还给定V V中的一中的一个顶点，称为个顶点，称为源源。现在要计算从源到所有其他。现在要计算从源到所有其他各顶点的各顶点的最短路经长度最短路经长度。这里路径长度是指路。这里路径长度是指路上各边权之和。这个问题通常称为上各边权之和。这个问题通常称为单源最短路单源最短路径问题径问题。2021/5/2134v0v0v1v1 : :无无v0v0v2v2:10:10v0 v0 v4 v4 v3v3:50:50v0 v0 v4v4:30:30v0 v0 v4 v4 v3 v3 v5v5:60:60v0v1v2v3v4v510060302010505102021/5/2135（1 1）DijkstraDijkstra算法算法DijkstraDijkstra算法是解单源最短路径问题的算法是解单源最短路径问题的贪心算法贪心算法。其。其基本思想基本思想是设置一个已经是设置一个已经确定最短路径的顶点集合确定最短路径的顶点集合S S，并通过不断，并通过不断地地贪心选择贪心选择来扩充这个集合。一个顶点来扩充这个集合。一个顶点属于集合属于集合S S当且仅当从源到该顶点的最短当且仅当从源到该顶点的最短路径长度已知。路径长度已知。 2021/5/2136DijkstraDijkstra算法基本过程算法基本过程初始时，初始时，S S中仅含有源。设中仅含有源。设u u是是V-SV-S中的一个顶中的一个顶点。把从源到点。把从源到u u且中间只经过且中间只经过S S中顶点的路称为中顶点的路称为从源到从源到u u的的特殊路径特殊路径，并用数组，并用数组distdist记录当前记录当前每个顶点所对应的最短特殊路径长度。每个顶点所对应的最短特殊路径长度。uSV-S2021/5/2137DijkstraDijkstra算法基本过程算法基本过程DijkstraDijkstra算法每次从算法每次从V-SV-S中取出具有中取出具有最短特殊最短特殊路长度路长度的顶点的顶点u u，将，将u u添加到添加到S S中，同时对数组中，同时对数组distdist作必要的修改。一旦作必要的修改。一旦S S包含了所有包含了所有V V中顶点，中顶点，distdist就记录了从源到所有其他顶点之间的最短就记录了从源到所有其他顶点之间的最短路径长度。路径长度。uV-SS2021/5/2138DijkstraDijkstra算法的迭代过程算法的迭代过程迭代迭代S Su udist2dist2 dist3dist3 dist4dist4 dist5dist5 初始初始11- -1010 30301001001 11,1,2 2 2 21010606030301001002 21,2,1,2,4 4 4 410105050303090903 31,2,4,1,2,4,3 3 3 310105050303060604 41,2,4,3,1,2,4,3,5 5 5 510105050303060602021/5/2139算法算法 置置S S为空；为空； 将源点将源点v v0 0加入加入S S； 初始化初始化distdist，即对每个非源点，即对每个非源点i i令令distidisti为边为边的权，不存在令的权，不存在令distidisti为为。 while (Swhile (S中没有包含全部顶点中没有包含全部顶点) ) /贪心选择贪心选择 选择选择V-SV-S结点结点u u， distu=mindistv|v distu=mindistv|vV-SV-S； 将将u u加入加入S;S; for (V-S for (V-S中每个结点中每个结点v)v) distv=mindistv,distu+cost(u,v);distv=mindistv,distu+cost(u,v); 2021/5/2140（2）DijkstraDijkstra算法具有算法具有最优子结构性质最优子结构性质 证明算法中每步确定的证明算法中每步确定的disti是当前从源点到顶是当前从源点到顶点点i的最短的最短特殊路径特殊路径长度。长度。证明证明：采用数学归纳法。：采用数学归纳法。当当|S|=1时，显然成立。时，显然成立。假设在第假设在第k次贪心选择之前次贪心选择之前disti存放着从源点到存放着从源点到顶点顶点i的最短特殊路径长度。的最短特殊路径长度。需要证明（第需要证明（第k+1次贪心选择）：根据贪心选择次贪心选择）：根据贪心选择策略，将顶点策略，将顶点u添加到添加到S之后，之后，disti仍然是当前仍然是当前从源点到顶点从源点到顶点i的最短特殊路径长度。的最短特殊路径长度。2021/5/2141Susix假设根据贪心选择策略，第假设根据贪心选择策略，第k+1选选择将顶点择将顶点u添加到添加到S中，对于顶点中，对于顶点i可能会增加一条从源点到达顶点可能会增加一条从源点到达顶点i的的新的特殊路径。新的特殊路径。这条新的特殊路径由两种可能：这条新的特殊路径由两种可能：情况情况1：这条路径先由源点到达顶点：这条路径先由源点到达顶点u，再由顶点，再由顶点u直接直接到达到达i，则这条，则这条特殊路径特殊路径的长度为：的长度为： distu+aui如果这条路径更短，替换如果这条路径更短，替换disti；否则不变。；否则不变。2021/5/2142Susix情况情况2：如果新增加的特殊路径先：如果新增加的特殊路径先由源点到达顶点由源点到达顶点u，再由顶点，再由顶点u途径途径另一顶点另一顶点x到达到达i。由于。由于x早早于于u进入进入S中，所以中，所以distxdistu,即即distx+axi distu+aux+axi，故：这条新特殊路径不会影响故：这条新特殊路径不会影响disti，因此不需，因此不需要考虑。要考虑。结论：在任何时候，结论：在任何时候，disti都存放着当前从源点都存放着当前从源点到到i点的最短特殊路径长度。点的最短特殊路径长度。2021/5/2143（3） Dijkstra Dijkstra算法具有算法具有贪心选择性质贪心选择性质 按照贪心选择方式得到的按照贪心选择方式得到的distudistu一定是从源一定是从源点点s s到顶点到顶点u u的最短路径长度。的最短路径长度。 证明：假设存在一条从源点证明：假设存在一条从源点s s到到u u的更短路径。的更短路径。Sxsud(s,x) 是从是从s 到到x的路径长度的路径长度d(s,u) 是从是从s 到到u的路径长度的路径长度 d(x,u) 是从是从x 到到u的路径长度的路径长度 则则 distx d(s,x)d(s,x)+d(x,u)=d(s,u)distu由于由于d(x,u) 0，所以所以distxdistu按照贪心选择策略，按照贪心选择策略，x不应该位于不应该位于S之外，之外，矛盾！矛盾！2021/5/2144计算复杂性计算复杂性 对于具有对于具有n n个顶点和个顶点和e e条边的带权有向图，条边的带权有向图，如果用带权邻接矩阵表示图，如果用带权邻接矩阵表示图，DijkstraDijkstra算算法的时间复杂度法的时间复杂度O(nO(n2 2) )。2021/5/21454.5 4.5 哈夫曼编码哈夫曼编码 abcdef字符使用频率字符使用频率4513121695固定长度的编码固定长度的编码000001010011100101变长编码变长编码010110011111011100如果文本中包含如果文本中包含100,000个字符，个字符，固定长度的编码：固定长度的编码：100,0003=300,000（位）（位）变长编码：变长编码：145,000+341,000+414,000=224,000（位）（位）结论：节省结论：节省25%2021/5/2146哈夫曼编码哈夫曼编码广泛应用于数据文件压缩中。其压缩广泛应用于数据文件压缩中。其压缩率通常在率通常在20%20%90%90%之间。哈夫曼编码算法用字符之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用在文件中出现的频率表来建立一个用0 0，1 1串表示串表示各字符的最优表示方式。给出现频率高的字符较各字符的最优表示方式。给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码，短的编码，出现频率较低的字符以较长的编码，可以大大缩短总码长。可以大大缩短总码长。 1. 1.前缀码前缀码对每一个字符规定一个对每一个字符规定一个0,10,1串作为其代码，并要求串作为其代码，并要求任一字符的代码都不是其他字符代码的前缀任一字符的代码都不是其他字符代码的前缀, ,称为称为前缀码前缀码。2021/5/2147 编码的前缀性质可以使译码方法非常简单。编码的前缀性质可以使译码方法非常简单。 可以采用可以采用二叉树表示前缀编码二叉树表示前缀编码，平均码长平均码长定义为：定义为：使平均码长达到最小的前缀码编码方案称使平均码长达到最小的前缀码编码方案称为给定编码字符集为给定编码字符集C C的的最优前缀码最优前缀码。 2021/5/2148n编码指：将文件中各个代表各个字符的编码连编码指：将文件中各个代表各个字符的编码连接起来。例如：接起来。例如：abc0 101 100 0101100n因为任何一个因为任何一个 编码码字都不是其他编码码字编码码字都不是其他编码码字的前缀，因此，的前缀，因此，解码解码一个文件的码字是明确一个文件的码字是明确的。例如的。例如: 001011101 0 0 101 1101 aaben解码过程解码过程需要一种方便的形式来表示前缀码，需要一种方便的形式来表示前缀码，二叉树就是一种好的表示方式。二叉树就是一种好的表示方式。2021/5/2149n二叉树作为前缀码的数据结构：树叶表示给二叉树作为前缀码的数据结构：树叶表示给定字符；从树根到树叶的路径当作该字符的定字符；从树根到树叶的路径当作该字符的前缀码；前缀码；n代码中每一位的代码中每一位的0 0或或1 1分别作为指示某节点到分别作为指示某节点到左儿子或右儿子的左儿子或右儿子的“路标路标”。n其中其中（a)a)为固定长度编码的二叉树表示；为固定长度编码的二叉树表示； （b)b)为变长编码的二叉树表示；为变长编码的二叉树表示； 00000110111a: 45c: 12d: 16e: 9f: 5b: 1558288614141000000011111c: 12a: 45d: 16e: 9f: 5b: 13142510055302021/5/2150 2. 2.构造哈夫曼编码构造哈夫曼编码哈夫曼提出构造最优前缀码的贪心算法，哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为由此产生的编码方案称为哈夫曼编码哈夫曼编码。哈夫曼算法以自底向上的方式构造表示最哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树优前缀码的二叉树T T。算法以算法以|C|C|个叶结点开始，执行个叶结点开始，执行|C|C|1 1次的次的“合并合并”运算后产生最终所要求的树运算后产生最终所要求的树T T。 2021/5/2151n假设假设编码字符集中每一字符编码字符集中每一字符c c的频率是的频率是f(c)f(c)。以以f f为键值的优先队列为键值的优先队列Q Q用在用在贪心选择贪心选择时时有效地确定算法当前要合并的有效地确定算法当前要合并的2 2棵具有最小棵具有最小频率的树。一旦频率的树。一旦2 2棵具有最小频率的树合并棵具有最小频率的树合并后，产生一棵新的树，其频率为合并的后，产生一棵新的树，其频率为合并的2 2棵棵树的频率之和，并将新树插入优先队列树的频率之和，并将新树插入优先队列Q Q。经过经过n n1 1次的合并后，优先队列中只剩下次的合并后，优先队列中只剩下一棵树，即所要求的树一棵树，即所要求的树T T。2021/5/2152（1）最优子结构性质）最优子结构性质 设设 x 和和 y 是二叉树是二叉树T中的两个叶子且兄弟，中的两个叶子且兄弟，z 是双亲。若将是双亲。若将 z 看作是具有看作是具有f(z) = f(x)+f(y)的字符，则树的字符，则树 T=T-x,y 表示字符集表示字符集 C=C-x,y z 的一个最优前缀编码。的一个最优前缀编码。 利用反证法证明利用反证法证明T是一个最优前缀编码是一个最优前缀编码。 2021/5/2153（2）贪心选择性质）贪心选择性质 令令 C 为一个字符表。对为一个字符表。对 cC，字符，字符 c在文件在文件中出现的频率为中出现的频率为f(c)。令。令 x 和和 y 为为 C 中出现中出现频率最小的两个字符，则对频率最小的两个字符，则对 C 存在一个最优存在一个最优前缀编码。在这个编码中，前缀编码。在这个编码中，x 和和 y 的编码长的编码长度最长，且长度相等，只有最后一位不同。度最长，且长度相等，只有最后一位不同。 假设有字符假设有字符b,c,x,y，其中，其中，x,y是具有最小频是具有最小频率率 的两个字符，且的两个字符，且f(b) f(c), f(x) f(y) 故故f(x) f(b), f(y) f(c)。2021/5/2154f(b) f(c), f(x) f(y) f(x) f(b), f(y) f(c)yxbcybxccbxy说明：贪心选说明：贪心选择得到最优前择得到最优前缀编码。缀编码。2021/5/2155f: 5e: 9d: 16c: 12b: 13a: 45c: 12e: 9d: 16f: 5b: 13a: 4514d: 16a: 45e: 9f: 514c: 12b: 1325a: 45c: 12b: 1325d: 16e: 9f: 51430a: 45c: 12b: 1325d: 16e: 9f: 51430550000011111c: 12a: 45d: 16e: 9f: 5b: 1314251005530哈夫曼编码举例2021/5/2156 (a)给出了每给出了每个字符出现的个字符出现的频率频率,并初始并初始化为一座森林。化为一座森林。然后，选择两然后，选择两个最小的节点个最小的节点x和和y，产生一，产生一个新节点个新节点z,从从而得到一棵新而得到一棵新的子树。的子树。2021/5/2157哈夫曼算法的正确性哈夫曼算法的正确性要证明哈夫曼算法的正确性，只要证明最优前缀码问题具有贪心选择性质贪心选择性质和最优子结构性质最优子结构性质。贪贪心心选选择择性性质质- -二叉树T表示字符集C的一个最优前缀码，证明可以对T作适当修改后得到一棵新的二叉树T”，在T”中x和y是最深叶子且为兄弟，同时T”表示的前缀码也是C的最优前缀码。最最优优子子结结构构性性质质- -二叉树T表示字符集C的一个最优前缀码，x和y是树T中的两个叶子且为兄弟，z是它们的父亲。若将z当作是具有频率f(z)=f(x)+f(y)的字符，则树T=T-x,y表示字符集C=C-x, y z的一个最优前缀码。2021/5/2158贪贪心心选选择择性性质质- -二叉树T表示字符集C的一个最优前缀码，证明可以对T作适当修改后得到一棵新的二叉树T”，在T”中x和y是最深叶子且为兄弟，同时T”表示的前缀码也是C的最优前缀码。xTycbbTycxbT ”cyx2021/5/21594.6 4.6 多机调度问题多机调度问题问题提出问题提出: :多机调度问题多机调度问题要求给出一种作业调度方要求给出一种作业调度方案，使所给的案，使所给的n n个作业在尽可能短的时间内由个作业在尽可能短的时间内由m m台台机器加工处理完成。机器加工处理完成。 约定约定: :每个作业均可在任何一台机器上加工处理，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更但未完工前不允许中断处理。作业不能拆分成更小的子作业。小的子作业。这个问题是这个问题是NPNP完全问题完全问题，到目前为止还没有有效，到目前为止还没有有效的解法。对于这一类问题的解法。对于这一类问题, ,用用贪心选择策略贪心选择策略有时可有时可以设计出较好的近似算法。以设计出较好的近似算法。2021/5/2160解决方案解决方案采用采用最长处理时间作业优先最长处理时间作业优先的贪心选择策略可的贪心选择策略可以设计出解多机调度问题的较好的近似算法。以设计出解多机调度问题的较好的近似算法。当当n=mnmnm 时，首先将时，首先将n n个作业依其所需的处理时个作业依其所需的处理时间从大到小排序。然后依此顺序将作业分配给间从大到小排序。然后依此顺序将作业分配给空闲的处理机。算法所需的计算时间为空闲的处理机。算法所需的计算时间为O(nlogn)O(nlogn)。2021/5/2161多机调度问题举例多机调度问题举例假设假设7 7个独立作业个独立作业1,2,3,4,5,6,71,2,3,4,5,6,7由由3 3台机器台机器M1M1，M2M2和和M3M3加工处理。各作业所需的处理时间分别为加工处理。各作业所需的处理时间分别为2,14,4,16,6,5,32,14,4,16,6,5,3。按算法。按算法greedygreedy产生的作业调度产生的作业调度如下图所示，所需的加工时间为如下图所示，所需的加工时间为1717。 2021/5/21624.7 4.7 最小生成树最小生成树 设设G =(V,E)G =(V,E)是无向连通带权图，即一个是无向连通带权图，即一个网络网络。E E中每中每条边条边(v,w)(v,w)的权为的权为cvwcvw。如果。如果G G的子图的子图G G是一棵包含是一棵包含G G的所有顶点的树，则称的所有顶点的树，则称G G为为G G的生成树。生成树上各边权的生成树。生成树上各边权的总和称为该生成树的的总和称为该生成树的耗费耗费。在。在G G的所有生成树中，耗费的所有生成树中，耗费最小的生成树称为最小的生成树称为G G的的最小生成树最小生成树。网络的最小生成树在实际中有广泛应用。网络的最小生成树在实际中有广泛应用。例如例如，在设，在设计通信网络时，用图的顶点表示城市，用边计通信网络时，用图的顶点表示城市，用边(v,w)(v,w)的权的权cvwcvw表示建立城市表示建立城市v v和城市和城市w w之间的通信线路所需的费之间的通信线路所需的费用，则最小生成树就给出了建立通信网络的最经济的方案。用，则最小生成树就给出了建立通信网络的最经济的方案。 2021/5/21631.1.最小生成树性质最小生成树性质用贪心算法设计策略可以设计出构造最小用贪心算法设计策略可以设计出构造最小生成树的有效算法。本节介绍的构造最小生成生成树的有效算法。本节介绍的构造最小生成树的树的PrimPrim算法算法和和KruskalKruskal算法算法都可以看作是应都可以看作是应用贪心算法设计策略的例子。尽管这用贪心算法设计策略的例子。尽管这2 2个算法个算法做贪心选择的方式不同，它们都利用了下面的做贪心选择的方式不同，它们都利用了下面的最小生成树性质最小生成树性质：设设G=(V,E)G=(V,E)是连通带权图，是连通带权图，U U是是V V的真子集。的真子集。如果如果(u,v)(u,v) E E，且，且u u U U，v v V-UV-U，且在所有这，且在所有这样的边中，样的边中，(u,v)(u,v)的权的权cuvcuv最小，那么一定最小，那么一定存在存在G G的一棵最小生成树，它以的一棵最小生成树，它以(u,v)(u,v)为其中一为其中一条边。这个性质有时也称为条边。这个性质有时也称为MSTMST性质性质。 2021/5/21642.Prim2.Prim算法算法 设设G=(V,E)G=(V,E)是连通带权图，是连通带权图，V=1,2,V=1,2,n,n。构造构造G G的最小生成树的的最小生成树的PrimPrim算法的算法的基本思想基本思想是：是：首先置首先置S=1S=1，然后，只要，然后，只要S S是是V V的真子集，就作如的真子集，就作如下的下的贪心选择：贪心选择：选取满足条件选取满足条件i i S S，j j V-SV-S，且，且cijcij最小的边，将顶点最小的边，将顶点j j添加到添加到S S中。这个过程中。这个过程一直进行到一直进行到S=VS=V时为止。时为止。在这个过程中选取到的所有边恰好构成在这个过程中选取到的所有边恰好构成G G的一的一棵棵最小生成树最小生成树。 2021/5/2165利用最小生成树性质利用最小生成树性质和数学归纳法容易证明，和数学归纳法容易证明，上述算法中的上述算法中的边集合边集合T T始始终包含终包含G G的某棵最小生成的某棵最小生成树中的边树中的边。因此，在算法。因此，在算法结束时，结束时，T T中的所有边构中的所有边构成成G G的一棵最小生成树。的一棵最小生成树。 例如例如，对于右图中的，对于右图中的带权图，按带权图，按PrimPrim算法算法选取选取边的过程如下页图所示。边的过程如下页图所示。2021/5/21662021/5/2167在上述在上述PrimPrim算法中，还应当考虑算法中，还应当考虑如何有效地如何有效地找出满足条件找出满足条件i i S,jS,j V-SV-S，且权，且权cijcij最小的最小的边边(i,j)(i,j)。实现这个目的的较简单的办法是设置。实现这个目的的较简单的办法是设置2 2个数组个数组closestclosest和和lowcostlowcost。在在PrimPrim算法执行过程中，先找出算法执行过程中，先找出V-SV-S中使中使lowcostlowcost值最小的顶点值最小的顶点j j，然后根据数组，然后根据数组closestclosest选取边选取边(j,closestj(j,closestj) )，最后将，最后将j j添加到添加到S S中，中，并对并对closestclosest和和lowcostlowcost作必要的修改。作必要的修改。用这个办法实现的用这个办法实现的PrimPrim算法所需的算法所需的计算时间计算时间为为 2021/5/21683.Kruskal3.Kruskal算法算法KruskalKruskal算法构造算法构造G G的最小生成树的的最小生成树的基本思想基本思想是，首先将是，首先将G G的的n n个顶点看成个顶点看成n n个孤立的连通分支。个孤立的连通分支。将所有的边按权从小到大排序。然后从第一条边将所有的边按权从小到大排序。然后从第一条边开始，依边权递增的顺序查看每一条边，并按下开始，依边权递增的顺序查看每一条边，并按下述方法连接述方法连接2 2个不同的连通分支：当查看到第个不同的连通分支：当查看到第k k条条边边(v,w)(v,w)时，如果端点时，如果端点v v和和w w分别是当前分别是当前2 2个不同的个不同的连通分支连通分支T1T1和和T2T2中的顶点时，就用边中的顶点时，就用边(v,w)(v,w)将将T1T1和和T2T2连接成一个连通分支，然后继续查看第连接成一个连通分支，然后继续查看第k+1k+1条边；如果端点条边；如果端点v v和和w w在当前的同一个连通分支中在当前的同一个连通分支中，就直接再查看第，就直接再查看第k+1k+1条边。这个过程一直进行条边。这个过程一直进行到只剩下一个连通分支时为止。到只剩下一个连通分支时为止。 2021/5/2169例如，例如，对前面的连通带权图，按对前面的连通带权图，按KruskalKruskal算法顺序得到的最小生成树上的边如下图所算法顺序得到的最小生成树上的边如下图所示。示。2021/5/2170总结总结p如果问题具有最优子结构且贪心选择如果问题具有最优子结构且贪心选择性质，贪心算法通过逐步地局部贪心性质，贪心算法通过逐步地局部贪心选择能够快速地得到问题的最优解。选择能够快速地得到问题的最优解。p如果不具有最优子结构或贪心选择性如果不具有最优子结构或贪心选择性质，利用贪心算法得不到最优解。然质，利用贪心算法得不到最优解。然而，对有些问题求解的速度快，质量而，对有些问题求解的速度快，质量也不错。也不错。2021/5/2171本章上机作业本章上机作业 利用利用huffmanhuffman编码对文本文件进行压缩与解压。编码对文本文件进行压缩与解压。 输入：一个文本文件输入：一个文本文件 输出：压缩后的文件输出：压缩后的文件 算法过程：算法过程： （1 1）统计文本文件中每个字符的使用频度）统计文本文件中每个字符的使用频度 （2 2）构造）构造huffmanhuffman编码编码 （3 3）以二进制流形式压缩文件）以二进制流形式压缩文件2021/5/2172部分资料从网络收集整理而来，供大家参考，感谢您的关注！