Greedy Algorithms(Chap16)

《Greedy Algorithms(Chap16)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、GreedyAlgorithms(Chap.16)OptimizationproblemsDynamicprogramming,butoverkillsometime.Greedyalgorithm:Beinggreedyforlocaloptimizationwiththehopeitwillleadtoaglobaloptimalsolution,notalways,butinmanysituations,itworks.AnActivity-SelectionProblemSupposeAsetofactivitiesS={a1,a2,

2、…,an}Theyuseresources,suchaslecturehall,onelectureatatimeEachai,hasastarttimesi,andfinishtimefi,with0si

3、erelationbetweenthetwo.DPsolution–step1Optimalsubstructureofactivity-selectionproblem.Furthermore,assumethatf1…fn.DefineSij={ak:fisk

4、fn+1.ThenanoptimalsolutionincludingaktoSijcontainswithinittheoptimalsolutiontoSikandSkj.DPsolution–step2ArecursivesolutionAssumec[n+1,n+1]withc[i,j]isthenumberofactivitiesinamaximum-sizesubsetofmutuallycompatibleactivitiesinSij.Sothesolutionisc[0,n+1]=S0,n+1.C[i,j]=0ifSij=

5、max{c[i,k]+c[k,j]+1}ifSiji

6、bproblemSimisempty,sothatchoosingamleavesSmjastheonlyonethatmaybenonempty.Proofofthetheorem:Top-DownRatherThanBottom-UpTosolveSij,chooseaminSijwiththeearliestfinishtime,thensolveSmj,(Simisempty)ItiscertainthatoptimalsolutiontoSmjisinoptimalsolutiontoSij.NoneedtosolveSmjahea

7、dofSij.Subproblempattern:Si,n+1.OptimalSolutionPropertiesInDP,optimalsolutiondepends:Howmanysubproblemstodivide.(2subproblems)Howmanychoicestodeterminewhichsubproblemtouse.(j-i-1choices)However,theabovetheorem(16.1)reducesbothsignificantlyOnesubproblem(theotherissuretobeemp

8、ty).Onechoice,i.e.,theonewithearliestfinishtimeinSij.Moreover,top-downsolving,rath