算法设计-第4章

第4章贪心算法1学习要点理解贪心算法的概念。掌握贪心算法的基本要素（1）最优子结构性质（2）贪心选择性质理解贪心算法与动态规划算法的差异理解贪心算法的一般理论通过应用范例学习贪心设计策略。（1）活动安排问题；（2）最优装载问题；（3）哈夫曼编码；（4）单源最短路径；（5）最小生成树；（6）多机调度问题。2 贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。3基本思想通过作出在当前看来最优的选择（贪心选择），将原问题规模缩小，如此反复，直至得到最终解。贪心算法并非对所有问题都能得到整体最优解。4例4.1设有4种硬币，它们的面值分别为1角，5分，2分和1分。现在要找给某顾客3角7分钱。此时我们会不假思索地拿出3个1角，1个5分和1个2分的硬币交给顾客，这种找法与其他找法相比，拿出的硬币的个数时最少的。

找硬币算法：首先选出一个面值不超过3角7分的最大硬币（1角）然后从3角7分中减去1角，剩余2角7分再选出一个不超过2角7分的最大硬币（另一个1角），…，直到找足3角7分。第4章贪心算法5voidzhao(int*p,intn){

inti=1;

while(n!=0){

if(n>=p[i]){

printf("%d",p[i]);n=n-p[i];}elsei++;}}6这个找硬币的算法就是贪心算法：总是作出在当前看来是最好的选择，即贪心算法并不是从总体最优上加以考虑，它所作的选择只是在某种意义上的局部最优选择。找硬币问题本身最优原理成立，可以用动态规划方法求解，但用贪心算法更简单，直接且解题效率更高。这利用了问题本身的特性。7动态规划算法： 使用dp，关键是找出递归方程，而该问题可以提炼出递归方程如下（令C(t)表示要找t元用的最少硬币数，di表示币种）： 当求解总面值为t的找零最少硬币数c[t]时，将其分解成求解c[t

–di]和一个面值为

di

元的硬币，由于t

–di<t，其解c[t

–di]已经存在，如果面值为di

的硬币满足题意，那么最终解c[t]则等于c[t

–di]再加上1（即面值为di）的这一个硬币。

C(t)=min{1+C(t-di),c(di)}

据此，C++程序为：

//data[0]~data[n-1]存币种，已排序（升序），要找total元

8int

dpCoin(int*data,int

n,inttotal){

if(total<data[0])returnINT_MAX;

int*tmp=newint[total+1];

//存下所有C(t)

intt=0;

for(inti=data[0];i<=total;++i){

if(t<n&&i==data[t]){

tmp[i]=1;

++t;

}

else{

//C(t)=min{1+C(t-di),di<=t,1<=i<=n}

tmp[i]=INT_MAX;

for(intk=0;k=data[0]&&tmp[i-data[k]]!=INT_MAX;++k){

intj=1+tmp[i-data[k]];

if(j<tmp[i])tmp[i]=j;

}

}

}

intresult=tmp[total];

delete[]tmp;

returnresult;

//返回INT_MAX表示不能找

}9例4.2删数字问题对给定的n位高精度正整数,去掉其中k(k<n)个数字后，按原左右次序将组成一个新的正整数，使得剩下的数字组成的新数最大。操作对象是一个可以超过有效数字位数的n位高精度数,存储在数组a中。每次删除一个数字,选择一个使剩下的数最大的数字作为删除对象。之所以选择这样“贪心”的操作,是因为删k个数字的全局最优解包含了删一个数字的子问题的最优解。当k=1时,在n位整数中删除哪一个数字能达到最大的目的?从左到右每相邻的两个数字比较:若出现增,即左边小于右边,则删除左边的小数字。若所有数字全部降序,则删除最右边的数字。10当k>1(当然小于n),按上述操作一个一个删除。删除一个达到最大后,再从头即从串首开始,删除第2个,依此分解为k次完成。若删除不到k个后已无左边小于右边的增序,则停止删除操作,打印剩下串的左边n-k个数字即可（相当于删除了若干个最右边的数字）11贪心法也是一个多步决策法。每一步选择都使得能构成问题的一个可行解，同时使目标函数的值增加最快（求max）或增加最小（如求min），这种选择过程是以某些最优量度为根据，而最优化量度有时可以是目标函数本身，也可以是别的量度。最优化度量的选择是贪心算法的关键。124.1活动安排问题

活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。134.1活动安排问题

设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si

<fi。如果选择了活动i，则它在半开时间区间[si,fi)内占用资源。若区间[si,fi)与区间[sj,fj)不相交，则称活动i与活动j是相容的。也就是说，当si≥fj或sj≥fi时，活动i与活动j相容。14贪心算法GreedySelector（活动安排）中，各活动的开始时间和结束时间分别存储于数组S和f中且按结束时间的非减序：排列（量度标准）。如果所给出的活动未按此序排列，可用O(nlogn)的时间重排。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。15活动安排问题贪心解法：将所有活动按结束时间的非减序排序，得到活动集合E={e1,e2…en}；先将e1选入结果集合A中，即A={e1}；依次扫描每一个活动ei：如果ei的开始时间晚于最后一个选入A的活动ej的结束时间，则将ei选入A中，否则放弃ei；16活动安排问题解法证明：若E={e1,e2…en}是按结束时间排序的活动集合，则e1具有最早的结束时间，设存在一个最优安排A不包含e1，并以ei开始，则易见：

A-{ei}∪{e1}也是最优的活动安排；

依此类推。174.1活动安排问题template<classType>voidGreedySelector(intn,Types[],Typef[],boolA[]){A[1]=true;

intj=1;for(inti=2;i<=n;i++){if(s[i]>=f[j]){A[i]=true;j=i;}elseA[i]=false;}}下面给出解活动安排问题的贪心算法GreedySelector:各活动的起始时间和结束时间存储于数组s和f中且按结束时间的非减序排列

说明：用集合A存储所选择的活动。活动i在集合A中，当且仅当A[i]＝true。变量j用以记录最近一次加入到A中所有活动。由于输入的活动是按其结束时间的非减序排列，fj总是当前集合A中所有活动的最大结束时间，即184.1活动安排问题 由于输入的活动以其完成时间的非减序排列，所以算法greedySelector每次总是选择具有最早完成时间的相容活动加入集合A中。直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。

算法greedySelector的效率极高。当输入的活动已按结束时间的非减序排列，算法只需O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，可以用O(nlogn)的时间重排。194.1活动安排问题

例：设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下：i1234567891011S[i]130535688212f[i]4567891011121314204.1活动安排问题

算法greedySelector

的计算过程如左图所示。图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合A的活动，而空白长条表示的活动是当前正在检查相容性的活动。214.1活动安排问题

说明：

若被检查的活动i的开始时间Si小于最近选择的活动j的结束时间fi，则不选择活动i，否则选择活动i加入集合A中。

贪心算法并不总能求得问题的整体最优解。但对于活动安排问题，贪心算法greedySelector却总能求得的整体最优解，即它最终所确定的相容活动集合A的规模最大。这个结论可以用数学归纳法证明。22贪心算法主要用于处理优化问题。每个优化问题都是由目标函数和约束条件组成。满足约束条件的解称为可行解，而那些使得目标函数取极值的可行解称为最优解。在贪婪算法（greedymethod）中采用逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的决策（在一定的标准下）。决策一旦作出，就不可再更改。作出贪婪决策的依据称为贪婪准则（greedycriterion）。4.2贪心算法的基本要素234.2贪心算法的基本要素

本节着重讨论可以用贪心算法求解的问题的一般特征。 对于一个具体的问题，怎么知道是否可用贪心算法解此问题，以及能否得到问题的最优解呢?这个问题很难给予肯定的回答。但是，从许多可以用贪心算法求解的问题中看到这类问题一般具有2个重要的性质：贪心选择性质和最优子结构性质。

241、贪心选择性质所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。

动态规划是由子问题的解得到当前问题的解，所以动态规划算法通常以自底向上的方式解各子问题；而贪心算法则是由当前问题的局部最优解导出子问题，所以贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。

该性质是贪心法使用成功的保障，否则得到的是近优解；

25 对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。也就是说需要证明问题的一个整体最优解是从贪心选择开始的；证明方法：首先考察问题的一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始。做了贪心选择后，原问题简化为规模更小的类似子问题。然后，用数学归纳法证明，通过每一步做贪心选择，最终可得到问题的整体最优解。注：其中，证明贪心选择后的问题简化为规模更小的类似子问题的关键在于利用该问题的最优子结构性质。264.2贪心算法的基本要素

当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。2、最优子结构性质通过局部最优选择，原问题将被化简为类似的子问题；亦即是说，整体最优解中包含了子问题的最优解；27除非满足贪心性质，否则贪心算法存在：不能保证求得的最后解是最佳的；只能求满足某些约束条件的可行解的范围。注：贪婪算法虽不能保证得到最优结果，但对于一些除了“穷举”方法外没有有效算法的问题，用贪婪算法往往能很快地得出较好的结果，如果此较好结果与最优结果相差不是很多的话，此方法还是很实用的。也就是说,在一些情况下，即使贪婪算法不能得到整体最优解，但其最终结果却是最优解的很好的近似解。284.2贪心算法的基本要素

贪心算法和动态规划算法都要求问题具有最优子结构性质，这是2类算法的一个共同点。但是，对于具有最优子结构的问题应该选用贪心算法还是动态规划算法求解?是否能用动态规划算法求解的问题也能用贪心算法求解?下面研究2个经典的组合优化问题，并以此说明贪心算法与动态规划算法的主要差别。

0-1背包问题背包问题3、贪心算法与动态规划算法的差异294.2贪心算法的基本要素0-1背包问题：

给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。304.2贪心算法的基本要素背包问题：

与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1≤i≤n。

这2类问题都具有最优子结构性质，极为相似，但背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。

31其中（4.2.1）是目标函数，（4.2.2）及（4.2.3）是约束条件。满足约束条件的任一集合(x1,…,xn)一个可行解，使目标函数取最大值的可行解是最优解。(4.2.1)(4.2.2)(4.2.3)对于背包问题，形式化描述为：32

例

考虑下列情况下的背包问题:n＝3,c＝20,(v1,v2,v3)=(25,24,15),(w1,w2,w3)=(18,15,10)其中的四个可行解是

①（1,2/15,0）2028.2②（0,2/3,1）2031③（0,1,1/2）2031.5先检验这四个为可行解*,即满足约束条件(4.2.2),(4.2.3).再比较目标函数值,∑vixi.知④组解效益值最大.该组解是背包问题的最优解。33（1）取目标函数作为量度标准，即每次选择利润最大的物品装包，使背包获得最大可能的效益值增量。在此量度标准下贪心方法就是按效益值的非增次序，将物品一一装包，直到某一i物品放不下时，取一种能获得最大增量的物品，将它（或其一部分）放入背包，而使最后一次装包也符合量度标准的要求。例n＝3,c＝20,此解是一个次优解。显然，按物品效益值的非增次序装包不能得最优解。原因：背包可用容量消耗过快。34

（2）以容量作为量度。即按物品重量的非降次序将物品装包。如例中的解②（让背包尽可能慢被消耗）排序:(w3,w2,w1)=(10,15,18)V3=15,x3=1,w3=10,背包剩余C－10＝10;物品2有次大重量(w2＝15),但包装不下。使用x2＝2/3，刚好装满背包且物品2装入2/3与物品1装入5/9的容量均为10个单位。但前者的效益值24×2/3=16>后者效益值＝25×5/9≈14，但②

∑vixi=31,

解（0，2/3，1)仍是一个次优解

。原因：容量慢慢消耗，但效益值未能迅速增大。35

（3）效益值的增长速率和容量的消耗速率间取平衡的量度标准。即以单位效益为量度，使物品装入次序按比值的非增次序排列，应用于例中的数据，得解③:（0,1,1/2）,∑vixi=31.5,∑wixi=20.为例背包问题的最优解.

选取最优的量度标准实为用贪心方法求解问题的核心.364.2贪心算法的基本要素

首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。 具体算法可描述如下页：

用贪心算法解背包问题的基本步骤：374.2贪心算法的基本要素voidKnapsack(int

n,float

M,float

v[],float

w[],floatx[]){

Sort(n,v,w);

inti;for(i=1;i<=n;i++)x[i]=0;floatc=M;for(i=1;i<=n;i++){if(w[i]>c)break;

x[i]=1;c-=w[i];}if(i<=n)x[i]=c/w[i];}

算法knapsack的主要计算时间在于将各种物品依其单位重量的价值从大到小排序。因此，算法的计算时间上界为O（nlogn）。为了证明算法的正确性，还必须证明背包问题具有贪心选择性质。38102030501.￥602.￥1003.￥1204.背包=￥220

=￥160

=￥180

=￥240100201203060101002060

10120306010100208020120

——×2030

0-1背包问题的例子39对于0-1背包问题，贪心选择之所以不能得到最优解是因为在这种情况下，它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。事实上，在考虑0-1背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择。由此就导出许多互相重叠的子问题。这正是该问题可用动态规划算法求解的另一重要特征。实际上，动态规划算法的确可以有效地解0-1背包问题。说明40贪心算法与动态规划的比较

利用动态规划求解最优问题的步骤：

（1）证明该问题具有最优子结构性质；

（2）根据最优子结构性质，写出最优值的递归表达式；

（3）根据递归式，采用自底向上的方式计算，最优值；

（5）求得最优解。利用贪心算法求解最优问题的步骤：

（1）选定合适的贪心选择的标准；

（2）证明在此标准下该问题具有贪心选择性质；

（3）证明该问题具有最优子结构性质；

（4）根据贪心选择的标准，写出贪心选择的算法，求得最优解。

41动态规划算法和贪心算法都属于递推算法，并且这两个算法适用的问题都具有最优子结构，都利用局部最优解来推导全局最优解。42两者的不同点：

1贪心算法作出的每步贪心决策都无法改变，因为贪心策略是由上一步的最优解推导下一步的最优解，而上一部之前的最优解则不作保留。

2动态规划算法的全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有局部最优解；43动态规划算法和贪心算法有一个显著区别：

1）在动态规划算法中，以自底向上的方式来利用最优子结构，也就是说，首先找到子问题的最优解，解决子问题，然后找到问题的一个最优解。

2）在贪心算法中，以自顶向下的方式使用最优子结构，也就是说，贪心算法会先做出选择，在当时看起来是最优的选择，然后再求解一个结果子问题，而不是先求解子问题的最优解，然后再做出选择。

44性能分析45贪心算法存在问题：

（1）不能保证求得的最后解是最佳的；

（2）不能用来求最大最小解的问题；比如钱币分为1元3元4元，要拿6元钱，贪心的话，先拿4，再拿两个1，一共3张钱；实际最优却是两张3元就够了。464.3最优装载 有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。该问题可形式化描述为其中变量xi=0表示不装入集装箱i，xi=1表示装入集装箱i。471、算法描述

最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略，可产生最优装载问题的最优解。具体算法描述如下页。484.3最优装载template<classType>voidLoading(intx[],Typew[],Typec,intn){

int*t=newint[n+1];Sort(w,t,n);for(inti=1;i<=n;i++)x[i]=0;for(inti=1;i<=n&&w[t[i]]<=c;i++){x[t[i]]=1;c-=w[t[i]];}}492、贪心选择性质

设集装箱已依其重量从小到大排列，（x1,x2,…，xn）是最优装载问题的一个最优解。又设

易知，如果给定的最优装载问题有解，则1≤K≤n。 （1）当k=1时，（x1,x2,…,xn)是一个满足贪心选择性质的最优解。 （2）当k>1时，取y1=1；yk=0;yi=xi,1<i≤n,i≠k,则

因此，（y1,y2,…,yn)是所给最优装载问题的可行解。

另一方面，由知，（y1,y2,…,yn)

是满足贪心选择性质的最优解。所以，装载问题具有贪心选择性质。

ywniiiå=1xwniiiå=1xwniiiå=1=w1-wk+≤≤c4.3最优装载yniiå=1=xniiå=1k=min{i|xi=1},1≤i≤n503、最优子结构性质

设（x1,x2,…,xn）是最优装载问题的满足贪心选择性质的最优解，则易知，x1=1，(x2,x3,…,xn)是轮船载重量为c-w1，待装船集装箱为{2，3，…,n)时相应最优装载问题的最优解。也就是说，最优装载问题具有最优子结构性质。 由最优装载问题的贪心选择性质和最优子结构性质，容易证明算法loading的正确性。4、算法复杂性

算法loading的主要计算量在于将集装箱依其重量从小到大排序，故算法所需的计算时间为O(nlogn)。

514.4哈夫曼编码

哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%～90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。 给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码，可以大大缩短总码长。例如一个包含100,000个字符的文件，各字符出现频率不同，如下表所示。定长变码需要300,000位，而按表中变长编码方案，文件的总码长为：（45×1+13×3+12×3+16×3+9×4+5×4）×1000=224,000。比用定长码方案总码长较少约45%。521、前缀码 对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其它字符代码的前缀。这种编码称为前缀码。abcdef频率(千次)4513121695定长码000001010011100101变长码01011001111101110053 译码过程需要方便地取出编码的前缀，因此需要表示前缀码的合适的数据结构。为此，可以用二叉树作为前缀编码的数据结构。在表示前缀码的二叉树中，树叶代表给定的字符，并将每一个字符的前缀码看作是从树根到代表该字符的树叶的一条道路。

表示最优前缀码的二叉树总是一棵完全二叉树，即树中任一结点都有2个儿子结点。

在一般情况下，若C是编码字符集，表示其最优前缀码的二叉树中有|C|个叶子，每个叶子对应于字符集中的一个字符，该二叉树恰有|C|-1个内部结点。54给定编码字符集C及其频率分布f，即C中任一字符c以频率f(c)在数据文件中出现。C的一个前缀码编码方案对应于一棵二叉树T。字符c在树T中的深度即为dT(c)。dT(c)也是字符c的前缀码长。该编码方案的平均码长定义为： 使平均码长达到最小的前缀码编码方案称为给定编码字符集C的最优前缀码。

554.4哈夫曼编码2、构造哈夫曼编码 哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码。 哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。 算法以|C|个叶结点开始，执行|C|－1次的“合并”运算后产生最终所要求的树T。

56Template<classType>ClassHuffman{friendBinaryTree<int>HuffmanTree(Type[],int);public:operatorType()const{returnweight;}private:

BinaryTree<int>tree;Typeweight;};57Template<classType>BinaryTree<int>HuffmanTree(Typef[],intn){//生成单结点树Huffman<Type>*w=newHuffman<Type>[n+1];

BinaryTree<int>z,zero;For(inti=1;i<=n;i++){

z.MakeTree(I,zero,zero);

w[i].weight=f[i];

w[i].tree=z;}//建优先队列

MinHeap<Huffmna<Type>>Q(1);

Q.Initialize(w,n,n);58//反复合并最小频率树

Huffman<Type>x,y;for(inti=1;i<n;i++){

Q.DeleteMin(x);

Q.DeleteMin(y);z.MakeTree(0,x.tree,y.tree);

x.weight+=y.weight;

x.tree=z;

Q.Insert(x);}

Q.DeleteMin(x);

Q.DeleteMin(y);delete[]w;returnx.tree;}594.4哈夫曼编码在书上给出的算法huffmanTree中，编码字符集中每一字符c的频率是f(c)。以f为键值的优先队列Q用在贪心选择时有效地确定算法当前要合并的2棵具有最小频率的树。一旦2棵具有最小频率的树合并后，产生一棵新的树，其频率为合并的2棵树的频率之和，并将新树插入优先队列Q。经过n－1次的合并后，优先队列中只剩下一棵树，即所要求的树T。 算法huffmanTree用最小堆实现优先队列Q。初始化优先队列需要O(n)计算时间，由于最小堆的removeMin和put运算均需O(logn)时间，n－1次的合并总共需要O(nlogn)计算时间。因此，关于n个字符的哈夫曼算法的计算时间为O(nlogn)。604.4哈夫曼编码3、哈夫曼算法的正确性 要证明哈夫曼算法的正确性，只要证明最优前缀码问题具有贪心选择性质和最优子结构性质。

(1)贪心选择性质

(2)最优子结构性质61哈夫曼算法的证明贪心选择性质的证明设C是编码字符集，C中字符c的频率为f(c)。又设x和y是C中具有最小频率的两个字符，则存在C的最优前缀码使x和y具有相同码长且仅最后一位编码不同。证明：设二叉树T表示C的任意一个最优前缀码。则可以证明对T做适当调整得到一棵新的二叉树T’’，使得在新树中，x和y是最深叶子节点且为兄弟，同时新树T’’的前缀码也是C的最优前缀码。从而证明x和y在T’’表示的最优前缀码中具有相同的码长且仅最后一位编码不同。62哈夫曼算法的证明最优子结构性质的证明设T是表示字符集C的一个最优前缀码的完全二叉树。C中字符c的出现频率为f(c)。设x和y是树T中的两个叶子结点且为兄弟，z是他们的父亲。若将z看做是具有频率f(z)=f(x)+f(y)的字符，则树T’=T-{x,y}表示字符集C’=C-{x,y}U{z}的一个最优前缀码。即：取x,y的父结点代替x,y结点，取x,y的权值和作为其父结点的权值，得到的仍是一棵最优二叉树；

证明：设原二叉树的权值为W=W’+x*d+y*d，d为x,y的深度，则用x,y的父结点取代x,y后的二叉树的权值为W’+(x+y)*(d-1)，易见，若存在一个更优的二叉树，将x,y再替换回来也应是一棵更优的二叉树；63XY证明：取x,y的父结点代替x,y结点，取x,y的权值和作为其父结点的权值，得到的仍是一棵最优二叉树。W=W’+x*d+y*dW’+(x+y)*(d-1)644.5单源最短路径 给定带权有向图G=(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。

651、算法基本思想

Dijkstra于1959年提出了解决此问题的一般算法，此算法可按边的权值由小到大的次序，通过贪婪选择，逐步得到由给定源点到图的其余各点间的最短路径。 采用逐条构造最短路径的办法，用迄今已生成的所有路径长度之和为最小作为贪心准则，为此，每一条单独的路径都必须具有最小长度。

66一般情况下，

Dist[k]=<源点到顶点k的弧上的权值>

或者=<源点到其它顶点的路径长度>+<其它顶点到顶点k的弧上的权值>。674.5单源最短路径 其基本思想是，设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源点到该顶点的最短路径长度已知。 初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。

Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist作必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其它顶点之间的最短路径长度。681）在所有从源点出发的弧中选取一条权值最小的弧，即为第一条最短路径。2）修改其它各顶点的Dist[k]值。假设求得最短路径的顶点为u，若Dist[u]+G.arcs[u][k]<Dist[k]则将Dist[k]改为Dist[u]+G.arcs[u][k]。V0和k之间存在弧V0和k之间不存在弧其中的最小值即为最短路径的长度。69迪杰斯特拉(Dijkstra)算法思想按路径长度递增次序产生最短路径算法：把V分成两组：（1）S：已求出最短路径的顶点的集合（2）V-S=T：尚未确定最短路径的顶点集合将T中顶点按最短路径递增的次序加入到S中，保证：（1）从源点V0到S中各顶点的最短路径长度都不大于从V0到T中任何顶点的最短路径长度（2）每个顶点对应一个距离值

S中顶点：从V0到此顶点的最短路径长度

T中顶点：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度依据：可以证明V0到T中顶点Vk的最短路径，或是从V0到Vk的直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和（反证法可证）70求最短路径步骤初使时令S={V},T={其余顶点}，T中顶点对应的距离值若存在<V,Vi>，为<V,Vi>弧上的权值若不存在<V,Vi>，为

从T中选取一个其距离值为最小的顶点W，加入S对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值比不加W的路径要短，则修改此距离值重复上述步骤，直到S中包含所有顶点，即S=V为止71516432085623013717329终点从V0到各终点的最短路径及其长度V1V2V3V4V5V6VjS13<V0,V1>8<V0,V2>

30<V0,V4>

32<V0,V6>V2:8<V0,V2>{V0,V2}13<V0,V1>-------13<V0,V2,V3>30<V0,V4>

32<V0,V6>V1:13<V0,V1>{V0,V2,V1}--------------13<V0,V2,V3>30<V0,V4>22<V0,V1,V5>20<V0,V1,V6>V3:13<V0,V2,V3>{V0,V2,V1,V3}---------------------19<V0,V2,V3,V4>22<V0,V1,V5>20<V0,V1,V6>V4:19<V0,V2,V3,V4>--------------------------------21<V0,V2,V3,V4,V5>20<V0,V1,V6>V6:20<V0,V1,V6>72Template<classType>VoidDijkstra(int

n,int

v,Type

dist[],int

prev[],type**c){//单源最短路径问题的Dijkstra算法，c[i][j]表示边（i,j)的权，dist[i]表示当前//从源到顶点i的最短特殊路径。

bool

s[maxint];for(inti=1;i<=n;i++){

dist[i]=c[v][i];

s[i]=false;if(dist[i]==maxint)prev[i]=0;//设空路径elseprev[i]=v;}

dist[v]=0;s[v]=true;//初始化，v顶点属于S集合//开始主循环，每次求得v到某个顶点的最短路径，并加该顶点到S集73For(inti=1;i<n;i++){//其余n-1个顶点

inttemp=maxint;//当前所指离v顶点的最近距离

Intu=v;for(intj=1;j<=n;j++)if((!s[j])&&(dist[j]<temp))//w顶点在V-S中，且w顶点离v更近{u=j;temp=dist[j];}

s[u]=true;//离v顶点最近的v加入S集合for(intj=1;j<=n;j++)//更新当前最短路径即距离if((!s[j]&&(c[u][j]<maxint)){typenewdist=dist[u]+c[u][j];if(newdist<dist[j]){dist[j]=newdist;prev[j]=u;}//修改D[w]和P[w]}}}744.5单源最短路径

例如，对右图中的有向图，应用Dijkstra算法计算从源顶点1到其它顶点间最短路径的过程列在下页的表中。754.5单源最短路径迭代Sudist[2]dist[3]dist[4]dist[5]初始{1}-10maxint301001{1,2}21060301002{1,2,4}4105030903{1,2,4,3}3105030604{1,2,4,3,5}510503060Dijkstra算法的迭代过程：

764.5单源最短路径2、算法的正确性和计算复杂性(1)贪心选择性质(2)最优子结构性质(3)计算复杂性 对于具有n个顶点和e条边的带权有向图，如果用带权邻接矩阵表示这个图，那么Dijkstra算法的主循环体需要时间。这个循环需要执行n-1次，所以完成循环需要时间。算法的其余部分所需要时间不超过。774.6最小生成树

设G=(V,E)是无向连通带权图，即一个网络。E中每条边(v,w)的权为c[v][w]。如果G的子图G’是一棵包含G的所有顶点的树，则称G’为G的生成树。生成树上各边权的总和称为该生成树的耗费。在G的所有生成树中，耗费最小的生成树称为G的最小生成树。 网络的最小生成树在实际中有广泛应用。例如，在设计通信网络时，用图的顶点表示城市，用边(v,w)的权c[v][w]表示建立城市v和城市w之间的通信线路所需的费用，则最小生成树就给出了建立通信网络的最经济的方案。78144187125818410909461121234212351464337139180218642704621740849867MIAPVDJFKBWIDFWLAXSFOORDBOS144187125818410909461121234212351464337139180218642704621740849867MIAPVDJFKBWIDFWLAXSFOORDBOS794.6最小生成树1、最小生成树性质 用贪心算法设计策略可以设计出构造最小生成树的有效算法。本节介绍的构造最小生成树的Prim算法和Kruskal算法都可以看作是应用贪心算法设计策略的例子。尽管这2个算法做贪心选择的方式不同，它们都利用了下面的最小生成树性质： 设G=(V,E)是连通带权图，U是V的真子集。如果(u,v)

E，且u

U，v

V-U，且在所有这样的边中，(u,v)的权c[u][v]最小，那么一定存在G的一棵最小生成树，它以(u,v)为其中一条边。这个性质有时也称为MST性质。

802、Prim算法

Prim在1957年提出一种算法，这种算法特别适用于边数相对较多，即比较接近于完全图的图。此算法是按逐个将顶点连通的步骤进行的，它只需采用一个顶点集合。这个集合开始时是空集，以后将已连通的顶点陆续加入到集合中去，到全部顶点都加入到集合中了，就得到所需的生成树。

814.6最小生成树2、Prim算法

设G=(V,E)是连通带权图，V={1,2,…,n}。 构造G的最小生成树的Prim算法的基本思想是：首先置S={1}，然后，只要S是V的真子集，就作如下的贪心选择：选取满足条件i

S，j

V-S，且c[i][j]最小的边，将顶点j添加到S中。这个过程一直进行到S=V时为止。 在这个过程中选取到的所有边恰好构成G的一棵最小生成树。82构造最小生成树方法方法一：普里姆(Prim)算法算法思想：设N=(V,{E})是连通网，TE是N上最小生成树中边的集合初始令U={u0},(u0V),TE=在所有uU,vV-U的边(u,v)E中，找一条代价最小的边(u0,v0)将(u0,v0)并入集合TE，同时v0并入U重复上述操作直至U=V为止，则T=(V,{TE})为N的最小生成树V3V1V4V6V5V23652165546如何求连通图的最小生成树?？

求解:

连通6个城市且代价最小的交通线路?

834.6最小生成树 利用最小生成树性质和数学归纳法容易证明，上述算法中的边集合T始终包含G的某棵最小生成树中的边。因此，在算法结束时，T中的所有边构成G的一棵最小生成树。

例如，对于右图中的带权图，按Prim算法选取边的过程如下页图所示。84V3V1V4V6V5V23652165546V3V1V4V6V5V212V3V1V4V6V5V214V3V1V4V6V5V2142V3V1V4V6V5V21452V3V1V4V6V5V21453U={V1}U={V1,V3}U={V1,V3,V6}U={V1,V3,V6,V4}U={V1,V3,V6,V4,V2}U={V1,V3,V6,V4,V2,V5}854.6最小生成树86Prim最小生成树算法描述VoidPrim(int

n,type**c){T=Ø；

S={1}；

while(S!=v){

（i,j)=i∈S

且j∈V-S的最小权边；

T=T∪{(i,j)};S=S∪{j};}}874.6最小生成树 在上述Prim算法中，还应当考虑如何有效地找出满足条件i

S,j

V-S，且权c[i][j]最小的边(i,j)。实现这个目的的较简单的办法是设置2个数组closest和lowcost。 在Prim算法执行过程中，先找出V-S中使lowcost值最小的顶点j，然后根据数组closest选取边(j,closest[j］)，最后将j添加到S中，并对closest和lowcost作必要的修改。 用这个办法实现的Prim算法所需的计算时间为88

有关数据的存储结构

无向连通网络:

G

为选择权值最小的边:

置一个一维数组：closedge[]，以记录从U到

V-U具有最小代价的边。对每一顶点vi

V-U,在辅助数组中相应分量closedge[i-1],包括两域Closedge[i-1].lowcost=Min{cost(u,vi)|u∈U}存储该边上的权Closedge[i-1].adjvex域：存储该边依附的在U中的顶点。

普鲁姆算法涉及的数据和操作：

数据：无向连通网络

操作:选择权值最小的边，不妨设为（u,v)

(u,v)加入TE，u加入UUV-U

viV2V0V3V5V4V-U

vivj89V3V1V4V6V5V23652165546例

111111

06

1

5maxmax

viadjvexlowcost

123456

vi

adjvexlowcost

123456

131133

05056

4U={v1}U={v1,v3}V3V1V4V6V5V23652165546UU对每一顶点vi

V-U,在辅助数组中相应分量closedge[i-1],包括两域Closedge[i-1].lowcost=Min{cost(u,vi)|u∈U}存储该边上的权Closedge[i-1].adjvex域：存储该边依附的在U中的顶点。V-U={v2,V3,V4,V5,V6}V-U={v2,V4,V5,V6}90

0v1v1v100

06

1

5maxmax

lowcost{v1}

0v30v1v3v3

05056

4

adjvexlowcost{v1,v3}

0v30v6v30

050

2

60

adjvexlowcost{v1,v3,v6}

0v300v30

0

5

0060

adjvexlowcost{v1,v3,v6,v4}

0000v20

0000

3

0

adjvexlowcost{v1,v3,v6,v4,v2}

000000

000000

adjvexlowcost{v1,v3,v6,v4,v2,v5}iadjvex

012345UV3V1V4V6V5V23652165546closedge

v1v2v3v4v5v691

设置一个辅助数组，对当前V－U集中的每个顶点，记录和顶点集U中顶点相连接的代价最小的边：typedef

struct{

VertexType

adjvex;//U集中的顶点序号

VRType

lowcost;//边的权值}closedge[MAX_VERTEX_NUM];92voidMiniSpanTree_P(MGraphG,VertexTypeu){

//用普里姆算法从顶点u出发构造网G的最小生成树

k=LocateVex(G,u);for(j=0;j<G.vexnum;++j)//辅助数组初始化

if(j!=k)

closedge[j]={u,G.arcs[k][j].adj};//{adjvex,lowcost}

closedge[k].lowcost=0;//初始，U＝{u}for(i=0;i<G.vexnum;++i){继续向生成树上添加顶点;

}93

k=minimum(closedge);

//求出加入生成树的下一个顶点(k)

printf(closedge[k].adjvex,G.vexs[k]);

//输出生成树上一条边

closedge[k].lowcost=0;//第k顶点并入U集

for(j=0;j<G.vexnum;++j)

//修改其它顶点的最小边

if(G.arcs[k][j].adj<closedge[j].lowcost)

closedge[j]={G.vexs[k],G.arcs[k][j].adj};

}}94abcdegf195141827168213ae12dcb7aaa19141814例如:e12ee8168d3dd7213c5516953、Kruskal算法

Kruskal

在1956年提出了1个最小生成树算法，它的思路很容易理解。设G=(V,E)是一个连通带权图，V={1,2,…,n}。将图中的边按其权值由小到大排序，然后作如下的贪婪选择，由小到大顺序选取各条边，若选某边后不形成回路，则将其保留作为树的一条边；若选某边后形成回路，则将其舍弃，以后也不再考虑。如此依次进行，到选够（n-1）条边即得到最小生成树。96具体做法:

先构造一个只含n个顶点的子图SG，然后从权值最小的边开始，若它的添加不使SG中产生回路，则在SG上加上这条边，如此重复，直至加上n-1条边为止。97算法思路：假设N=(V,{E})是连通图，将N中的边按权值从小到大的顺序排列；（1）将n个顶点看成n个集合；（2）按权值由小到大的顺序选择边，所选边应满足两个顶点不在同一个顶点集合内，将该边放到生成树边的集合中，同时将该边的两个顶点所在的顶点集合合并；（3）重复（2），直到所有的顶点都在同一个顶点集合内。9899

例如，对前面的连通带权图，按Kruskal算法顺序得到的最小生成树上的边如下图所示。各边按权值排序为：d13=1d46=2d25=3d36c4d14=

5d34=5d23=5d12=6d35=6d56=6100//在一个具有n个顶点的网络中找棵最小生成树令E为网络中边的集合令T为所选边的集合,初始化T为空集

while(E不是空集&&T中元素个数不等于n-1){

令(u,v)为E中最小代价的边;E=E-(u,v);//从中删除该边;if((u,v)加入T中不会产生环)

将(u,v)加入T;}算法复杂度为O(n+eloge)Kruskal最小生成树算法1014.6最小生成树说明： 关于集合的一些基本运算可用于实现Kruskal算法。 按权的递增顺序查看等价于对优先队列执行removeMin

运算。可以用堆实现这个优先队列。

算法复杂性：

当图的边数为e时，Kruskal算法所需的计算时间是。当时，Kruskal算法比Prim算法差，但当时，Kruskal算法却比Prim算法好得多。102普里姆算法克鲁斯卡尔算法时间复杂度O(n2)O(eloge)稠密图稀疏图算法名适应范围比较两种算法103问题描述：设有n个独立的作业{1,2,…,n}，由m台相同的机器进行加工处理。作业i所需的处理时间为ti。现约定，任何作业可以在任何一台机器上加工处理，但未完工前不允许中断处理。任何作业不能拆分成更小的子作业。4.7多机调度问题1044.7多机调度问题

多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。 这个问题是NP完全问题，到目前为止还没有有效的解法。对于这一类问题,用贪心选择策略有时可以设计出较好的近似算法。约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。1054.7多机调度问题 采用最长处理时间作业优先的贪心选择策略可以设计出解多机调度问题的较好的近似算法。 按此策略，当时，只要将机器i的[0,ti]时间区间分配给作业i即可，算法只需要O(1)时间。 当时，首先将n个作业依其所需的处理时间从大到小排序。然后依此顺序将作业分配给空闲的处理机。算法所需的计算时间为O(nlogn)。1064.7多机调度问题

例如，设7个独立作业{1,2,3,4,5,6,7}由3台机器M1，M2和M3加工处理。各作业所需的处理时间分别为{2,14,4,16,6,5,3}。按算法greedy产生的作业调度如下图所示，所需的加工时间为17。

各作业按时间由大到小排序为{4，2，5，6，3，7，1}1074.8贪心算法的理论基础

借助于拟阵工具，可建立关于贪心算法的较一般的理论。这个理论对确定何时使用贪心算法可以得到问题的整体最优解十分有用。1、拟阵 拟阵M定义为满足下面3个条件的有序对(S,I)： (1)S是非空有限集。 (2)I是S的一类具有遗传性质的独立子集族，即若B

I，则B是S的独立子集，且B的任意子集也都是S的独立子集。空集

必为I的成员。 (3)I满足交换性质，即若A

I,B

I且|A|<|B|，则存在某一元素x

B-A，使得A∪{x}

I。1084.8贪心算法的理论基础

例如，设S是一给定矩阵中行向量的集合，I是S的线性独立子集族，则由线性空间理论容易证明(S,I)是一拟阵。拟阵的另一个例子是无向图G=(V,E)的图拟阵。 给定拟阵M=(S,I)，对于I中的独立子集A

I，若S有一元素x

A，使得将x加入A后仍保持独立性，即A∪{x}

I,则称x为A的可扩展元素。 当拟阵M中的独立子集A没有可扩展元素时，称A为极大独立子集。1094.8贪心算法的理论基础 下面的关于极大独立子集的性质是很有用的。 定理4.1：拟阵M中所有极大独立子集大小相同。

这个定理可以用反证法证明。 若对拟阵M=(S,I)