资源描述
CHAPTER10ALGORITHMDESIGNTECHNIQUES,1GreedyAlgorithms,OptimizationProblems:Givenasetofconstrainsandanoptimizationfunction.Solutionsthatsatisfytheconstrainsarecalledfeasiblesolutions.Afeasiblesolutionforwhichtheoptimizationfunctionhasthebestpossiblevalueiscalledanoptimalsolution.,TheGreedyMethod:Makethebestdecisionateachstage,undersomegreedycriterion.Adecisionmadeinonestageisnotchangedinalaterstage,soeachdecisionshouldassurefeasibility.,1/12,1GreedyAlgorithms,2/12,Note:Greedyalgorithmworksonlyifthelocaloptimumisequaltotheglobaloptimum.Greedyalgorithmdoesnotguaranteeoptimalsolutions.However,itgenerallyproducessolutionsthatareverycloseinvalue(heuristics)totheoptimal,andhenceisintuitivelyappealingwhenfindingtheoptimalsolutiontakestoomuchtime.,1GreedyAlgorithms,1.HuffmanCodesforfilecompression,ExampleSupposeourtextisastringoflength1000thatcomprisesthecharactersa,u,x,andz.Thenitwilltake?bitstostorethestringas1000one-bytecharacters.,8000,Noticethatwehaveonly4distinctcharactersinthatstring.Henceweneedonly2bitstoidentifythem.,Wemayencodethesymbolsasa=00,u=01,x=10,z=11.Forexample,aaaxuaxzisencodedas0000001001001011.Thenthespacetakenbythestringwithlength1000willbe2000bits+spaceforcodetable./*logCbitsareneededinastandardencodingwhereCisthesizeofthecharacterset*/,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.,3/12,Discussion9:InwhatcasethattherearenotlikelytobeanysavingsevenusingHuffmancodes?,1GreedyAlgorithms,Representationoftheoriginalcodeinabinarytree/*trie*/,IfcharacterCiisatdepthdiandoccursfitimes,thenthecostofthecode=difi.,Cost(aaaxuaxz0000001001001011)=24+21+22+21=16,Representationoftheoptimalcodeinabinarytree,Cost(aaaxuaxz00010110010111)=14+31+22+31=14,Theanswerisaaaxuaxz(witha=0,u=110,x=10,z=111).Whatmakesthisdecodingmethodwork?,Thetrickis:Nocodeisaprefixofanother.,Now,witha=0,u=110,x=10,z=111andthestring00010110010111,canyoudecodeit?,4/12,Discussion10:Whatmustthetreelooklikeifwearetodecodeunambiguously?,1GreedyAlgorithms,HuffmansAlgorithm(1952),voidHuffman(PriorityQueueheap,intC)considertheCcharactersasCsinglenodebinarytrees,andinitializethemintoaminheap;for(i=1;iC;i+)createanewnode;/*begreedyhere*/deleterootfromminheapandattachittoleft_childofnode;deleterootfromminheapandattachittoright_childofnode;weightofnode=sumofweightsofitschildren;/*weightofatree=sumofthefrequenciesofitsleaves*/insertnodeintominheap;,T=O(?),ClogC,5/12,1GreedyAlgorithms,Cost=310+215+212+53+44+213+51=146,6/12,ResearchProject4HuffmanCodes(30),AsaprofessorwhogivesthefinalexamproblemonHuffmancodes,Iamencounteringabigproblem:theHuffmancodesareNOTunique.Thestudentsaresubmittingallkindsofcodes,andIneedacomputerprogramtohelpmedeterminewhichonesarecorrectandwhichonesarenot.Detailedrequirementscanbedownloadedfrom,7/12,2.ASimpleSchedulingProblem,GivenNjobsj1,j2,jN,theirrunningtimest1,t2,tN,andoneprocessor.,Schedulejobstominimizetheaveragecompletiontime./*assumenonpreemptivescheduling*/,TheSingleProcessorCase,1GreedyAlgorithms,8/12,1GreedyAlgorithms,Example,Schedule1,Tavg=(15+23+26+36)/4=25,Schedule2,Tavg=(3+11+21+36)/4=17.75,Ingeneral:,9/12,Bestschedulingistomaketiknondecreasing.,1GreedyAlgorithms,TheMultiprocessorCaseNjobsonPprocessors,AnOptimalSolution,MinimizingtheFinalCompletionTime,NPHard,10/12,1GreedyAlgorithms,FlowShopSchedulingasimplecasewith2processors,Consideramachineshopthathas2identicalprocessorsP1andP2.WehaveNjobsJ1,.,JNthatneedtobeprocessed.EachjobJicanbebrokeninto2tasksji1andji2.,Ascheduleisanassignmentofjobstotimeintervalsonmachinessuchthat,jijmustbeprocessedbyPjandtheprocessingtimeistij.,Nomachineprocessesmorethanonejobatanytime.,ji2maynotbestartedbeforeji1isfinished.,Constructaminimum-completion-time2machinescheduleforagivensetofNjobs.,Letai=ti10,andbi=ti2.,ExampleGivenN=4,T1234=?,40,11/12,Discussion11:Whatifai=0?,1GreedyAlgorithms,【Proposition】Anoptimalscheduleexistsifminbi,ajminbj,aiforanypairofadjacentjobsJiandJj.Allthescheduleswiththispropertyhavethesamecompletiontime.,AlgorithmSorta1,.,aN,b1,.,bNintonon-decreasingsequence;m=minimumelement;doif(m=ai),ExampleGivenN=4,T=O(NlogN),12/12,Sortingb2a1a2b1a3b3a4b4,J2,J1,J3,J4,T1342=?,38,
展开阅读全文