算法与结构课件-第五章-贪心法-old(华北电力大学科技学院)

NorthChinaElectricPowerUniversity计算机算法设计与分析NorthChinaElectricPowerUniversityComputerAlgorithmsDesign&Analysis华北电力大学计算机科学与工程系Dept.ofComputerScience&EngineeringofNorthChinaElectricPowerUniversityNorthChinaElectricPowerUniversity第五章贪心算法(GreedyAlgorithm)★活动安排问题★最优装载★单源最短路径★最小生成树★多机调度问题NorthChinaElectricPowerUniversity★贪心算法的基本要素NorthChinaElectricPowerUniversity例找钱问题：假定有四种面值分别为二角五分、一角、五分和一分，现要找给某顾客六角三分钱，问怎样找钱，才能使所拿出的硬币个数是最少的？分析与解答：1.动态规划算法设ak是找k分钱所需的最少硬币个数，则存在如下递归关系：ak=1+min{ak-25,ak-10,ak-5,ak-1}2.贪心算法：每次尽可能将面值大的硬币找给客户。问题的解为：需要找6枚硬币，面值分别为：{25分，25分，10分，1分，1分，1分}该解是问题的一个整体最优解。NorthChinaElectricPowerUniversity§1活动安排问题NorthChinaElectricPowerUniversity1.问题的描述:设有n个活动的集合E={1,2,…,n},其中每个活动都要求使用同一资源,而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和结束时间fi且sifi。如果选择了活动i，则它在半开时间区间[si,fi)内占用资源。若区间[si,fi)与区间[sj,fj)不相交，则称活动i与活动j是相容的。也就是说,当si≥fj或sj≥fi时，活动i与活动j相容。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。下面给出的算法GreedySelector中，各活动的起始时间和结束时间存储于数组s和f中且按结束时间的非递减序排列。NorthChinaElectricPowerUniversityNorthChinaElectricPowerUniversity2.算法描述：templateclassTypevoidGreedySelector(intn,Types[],Typef[],boolA[]){A[1]=true;//表示活动进入相容集合，即活动被安排intj=1;//进入相容集合的最后一个活动for(inti=2;i=n;i++){if(s[i]=f[j]{A[i]=ture;j=i;}elseA[i]=false;}}NorthChinaElectricPowerUniversityNorthChinaElectricPowerUniversity集合A用来存储所选择的活动。活动i在集合A中，当且仅当A[i]的值为ture。变量j用以记录最近一次加入到A中的活动。由于输入的活动是以其完成时间的非递减序排列的，所以算法GreedySelector每次总是选择具有最早完成时间的相容活动加入A中。直观上按这种方法选择相容活动就为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相同活动。3.例：设待安排的11个活动的开始时间和结束时间按时间的非减序排列如下：i1234567891011s[i]130535688212f[i]4567891011121314NorthChinaElectricPowerUniversity计算过程如图：012345678910111213141481114888811111111144444442356791011（时间）NorthChinaElectricPowerUniversity§2贪心算法的基本要素贪心算法通过一系列的选择来得到一个问题的解。它所作的每一个选择都是当前状态下某种意义的最好选择，即贪心选择。希望通过每次所做的贪心选择导致最终结果是问题的一个最优解。这种启发式的策略并不总能奏效，然而在许多情况下确能达到预期的目的。下面讨论用贪心法求解的问题的一般特征。贪心法两个重要的性质：贪心选择性质和最优子结构性质。1.贪心选择性质（存在一个以贪心选择开始的最优解）所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素。NorthChinaElectricPowerUniversity2.最优子结构性质当一个问题的最优解包含着它的子问题的最优解时，称此问题具有最优子结构性质。该性质是可用动态规划或贪心算法求解的一个关键特性。3.贪心算法和动态规划算法的差异贪心算法和动态规划算法虽然都要求问题具有最优子结构性质，但是能用动态规划算法求解的问题不一定能用贪心法来求解。下面用两个例子来说明一下：0-1背包问题：给定n种物品和一个背包。物品的i重量是wi，其价值为vi，背包的容量为c。问应如何选择装入背包中的物品的总价值最大？ivNorthChinaElectricPowerUniversity注意：在选择装入背包的物品时，对每中物品i只有两种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。背包问题：与0-1背包问题类似，所不同的是在选择物品装入背包时，可以选择物品的一部分，而不一定要全部装入背包。分析：两个问题相似，但背包问题可以用贪心算法求解，而0-1背包问题却不能。背包问题的贪心算法描述：首先计算每种物品单位重量的价值vi/wi，然后,依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过c，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直到背包装满为止。NorthChinaElectricPowerUniversityvoidKnapsack(intn,floatM,floatv[],floatw[],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];}这种贪心策略对0-1背包问题就不适用了，因为它无法保证最终能将背包装满，部分背包空间的闲置使每千克背包空间所具有的价值降低了。而动态规划算法可以解决0-1背包问题。NorthChinaElectricPowerUniversity§3最优装载1.问题描述：有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为wi。最优装载问题要求确定，在装载体积不受限制的情况下，应如何装载才能将尽可能多的集装箱上轮船。2.算法描述：最优装载问题可用贪心法求解。采用重量最轻者先装的贪心选择策略，由此可得最优装载问题的一个最优解，具体算法描述如下：NorthChinaElectricPowerUniversitytemplateclassTypevoidLoading(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]];}}NorthChinaElectricPowerUniversity3.贪心选择性质设集装箱已依其重量从小到大排序，(x1,x2,…,xn)是最优装载问题的一个最优解。又设k=min{i|xi=1}。易知，如果给定的最优装载问题有解，则1≤k≤n。1)当k=1时，(x1,x2,…,xn)是一个满足贪心选择性质的最优解。2)当k1时，取y1=1;yk=0;yi=xi,1i≤n,i≠n,则cxwx1111因此，(y1,y2,…,yn)是所给最优装载问题的一个可行解。另一方面，由知，(y1,y2,…,yn)是一个满足贪心选择性质的最优解。所以，最优装载问题具有贪心选择性质。niniiixy114.最优子结构性质NorthChinaElectricPowerUniversity设(x1,x2,…,xn)是最优装载问题的一个满足贪心选择性质的最优解，则易知，x1=1,(x2,x3,…,xn)是轮船载重量为c-w1且待装集装箱为{2,3,…,n}时相应最优装载问题的一个最优解。也就是说，最优装载问题具有最优子结构性质。由最优装载问题的贪心选择性质和最优子结构性质，容易证明算法Loading的正确性。算法Loading的主要计算量在于将集装箱依其重量从小到大排序，故算法所需的计算时间为O(nlogn)。NorthChinaElectricPowerUniversity§4哈夫曼编码哈夫曼编码是用于数据文件压缩的一个十分有效的编码方法。其压缩率通常在20%~90%之间。哈夫曼编码算法使用一个字符在文件中出现的频率表来建立一个用0，1串表示各符号的最优表示方式。例：假设有一个数据文件包含100000个字符，用压缩的方式来存储它。该文件中各字符出现的频率如表：abcdef频率（千次）4513121695定长码000001010011100101变长码010110011111011100NorthChinaElectricPowerUniversity若使用定长码，表示每个不同的字符需要3位：a=000，b=001，…，f=101。整个文件需300000位。使用变长码比定长码好的多，即给出现频率高的字符较短的编码，出现频率低的字符以较长的编码，其中字符a用0表示，f用4位串1100表示。整个文件的总码长为：=224000它比用定长码方案好，总码长减少了约25%。100045493163123131451.前缀码对每一个字符规定一个0，1串作为其代码，并要求任一字符的代码都不是其他字符代码的前缀，称这样的代码具有前缀性质，或简称为前缀码。编码的前缀性质可以使译码方法简单。即可从编码文件中不断取出代表某一字符的前缀码，转换成原字符，继而译出文件。NorthChinaElectricPowerUniversity给定编码字符集C及其频率分布f，即C中任一字符c以频率f（c）在数据文件中出现。C的一个前缀码编码方案对应于一棵二叉树T。字符c在树T中的深度记为。也是字符c的前缀码长。该编码方案的平均码长定义为：B（T）=使平均码长达到最小的前缀码编码方案称为C的一个最优前缀码。cdTcdTcdTCcTcdcf)()(2.构造哈夫曼编码哈夫曼提出了一种构造哈夫曼前缀码的贪心算法，由此产生的编码方案称为哈夫曼算法。哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。算法以个叶结点开始，执行次的“合并”运算后产生最终所要求的树T。下面的算法中，C1CNorthChinaElectricPowerUniversity编码字符集中每一字符c的频率是f（c）。以f为键值的优先队列Q用以在作贪心选择时有效地确定算法当前要合并的两棵具有最小频率的树。一旦两棵具有最小频率的树合并后，产生一棵新的树，其频率为合并的两棵树的频率之和，并将新树插入优先队列Q。算法中用到的类Huffman定义为：templateclassTypeclassHuffman{friendBinaryTreeintHuffman(Type[],int);public:operatorType()const{returnweight;}private:BinaryTreeint