1、1第第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 多机调度问题多机调度问题2贪心算法贪心算法n顾名思义，贪心算法总是作出在当前看来最好顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的虑，它所作出的选择只是在某种意义上的局部局部最优最优选择。当然，希望贪心算法得到的最终结选择。当然
2、，希望贪心算法得到的最终结果也是整体最优的。果也是整体最优的。n虽然贪心算法不能对所有问题都得到整体最优虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。其最终结果却是最优解的很好近似。3例：用贪心法求解付款问题。例：用贪心法求解付款问题。假设有面值为假设有面值为5元、元、2元、元、1元、元、5角、角、2角、角、1角的角的货币，需要找给
3、顾客货币，需要找给顾客4元元6角现金，为使付出的货角现金，为使付出的货币的数量最少，首先选出币的数量最少，首先选出1张面值不超过张面值不超过4元元6角的角的最大面值的货币，即最大面值的货币，即2元，再选出元，再选出1张面值不超过张面值不超过2元元6角的最大面值的货币，即角的最大面值的货币，即2元，再选出元，再选出1张面值张面值不超过不超过6角的最大面值的货币，即角的最大面值的货币，即5角，再选出角，再选出1张张面值不超过面值不超过1角的最大面值的货币，即角的最大面值的货币，即1角，总共角，总共付出付出4张货币。张货币。4 在付款问题每一步的贪心选择中，在不超在付款问题每一步的贪心选择中，在不超
4、过应付款金额的条件下，只选择面值最大过应付款金额的条件下，只选择面值最大的货币，而不去考虑在后面看来这种选择的货币，而不去考虑在后面看来这种选择是否合理，而且它还不会改变决定：一旦是否合理，而且它还不会改变决定：一旦选出了一张货币，就永远选定。付款问题选出了一张货币，就永远选定。付款问题的贪心选择策略是尽可能使付出的货币最的贪心选择策略是尽可能使付出的货币最快地满足支付要求，其目的是使付出的货快地满足支付要求，其目的是使付出的货币张数最慢地增加，这正体现了贪心法的币张数最慢地增加，这正体现了贪心法的设计思想。设计思想。5贪心算法的设计思路贪心算法的设计思路 贪心算法的设计思路是：总是做出贪心算
5、法的设计思路是：总是做出在当前看来最好的选择，即在当前看来最好的选择，即贪心算贪心算法并不是从整体最优考虑法并不是从整体最优考虑，它所做，它所做的选择只是在某种意义上的的选择只是在某种意义上的局部最局部最优选择优选择。6Greedy(A,n)/A为输入集合为输入集合 solution=;/解空间初始化为空解空间初始化为空 for(i=1;i=n;i+)/对每个输入进行检测对每个输入进行检测 x=select(A);/选择一个输入选择一个输入 if(feasible(solution,x)/如果可行如果可行 solution=union(solution,x);/添至解空间添至解空间 retur
6、n solution;74.1 4.1 贪心算法的基本要素贪心算法的基本要素 利用贪心算法求解最优解的两个前提条件利用贪心算法求解最优解的两个前提条件:贪心选择性质贪心选择性质和和最优子结构性质最优子结构性质。1.1.贪心选择性质贪心选择性质 所谓所谓贪心选择性质贪心选择性质是指所求问题的是指所求问题的整体最优解整体最优解可以通过一系列可以通过一系列局部最优局部最优的选择，即贪心选择的选择，即贪心选择来达到。这是利用贪心算法求解最优解的第一来达到。这是利用贪心算法求解最优解的第一个基本要素，也是贪心算法与动态规划算法的个基本要素，也是贪心算法与动态规划算法的主要区别。主要区别。8 2.2.最优
7、子结构性质最优子结构性质 当一个问题的最优解包含其子问题的最优解时，当一个问题的最优解包含其子问题的最优解时，称此问题具有称此问题具有最优子结构性质最优子结构性质。问题的最优子。问题的最优子结构性质是该问题可用动态规划算法或贪心算结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。法求解的关键特征。9 3.3.贪心算法与动态规划算法的差异贪心算法与动态规划算法的差异 共同点共同点：求解的问题都具有最优子结构性质：求解的问题都具有最优子结构性质差异点差异点：动态规划算法通常以动态规划算法通常以自底向上自底向上的方式的方式解各子问题，而贪心算法则通常以解各子问题，而贪心算法则通常以自顶向下自
8、顶向下的的方式进行，以迭代的方式作出相继的贪心选择，方式进行，以迭代的方式作出相继的贪心选择，每做一次贪心选择就将所求问题简化为规模更每做一次贪心选择就将所求问题简化为规模更小的子问题。小的子问题。10 0-10-1背包问题：背包问题：给定给定n n种物品和一个背包。物品种物品和一个背包。物品i i的重量是的重量是W Wi i，其价值为，其价值为V Vi i，背包最大承载重量为背包最大承载重量为C C。应如何选择装入背包的物品，使。应如何选择装入背包的物品，使得装入背包中物品的总价值最大得装入背包中物品的总价值最大?在选择装入背包的物品时，对每种物品在选择装入背包的物品时，对每种物品i i只有
9、只有2 2种选择，种选择，即装入背包或不装入背包。不能将物品即装入背包或不装入背包。不能将物品i i装入背包多装入背包多次，也不能只装入部分的物品次，也不能只装入部分的物品i i。背包问题背包问题：与与0-10-1背包问题类似，所不同的是在选择物品背包问题类似，所不同的是在选择物品i i装入背装入背包时，包时，可以选择物品可以选择物品i i的一部分的一部分，而不一定要全部装入，而不一定要全部装入背包，背包，1in1in。110-1背包与背包问题都具有最优子结构背包与背包问题都具有最优子结构 已知背包最大承载重量为已知背包最大承载重量为C，共有，共有n个物品，个物品，每个物品的重量分别为每个物品
10、的重量分别为Wi(i=1,2,.,n)，价值，价值为为Vi(i=1,2,.n)。证明证明：假设第假设第k个物品是最优解中的一个物品个物品是最优解中的一个物品，则，则 从中拿出从中拿出W Wk k对应的物品后所对应的解一定是对应的物品后所对应的解一定是其余其余n-1n-1个物品，装入背包最大承载重量为个物品，装入背包最大承载重量为C-WC-Wk k的最优解，否则与假设矛盾。的最优解，否则与假设矛盾。12l0-10-1背包问题不具有贪心选择性质背包问题不具有贪心选择性质。原因是无法保证能够将背包装满，原因是无法保证能够将背包装满，而所剩空间将会降低总价值。而所剩空间将会降低总价值。l背包问题具有贪
11、心选择性质背包问题具有贪心选择性质。130-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最优解最优解14背包问题具有贪心选择特性背包问题具有贪心选择特性物品物品1 11010公斤，
12、价值公斤，价值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公斤公斤15用贪心算法解背包问题的基本步骤：用贪心算法解背包问题的基本步骤：1.1.计算每种物品单位重量的价值计算每种物品单位重量的价值V Vi i/W/Wi i；2.2.按照单位重量的价值从高到低的顺序排序；按照单位
13、重量的价值从高到低的顺序排序；3.3.依据贪心选择策略，按照单位价值从高到低依据贪心选择策略，按照单位价值从高到低的顺序，依次将尽可能多的物品装入背包中。的顺序，依次将尽可能多的物品装入背包中。直到背包装满为止。直到背包装满为止。是否可以将物品装入背包的条件是：是否可以将物品装入背包的条件是：有空间有空间16背包问题的贪心算法背包问题的贪心算法void knapsack(float c,float w,float v,float x,int n)将各种物品依其单位重量的价值从高到低排序将各种物品依其单位重量的价值从高到低排序 初始化初始化 xi=0;for(i=0;in;i+)/贪心选择贪心选
14、择 if(不能放不能放)break;放入背包中放入背包中 if(背包没满背包没满&还有物品还有物品)装满装满;return opt;wiwi重量重量vivi单位价值单位价值xixi结果结果17背包问题的贪心算法背包问题的贪心算法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.
15、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:184.2 4.2 活动安排问题活动安排问题 设
16、有设有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|与假设矛盾！与假设矛盾！21 令子问题令子问题Sij 且且a1为子问题为子问题Sij中具有最中具有最早完成时间的任务，则早完成时间的任务，则a1一定包含在子
17、一定包含在子问题问题Sij中某个任务相互兼容的最大子集中某个任务相互兼容的最大子集中。中。结论：结论：具有贪心选择特性。具有贪心选择特性。（2）活动安排具有贪心选择特性）活动安排具有贪心选择特性22证明：证明：假设子问题假设子问题Sij的最优解为的最优解为Aij，其中的任，其中的任务按照完成时间由小到大排列；且第一个务按照完成时间由小到大排列；且第一个任务为任务为ak。如果。如果ak=a1，成立。，成立。如果如果ak a1，由于，由于a1完成时间较完成时间较ak早，所早，所以，可以将以，可以将ak去掉，换成去掉，换成a1，仍然相容，仍然相容，所含任务数量一样。所含任务数量一样。23活动安排问题
18、举例活动安排问题举例 假设待安排的假设待安排的1111个活动的开始时间和结束时个活动的开始时间和结束时间按结束时间的非减序排列如下：间按结束时间的非减序排列如下：i1234567891011Si130535688212fi4567891011121314若被检查的活动若被检查的活动i i的开始时间的开始时间S Si i小于最近小于最近选择的活动选择的活动j j的结束时间的结束时间f fi i，则不选择活，则不选择活动动i i，否则选择活动，否则选择活动i i加入集合加入集合A A中中24 图中每行相应于算法图中每行相应于算法的一次迭代。的一次迭代。阴影长阴影长条条表示的活动是已选表示的活动是已
19、选入集合入集合A A的活动，而的活动，而空白长条空白长条表示的活动表示的活动是当前正在检查相容是当前正在检查相容性的活动。性的活动。i1234567891011Si130535688212fi456789101112131425isifi11423530645753865976108811981210213111214012345678910 1112 13 14结果：选中的任务为：结果：选中的任务为：1 1、4 4、8 8、111126解活动安排问题的贪心算法解活动安排问题的贪心算法int greedySelector(int s,int f,boolean a,int n)a1=true;
20、/初始化初始化 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中且按结束时间中且按结束时间的非减序排列的非减序排列 27 假设输入的活动以其完成时间的假设输入的活动以其完成时间的非减序非减序排列，排列，则算法则算法greedySelectorgreedySelector总选择总选择最早完成时间最早完成时间的相容活动加入集合的相容活动加入集合A A中。该算法的贪心选择中。该算法的贪心选择的意义是的意
21、义是使剩余的可安排时间段极大化使剩余的可安排时间段极大化，以，以便安排尽可能多的相容活动。便安排尽可能多的相容活动。算法算法greedySelectorgreedySelector的效率极高。当输入的的效率极高。当输入的活动已按结束时间的非减序排列，算法只需活动已按结束时间的非减序排列，算法只需O(n)O(n)的时间安排的时间安排n n个活动，使最多的活动能相个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按容地使用公共资源。如果所给出的活动未按非减序排列，可以用非减序排列，可以用O(nlogn)O(nlogn)的时间重排。的时间重排。284.3 4.3 最优装载最优装载 有一批集
22、装箱要装上一艘载重量为有一批集装箱要装上一艘载重量为c c的的轮船。其中，集装箱轮船。其中，集装箱i i的重量为的重量为W Wi i。最。最优装载问题要求确定优装载问题要求确定在装载体积不受限在装载体积不受限制的情况下制的情况下，将，将尽可能多尽可能多的集装箱装上的集装箱装上轮船。轮船。29 最优装载问题可用贪心算法求解。采用重最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略，可产生最量最轻者先装的贪心选择策略，可产生最优装载问题的最优解。优装载问题的最优解。maxniix1niiiw xc1,ixin 0 1 130(1)(1)最优子结构的性质最优子结构的性质 设设 (x(x1
23、 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时相应最优装载时相应最优装载问题的最优解。问题的最优解。利用反证法证明。利用反证法证明。31(2)(2)贪心选择性质贪心选择性质 设集装箱依重量从小到大排序，设集装箱依重量从小到大排序，(x(x1 1,x,x2 2,.,x,.,xn n)是最优装载问题的一个最优解。设是最优装载问题的一个最优解。设x:(
24、0 x:(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）nnniikiiiiiiiw ywww xw xc11111|min1inixik32最优装载贪心算法最优装载贪心算法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
25、&di.w=c;i+)/贪心选择贪心选择 xdi.i=1;opt+=di.w;c-=di.w;return opt;typedef struct float w;int i;ITEMTYPE;33344.4 4.4 单源最短路径单源最短路径问题提出问题提出:给定带权有向图给定带权有向图G=(V,E)G=(V,E)，其中每，其中每条边的权是非负实数。另外，还给定条边的权是非负实数。另外，还给定V V中的一中的一个顶点，称为个顶点，称为源源。现在要计算从源到所有其他。现在要计算从源到所有其他各顶点的各顶点的最短路经长度最短路经长度。这里路径长度是指路。这里路径长度是指路上各边权之和。这个问题通常称
26、为上各边权之和。这个问题通常称为单源最短路单源最短路径问题径问题。35v0v0v1v1:无无v0v0v2v2:10:10v0 v0 v4 v4 v3v3:50:50v0 v0 v4v4:30:30v0 v0 v4 v4 v3 v3 v5v5:60:60v0v1v2v3v4v5100603020105051036（1 1）DijkstraDijkstra算法算法DijkstraDijkstra算法是解单源最短路径问题的算法是解单源最短路径问题的贪心算法贪心算法。其。其基本思想基本思想是设置一个已经是设置一个已经确定最短路径的顶点集合确定最短路径的顶点集合S S，并通过不断，并通过不断地地贪心选择
27、贪心选择来扩充这个集合。一个顶点来扩充这个集合。一个顶点属于集合属于集合S S当且仅当从源到该顶点的最短当且仅当从源到该顶点的最短路径长度已知。路径长度已知。37DijkstraDijkstra算法基本过程算法基本过程初始时，初始时，S S中仅含有源。设中仅含有源。设u u是是V-SV-S中的一个顶中的一个顶点。把从源到点。把从源到u u且中间只经过且中间只经过S S中顶点的路称为中顶点的路称为从源到从源到u u的的特殊路径特殊路径，并用数组，并用数组distdist记录当前记录当前每个顶点所对应的最短特殊路径长度。每个顶点所对应的最短特殊路径长度。uSV-S38DijkstraDijkstr
28、a算法基本过程算法基本过程DijkstraDijkstra算法每次从算法每次从V-SV-S中取出具有中取出具有最短特殊最短特殊路长度路长度的顶点的顶点u u，将，将u u添加到添加到S S中，同时对数组中，同时对数组distdist作必要的修改。一旦作必要的修改。一旦S S包含了所有包含了所有V V中顶点，中顶点，distdist就记录了从源到所有其他顶点之间的最短就记录了从源到所有其他顶点之间的最短路径长度。路径长度。uV-SS39DijkstraDijkstra算法的迭代过程算法的迭代过程迭代迭代S Su udist2dist2 dist3dist3 dist4dist4 dist5dis
29、t5初始初始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 5101050503030606040算法算法 置置S S为空；为空；将源点将源点v v0 0加入加入S S；初始化初始化distdist，即对每个非源点，即对每个非源点i i令令distidisti为边为边的权，不存在令的权，不存在令distidisti为为。while(Swhile(S中没
30、有包含全部顶点中没有包含全部顶点)/贪心选择贪心选择 选择选择V-SV-S结点结点u u，distu=mindistv|vV-S distu=mindistv|vV-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);41（2）DijkstraDijkstra算法具有算法具有最优子结构性质最优子结构性质 证明算法中每步确定的证明算法中每步确定的disti是当前从源点到顶是当前从源点到顶点点i的最短的最短特殊路径特殊路径长度。长度。证明证
31、明：采用数学归纳法。：采用数学归纳法。当当|S|=1时，显然成立。时，显然成立。假设在第假设在第k次贪心选择之前次贪心选择之前disti存放着从源点到存放着从源点到顶点顶点i的最短特殊路径长度。的最短特殊路径长度。需要证明（第需要证明（第k+1次贪心选择）：根据贪心选择次贪心选择）：根据贪心选择策略，将顶点策略，将顶点u添加到添加到S之后，之后，disti仍然是当前仍然是当前从源点到顶点从源点到顶点i的最短特殊路径长度。的最短特殊路径长度。42Susix假设根据贪心选择策略，第假设根据贪心选择策略，第k+1选选择将顶点择将顶点u添加到添加到S中，对于顶点中，对于顶点i可能会增加一条从源点到达顶
32、点可能会增加一条从源点到达顶点i的的新的特殊路径。新的特殊路径。这条新的特殊路径由两种可能：这条新的特殊路径由两种可能：情况情况1：这条路径先由源点到达顶点：这条路径先由源点到达顶点u，再由顶点，再由顶点u直接直接到达到达i，则这条，则这条特殊路径特殊路径的长度为：的长度为：distu+aui如果这条路径更短，替换如果这条路径更短，替换disti；否则不变。；否则不变。43Susix情况情况2：如果新增加的特殊路径先：如果新增加的特殊路径先由源点到达顶点由源点到达顶点u，再由顶点，再由顶点u途径途径另一顶点另一顶点x到达到达i。由于。由于x早早于于u进入进入S中，所以中，所以distxdist
33、u,即即distx+axi distu+aux+axi，故：这条新特殊路径不会影响故：这条新特殊路径不会影响disti，因此不需，因此不需要考虑。要考虑。结论：在任何时候，结论：在任何时候，disti都存放着当前从源点都存放着当前从源点到到i点的最短特殊路径长度。点的最短特殊路径长度。44（3）Dijkstra Dijkstra算法具有算法具有贪心选择性质贪心选择性质 按照贪心选择方式得到的按照贪心选择方式得到的distudistu一定是从源一定是从源点点s s到顶点到顶点u u的最短路径长度。的最短路径长度。证明：假设存在一条从源点证明：假设存在一条从源点s s到到u u的更短路径。的更短路
34、径。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之外，之外，矛盾！矛盾！45计算复杂性计算复杂性 对于具有对于具有n n个顶点和个顶点和e e条边的带权有向图，条边的带权有向图，如果用带权邻接矩阵表示图，如果用带权邻接矩阵表示图，DijkstraDijkstra算算法的时间复杂度法的时间复
35、杂度O(nO(n2 2)。464.5 4.5 哈夫曼编码哈夫曼编码abcdef字符使用频率字符使用频率4513121695固定长度的编码固定长度的编码000001010011100101变长编码变长编码010110011111011100如果文本中包含如果文本中包含100,000个字符，个字符，固定长度的编码：固定长度的编码：100,0003=300,000（位）（位）变长编码：变长编码：145,000+341,000+414,000=224,000（位）（位）结论：节省结论：节省25%47哈夫曼编码哈夫曼编码广泛应用于数据文件压缩中。其压缩广泛应用于数据文件压缩中。其压缩率通常在率通常在20
36、%20%90%90%之间。哈夫曼编码算法用字符之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用在文件中出现的频率表来建立一个用0 0，1 1串表示串表示各字符的最优表示方式。给出现频率高的字符较各字符的最优表示方式。给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码，短的编码，出现频率较低的字符以较长的编码，可以大大缩短总码长。可以大大缩短总码长。1.1.前缀码前缀码对每一个字符规定一个对每一个字符规定一个0,10,1串作为其代码，并要求串作为其代码，并要求任一字符的代码都不是其他字符代码的前缀任一字符的代码都不是其他字符代码的前缀,称为称为前缀码前缀码。48 编码的前缀性
37、质可以使译码方法非常简单。编码的前缀性质可以使译码方法非常简单。可以采用可以采用二叉树表示前缀编码二叉树表示前缀编码，平均码长平均码长定义为：定义为：使平均码长达到最小的前缀码编码方案称使平均码长达到最小的前缀码编码方案称为给定编码字符集为给定编码字符集C C的的最优前缀码最优前缀码。)()()(cdcfTBTCc 49n编码指：将文件中各个代表各个字符的编码编码指：将文件中各个代表各个字符的编码连接起来。例如：连接起来。例如：abc0 101 100 0101100n因为任何一个因为任何一个 编码码字都不是其他编码码字编码码字都不是其他编码码字的前缀，因此，的前缀，因此，解码解码一个文件的码
38、字是明确一个文件的码字是明确的。例如的。例如:001011101 0 0 101 1101 aaben解码过程解码过程需要一种方便的形式来表示前缀码需要一种方便的形式来表示前缀码，二叉树就是一种好的表示方式。，二叉树就是一种好的表示方式。50n二叉树作为前缀码的数据结构：树叶表示给二叉树作为前缀码的数据结构：树叶表示给定字符；从树根到树叶的路径当作该字符的定字符；从树根到树叶的路径当作该字符的前缀码；前缀码；n代码中每一位的代码中每一位的0 0或或1 1分别作为指示某节点到分别作为指示某节点到左儿子或右儿子的左儿子或右儿子的“路标路标”。n其中其中（a)a)为固定长度编码的二叉树表示；为固定长
39、度编码的二叉树表示；（b)b)为变长编码的二叉树表示；为变长编码的二叉树表示；00000110111a:45c:12d:16e:9f:5b:1558288614141000000011111c:12a:45d:16e:9f:5b:131425100553051 2.2.构造哈夫曼编码构造哈夫曼编码哈夫曼提出构造最优前缀码的贪心算法，哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为由此产生的编码方案称为哈夫曼编码哈夫曼编码。哈夫曼算法以自底向上的方式构造表示最哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树优前缀码的二叉树T T。算法以算法以|C|C|个叶结点开始，执行个叶结点开始
40、，执行|C|C|1 1次的次的“合并合并”运算后产生最终所要求的树运算后产生最终所要求的树T T。52n假设假设编码字符集中每一字符编码字符集中每一字符c c的频率是的频率是f(c)f(c)。以以f f为键值的优先队列为键值的优先队列Q Q用在用在贪心选择贪心选择时时有效地确定算法当前要合并的有效地确定算法当前要合并的2 2棵具有最小棵具有最小频率的树。一旦频率的树。一旦2 2棵具有最小频率的树合并棵具有最小频率的树合并后，产生一棵新的树，其频率为合并的后，产生一棵新的树，其频率为合并的2 2棵棵树的频率之和，并将新树插入优先队列树的频率之和，并将新树插入优先队列Q Q。经过经过n n1 1次
41、的合并后，优先队列中只剩下次的合并后，优先队列中只剩下一棵树，即所要求的树一棵树，即所要求的树T T。53（1）最优子结构性质）最优子结构性质 设设 x 和和 y 是二叉树是二叉树T中的两个叶子且兄弟，中的两个叶子且兄弟，z 是双亲。若将是双亲。若将 z 看作是具有看作是具有f(z)=f(x)+f(y)的字符，则树的字符，则树 T=T-x,y 表示字符集表示字符集 C=C-x,y z 的一个最优前缀编码。的一个最优前缀编码。利用反证法证明利用反证法证明T是一个最优前缀编码是一个最优前缀编码。54（2）贪心选择性质）贪心选择性质 令令 C 为一个字符表。对为一个字符表。对 cC，字符，字符 c在
42、文件在文件中出现的频率为中出现的频率为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)。55f(b)f(c),f(x)f(y)f(x)f(b),f(y)f(c)yxbcybxcc
43、bxy说明：贪心选说明：贪心选择得到最优前择得到最优前缀编码。缀编码。56f: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哈夫曼编码举例57(a)给出了每给出了每个字符出现个字符出现的频率的频率,并初并初始化为一座始化为一座森林。然后，森林。然后，选择两个最选择两个最小的节点小的节点x和和y，产生一个
44、，产生一个新节点新节点z,从而从而得到一棵新得到一棵新的子树。的子树。58哈夫曼算法的正确性哈夫曼算法的正确性要证明哈夫曼算法的正确性，只要证明最优前缀码问题具有贪心选择性质贪心选择性质和最优子结构性质最优子结构性质。贪心选择性质贪心选择性质-二叉树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表示
45、字符集C=C-x,y z的一个最优前缀码。59贪心选择性质贪心选择性质-二叉树T表示字符集C的一个最优前缀码，证明可以对T作适当修改后得到一棵新的二叉树T”，在T”中x和y是最深叶子且为兄弟，同时T”表示的前缀码也是C的最优前缀码。xTycbbTycxbT”cyx()()()()()()0()()()TTB TB Tf bf xdbdxB TB TB T()()B TB T()()B TB T604.6 4.6 多机调度问题多机调度问题问题提出问题提出:多机调度问题多机调度问题要求给出一种作业调度方要求给出一种作业调度方案，使所给的案，使所给的n n个作业在尽可能短的时间内由个作业在尽可能短的
46、时间内由m m台台机器加工处理完成。机器加工处理完成。约定约定:每个作业均可在任何一台机器上加工处理，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更但未完工前不允许中断处理。作业不能拆分成更小的子作业。小的子作业。这个问题是这个问题是NPNP完全问题完全问题，到目前为止还没有有效，到目前为止还没有有效的解法。对于这一类问题的解法。对于这一类问题,用用贪心选择策略贪心选择策略有时可有时可以设计出较好的近似算法。以设计出较好的近似算法。61解决方案解决方案采用采用最长处理时间作业优先最长处理时间作业优先的贪心选择策略可的贪心选择策略可以设计出解多机调度问题的较好的
47、近似算法。以设计出解多机调度问题的较好的近似算法。当当n=mnmnm 时，首先将时，首先将n n个作业依其所需的处理时个作业依其所需的处理时间从大到小排序。然后依此顺序将作业分配给间从大到小排序。然后依此顺序将作业分配给空闲的处理机。算法所需的计算时间为空闲的处理机。算法所需的计算时间为O(nlogn)O(nlogn)。62多机调度问题举例多机调度问题举例假设假设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
48、,14,4,16,6,5,3。按算法。按算法greedygreedy产生的作业调度产生的作业调度如下图所示，所需的加工时间为如下图所示，所需的加工时间为1717。634.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的所有生成树
49、中，耗费的所有生成树中，耗费最小的生成树称为最小的生成树称为G G的的最小生成树最小生成树。网络的最小生成树在实际中有广泛应用。网络的最小生成树在实际中有广泛应用。例如例如，在设，在设计通信网络时，用图的顶点表示城市，用边计通信网络时，用图的顶点表示城市，用边(v,w)(v,w)的权的权cvwcvw表示建立城市表示建立城市v v和城市和城市w w之间的通信线路所需的费之间的通信线路所需的费用，则最小生成树就给出了建立通信网络的最经济的方案用，则最小生成树就给出了建立通信网络的最经济的方案。641.1.最小生成树性质最小生成树性质用贪心算法设计策略可以设计出构造最小用贪心算法设计策略可以设计出构
50、造最小生成树的有效算法。本节介绍的构造最小生成生成树的有效算法。本节介绍的构造最小生成树的树的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
