算法分析与设计8

陈卫东chenwd华南师范大学计算机科学系,Algorithms:DesignTechniquesandAnalysis算法设计技巧与分析,TheGreedyApproach,TheOutlineThebasicideaofthegreedyapproach8.1IntroductionApplications8.2TheShortestPathProblem8.3MinimumCostSpanningTree(KruskalsAlgorithm)8.4MinimumCostSpanningTree(PrimsAlgorithm)8.5FileCompression,8.1Introduction,贪心法又叫优先策略，顾名思义就是“择优录取”，它是一种非常简单好用的求解最优化问题的方法，在好些方面的应用是非常成功的。TheBasicIdeaofGreedyApproach贪心算法是根据一种贪心准则(greedycriterion)来逐步构造问题的解的方法。在每一个阶段，都作出了相对该准则最优的决策。决策一旦作出，就不可更改。由贪心法得到的问题的解可能是最优解，也可能只是近似解。能否产生问题的最优解需要加以证明。所选的贪心准则不同，则得到的贪心算法不同，贪心解的质量当然也不同。因此，贪心算法的好坏关键在于正确的选择贪心准则。,8.1Introduction,TheKnapsackProblemGivennitemsofsizess1,s2,sn,andvaluesv1,v2,vnandsizeC,theknapsackcapacity,theobjectiveistofindnonnegativerealnumbersx1,x2,xnthatmaximizethesumi=1nxivisubjecttotheconstrainti=1nxisiC.,8.1Introduction,TheKnapsackProblemAninstancen=3,C=20,(s1,s2,s3)=(18,15,10),(v1,v2,v3)=(25,24,15).GreedycriterionsCriterion1根据物品的价值由大到小来放。（由例子可知，它不是最优量度标准）Criterion2根据物品的重量由小到大来放。（由例子可知，它也不是最优量度标准）Criterion3根据价值/重量（即单位价值）由大到小来放。（可以证明它是最优量度标准）,Thegreedyalgorithmbasedoncriterion3.1.Timecomplexity:O(nlogn)2.Correctness:贪心解:X=(x1,x2,xk-1,xk,xk+1,xn):最优解:Z=(x1,x2,xk-1,xk,zk+1,zn)最优解:Y=(x1,x2,xk-1,yk,yk+1,yn),8.1Introduction,8.2TheShortestPathProblem,TheproblemLetG=beadirectedgraphinwhicheachedgehasanonnegativelength,andadistinguishvertexscalledthesource.Thesingle-sourceshortestpathproblem,orsimplytheshortestpathproblem,istodeterminethedistancefromstoeveryothervertexinV,wherethedistancefromvertexstovertexxisdefinedasthelengthofashortestpathfromstox.,8.2TheShortestPathProblem,ThegreedycriterionThebasicideaofDijkstrasalgorithm(1)X1;YV-1(2)ForeachvertexvYifthereisanedgefrom1tovthenletv(thelabelofv)bethelengthofthatedge;otherwiseletv=.Let1=0.(3)whileY(4)LetyYbesuchthatyisminimum.(5)MoveyfromYtoX.(6)updatethelabelsofthoseverticesinYthatareadjacenttoy.(7)endwhile.,8.2TheShortestPathProblem,DijkstrasalgorithmAnInstanceFig.8.1Algorithm8.1DIJKSTRATimeComplexity:(n2)CorrectnessLemma8.1InAlgorithmDijkstra,whenavertexyischoseninstep5,ifitslabelyisfinitetheny=y,whereydenotesthedistancefromthesourcevertextoy.Proof.ByinductiontheorderinwhichverticesleavethesetYandenterX.,8.2TheShortestPathProblem,AnImprovement:AlineartimealgorithmfordensegraphsThebasicideaistousethemin-heapdatastructuretomaintaintheverticesinthesetYsothatthevertexyinYclosesttoavertexinXcanbeextractedinO(logn)time.Thekeyasscioatedwitheachvertexvisitslabelv.Algorithm8.2SHORTESTPATHThetimecomplexity:Theorem8.2,8.3MinimumCostSpanningTrees(KruskalsAlgorithm),TheProblemLetG=beaconnectedundirectedgraphwithweightsonitsedges.Aspanningtree(V,T)ofGisasubgraphofGthatisatree.IfGisweightedandthesumoftheweightsoftheedgesinTisminimum,then(V,T)iscalledaminimumcostspanningtreeorsimplyaminimumspanningtree.,8.3MinimumCostSpanningTrees(KruskalsAlgorithm),ThegreedycriterionThebasicideaofKruskalsalgorithm(1)SorttheedgesinGbynondecreasingweight.(2)Foreachedgeinthesortedlist,includethatedgeinthespanningtreeTifitdoesnotfromacyclewiththeedgescurrentlyincludedinT;otherwisediscardit.,8.3MinimumCostSpanningTrees(KruskalsAlgorithm),KruskalsalgorithmAnInstanceFig.8.4Algorithm8.3KRUSKALTimeComplexity:(mlogm)Correctness:Lemma8.2AlgorithmKruskalcorrectlyfindsaminimumcostspanningtreeinaweightedundirectedgraph.Proof.ProveByinductiononthesizeofTthatTisasubsetofthesetofedgesinaminimumcostspanningtree.,8.4MinimumCostSpanningTrees(PrimsAlgorithm),TheProblemTheproblemdiscussedhereisthesameastheonediscussedabove.Thegreedycriterion,8.4MinimumCostSpanningTrees(PrimsAlgorithm),ThebasicideaofPrimsalgorithm(1)T;X1;YV-1(2)whileY(3)Let(x,y)beofminimumweightsuchthatxXandyY.(4)XXy(5)YY-y(6)TT(x,y)(7)endwhile,8.4MinimumCostSpanningTrees(PrimsAlgorithm),PrimsalgorithmAnInstanceFig.8.5Algorithm8.4PRIMTimeComplexity:(n2)Correctness:Lemma8.3AlgorithmPRIMcorrectlyfindsaminimumcostspanningtreeinaconnectedundirectedgraph.Proof.ProvebyinductiononthesizeofTthat(X,T)isasubtreeofaminimumcostspanningtree.,8.4MinimumCostSpanningTrees(PrimsAlgorithm),AnImprovement:Alineartimealgorithmfordensegraphsthebasicideaistousethemin-heapdatastructuretomaintainthesetofborderingverticessothatthevertexyinYincidenttoanedgeoflowestcostthatisconnectedtoavertexinV-YcanbeextractedinO(logn)time.Algorithm8.5MSTThetimecomplexity:Theorem8.5,8.5FileCompression(HuffmansAlgorithm),TheProblemLetfisafile,whichisastringofcharacters.LetthesetofcharactersinthefilebeC=c1,c2,cn.Letalsof(ci),1in,bethefrequencyofcharacterciinthefile,i.e.,thenumberoftimesciappearsinthefile.Wewishtocompressthefileasmuchaspossibleinsuchawaythattheoriginalfilecaneasilybereconstructed.,8.5FileCompression(HuffmansAlgorithm),Astraightforwardalgorithm:useafixednumberofbitstorepresent(encode)eachcharacter.Huffmansalgorithm:useavariablelengthencodings.Thosecharacterswithlargefrequenciesshouldbeassignedshortencodings,whereaslongencodingsmaybeassignedtothosecharacterswithsmallfrequencies.,8.5FileCompression(HuffmansAlgorithm),实例数据压缩问题假设有一个数据文件包含100000个字符，我们要用压缩的方式来存储它。该文件中各个字符出现的频率如下表所示。文件中共有6个不同字符出现，字符a出现45000次，字符b出现13000次等。要压缩表示这个文件中的信息有多种方法。我们考虑用0，1码串来表示字符的方法，即每个字符用唯一的一个0，1串来表示。问题要求使用二进制数字0，1码串来编码，保证编码是前缀码的前提下使得压缩文件最短。（为了使得译码容易，编码必须具有性质：任一字符的代码都不是其它字符代码的前缀。我们称这样的编码为前缀码。）,8.5FileCompression(HuffmansAlgorithm),8.5FileCompression(HuffmansAlgorithm),若使用定长码，则表示每个不同的字符最少需要3位。用这种方法对整个文件编码需要300000位。那么，给这个文件编码最少需要多少位呢？采用上表中的变长码给文件编码需要224000位，它比定长码减少了约25%。事实上，这是该文件的一个最优编码方案。容易证明，任何一个前缀码都对应一棵二叉树。反之，任意一棵二叉树的树叶可对应一个前缀码。例如，表中的两个前缀码对应的二叉树为下图。