算法设计与分析课件_Algotiyhmsch04-greedyprogramming

算法设计与分析第4章贪心算法北京邮电大学王小茹内容安排什么是贪心算法？算法的设计思想贪心法不是万能的：再看一个例子活动安排问题贪心算法实例活动安排问题贪心总结如何证明贪心算法是最优解？对于活动安排问题：思路贪心算法的最优解证明贪心要素贪心要素1：贪心要素2：贪心算法的一般框架贪心算法与动态规划的区别重温0-1背包问题0-1背包适合贪心算法吗？区别最优装载问题贪心算法的实例最优装载问题是否具有贪心性质？是否具有最优子结构？哈夫曼编码贪心算法的实例GreedyAlgorithmsHuffmanCodes–用于文件压缩〖Example〗Supposeourtextisastringoflength1000thatcomprisesthecharactersa,u,x,andz.Thenitwilltake?bitstostorethestringas1000one-bytecharacters.8000Noticethatwehaveonly4distinctcharactersinthatstring.Henceweneedonly2bitstoidentifythem.Wemayencodethesymbolsasa=00,u=01,x=10,z=11.Forexample,aaaxuaxzisencodedas0000001001001011.Thenthespacetakenbythestringwithlength1000willbe2000bits+spaceforcodetable./*logCbitsareneededinastandardencodingwhereCisthesizeofthecharacterset*/frequency::=numberofoccurrencesofasymbol.Instringaaaxuaxz,f(a)=4,f(u)=1,f(x)=2,f(z)=1.Thesizeofthecodedstringcanbereducedusingvariable-lengthcodes,forexample,a=0,u=110,x=10,z=111.00010110010111Note:Ifallthecharactersoccurwiththesamefrequency,thentherearenotlikelytobeanysavings.1/17§1GreedyAlgorithmsaxuzRepresentationoftheoriginalcodeinabinarytree/*trie*/000111IfcharacterCiisatdepthdiandoccursfitimes,thenthecostofthecode=difi.Cost(aaaxuaxz0000001001001011)=24+21+22+21=16Representationoftheoptimalcodeinabinarytreeauxz000111Cost(aaaxuaxz00010110010111)=14+31+22+31=14Theanswerisaaaxuaxz(witha=0,u=110,x=10,z=111).Whatmakesthisdecodingmethodwork?Thetrickis:Nocodeisaprefixofanother.Now,witha=0,u=110,x=10,z=111andthestring00010110010111,canyoudecodeit?Anysequenceofbitscanalwaysbedecodedunambiguouslyifthecharactersareplacedonlyattheleavesofafulltree–suchkindofcodeiscalledprefixcode.Findthefullbinarytreeofminimumtotalcostwhereallcharactersarecontainedintheleaves.Allnodeseitherareleavesorhavetwochildren.2/17§1GreedyAlgorithmsHuffman’sAlgorithm(1952)voidHuffman(PriorityQueueheap[],intC){considertheCcharactersasCsinglenodebinarytrees,andinitializethemintoaminheap;for(i=1;iC;i++){createanewnode;/*begreedyhere*/deleterootfromminheapandattachittoleft_childofnode;deleterootfromminheapandattachittoright_childofnode;weightofnode=sumofweightsofitschildren;/*weightofatree=sumofthefrequenciesofitsleaves*/insertnodeintominheap;}}T=O(?)ClogC3/17§1GreedyAlgorithms〖Example〗Cifiaeis1015123tspnl4131a10e15i12s3t4sp13nl1a10e15i12s3t4sp13nl1nl1s3t44i12e15sp13a10nl1s3t44i12e15sp13a108nl1s3t44i12e15sp13a10818nl1s3t44i12e15sp13a1081825nl1s3t44i12e15sp13a108182533nl1s3t44i12e15sp13a10818253358000000111111aeistspnl:111:10:00:11011:1100:01:11010Cost=310+215+212+53+44+213+51=1464/17Huffmancodes•DataCompressionviaHuffmanCoding–Motivation»Limitednetworkbandwidth.»Limiteddiskspace.–Humancodesareusedfordatacompression.»Reducingtimetotransmitlargefiles,and»Reducingthespacerequiredtostorethemondiskortape.–Huffmancodesareawidelyusedandveryeffectivetechniqueforcompressingdata,savingsof20%to90%aretypical,dependingonthecharacteristicsofthedata.ExampleofHuffmancodesExampleofHuffmancodes•(cont.)AlgorithmofHuffmanCoding•ThegreedyalgorithmforcomputingtheoptimalHumancodingtreeTisasfollows.–Itstartswithaforestofone-nodetreesrepresentingeachc∈C,andmergestheminagreedystyle,usingapriorityqueueQ,sortedbythesmallestfrequency:哈夫曼编码单源最短路径贪心算法应用单源最短路径贪心算法的求解算法的正确性：贪心选择性质和最优子结构贪心算法性质每次的贪心选择是从V-S中选择具有最短的特殊路径的顶点U，从而确定从源到U的最短路径长度Dist[u]。证明：反证法假设从源s-u存在一个更好的路径，这条路径从源s出发，经过x，到达u.即D(s,x)+d(x,u)=d(s,u)dist[u]由于Dist[x]=d(s,x)所以dist[x]dist[u],导致矛盾。最优子结构性质最小生成树算法贪心算法的应用最小生成树算法的复杂性分析思考题：PrimVSKruskal算法复杂性分析计算机调度问题贪心法的应用§1GreedyAlgorithmsNote:Greedyalgorithmworksonlyifthelocaloptimumisequaltotheglobaloptimum.Greedyalgorithmdoesnotguaranteeoptimalsolutions.However,itgenerallyproducessolutionsthatareverycloseinvalue(heuristics)totheoptimal,andhenceisintuitivelyappealingwhenfindingtheoptimalsolutiontakestoomuchtime.1.ASimpleSchedulingProblemGivenNjobsj1,j2,…,jN,theirrunningtimest1,t2,…,tN,andoneprocessor.Schedulejobstominimizetheaveragecompletiontime./*assumenonpreemptivescheduling假定为非抢占式调度*/TheSingleProcessorCase2/7§1GreedyAlgorithms〖Example〗jobtimej1j2j3j4158310Schedule1j1015j223j326j436Tavg=(15+23+26+36)/4=25Schedule2j136j2110j33j421Tavg=(3+11+21+36)/4=17.75Ingeneral:0ji1ti1ji2ti1+ti2ji3ti1+ti2+ti3……NkiNkiNkikkktktNtkNC111)1()1(CostTotalBestschedulingistomake{tik}nondecreasing不减少，递增.3/7TheMultiprocessorCase–NjobsonPprocessors〖Example〗P=3jobtimej1j2j3j435610j5j6j7j811141518j920AnOptimalSolutionj13j25j360j413j516j620j728j834j940AnotherOptimalSolutionj13j25j360j415j514j620j730j838j934MinimizingtheFinalCompletionTimeNPHardAnOptimalSolutionj13j25j39j419j516j614j7j834j904/7§1GreedyAlgorithmsFlowShopScheduling–asimplecasewith2processorsConsideramachineshopthathas2identicalprocessorsP1andP2.WehaveNjobsJ1,...,JNthatneedtobeprocessed.EachjobJicanbebrokeninto2tasksji1andji2.AscheduleisanassignmentofjobstotimeintervalsonmachinessuchthatjijmustbeprocessedbyPjandtheprocessingtimeistij.Nomachineprocessesmorethanonejobatanytime.ji2maynotbestartedbeforeji1isfinished.Constructaminimum-completion-time2machinescheduleforagivenset