Chapter 5 Gready algorithm.ppt

算法设计与分析 NorthChinaElectricPowerUniversity AlgorithmsDesign Analysis 华北电力大学计算机科学与技术学院 SchoolofComputerScience TechnologyofNorthChinaElectricPowerUniversity NorthChinaElectricPowerUniversity Chapter5GreedyAlgorithm 1 Introduction 2 Fractionalknapsackproblem 3 Theshortestpathproblem 4 Minimumspanningtreesproblem 5 找钱问题 6 汽车加油问题 7 Anactivity selectionproblem NorthChinaElectricPowerUniversity 1Introduction Typically inoptimizationproblemsthealgorithmneedstomakeaseriesofchoiceswhoseoveralleffectistominimizethetotalcost ormaximizethetotalbenefit ofsomesystem Thegreedymethodconsistsofmakingthechoicesinsequencesuchthateachindividualchoiceisbestaccordingtosomelimited short term criterionthatisnottooexpensivetoevaluate Onceachoiceismade itcan tbeundown evenifitbecomesevidentlaterthatitwasapoorchoice Forthisreason greedyalgorithmdon tnecessarilyfindtheexactoptimumsolutionformanyproblems Unlikedynamicprogrammingalgorithms greedyalgorithmstypicallyconsistofaniterativeprocedurethattriestofindalocaloptimalsolution Agreedyalgorithmmakesacorrectguessonthebasisoflittlecalculationwithoutworryingaboutthefuture Thusitbuildsasolutionstepbystep Eachstepincreasesthesizeofthepartialsolutionandisbasedonlocaloptimization Thechoicemadeisthatwhichproducesthelargestimmediategainwhilemaintainingfeasibility NorthChinaElectricPowerUniversity Sinceeachstepconsistsoflittleworkbasedonasmallamountofinformation theresultingalgorithmsaretypicallyefficient Thehardpartinthedesignofagreedyalgorithmisprovingthatthealgorithmdoesindeedsolvetheproblemitisdesignedfor Thisiscontrastedwithrecursivealgorithmsthathavesimpleinductiveproofs Howcanonetellifagreedyalgorithmwillsolvea particularoptimizationproblem Thereisnowayingeneral Ifwecandemonstratethefollowingproperties thenitisprobabletousegreedyalgorithm Whengreedyalgorithmworks NorthChinaElectricPowerUniversity 1 Greedy choiceProperty 2 OptimalSubstructure thesamewiththatofdynamicprogramming property Greedychoiceproperty Aglobaloptimalsolutioncanbearrivedatbymakingalocallyoptimalgreedychoice Thatis whenweareconsideringwhichchoicetomake wemakethechoicethatlooksbestinthecurrentproblem withoutconsideringresultfromsubproblems Note Greedyalgorithmisaspecialdynamicprogramming NorthChinaElectricPowerUniversity StepsofGreedyAlgorithm1 Casttheoptimizationproblemasoneinwhichwemakeachoiceandareleftwithonesubproblemtosolve NorthChinaElectricPowerUniversity 2 Provethatthereisalwaysanoptimalsolutiontotheoriginalproblemthatmakesthegreedychoice sothatthegreedychoiceisalwayssafe 3 Demonstratethat havingmadethegreedychoice whatremainsisasubproblemwiththepropertythatifwecombineanoptimalsolutiontothesubproblemwiththegreedychoicewehavemade wearriveatanoptimalsolutiontotheoriginalproblem 2找钱问题 假定有四种面值分别为二角五分 一角 五分和一分的硬币 现要找给某顾客六角三分钱 问怎样找钱 才能使所拿出的硬币个数是最少的 分析与解答 1 动态规划算法 设ak是找k分钱所需的最少硬币个数 则存在如下递归关系 ak 1 min ak 25 ak 10 ak 5 ak 1 2 贪心算法 每次尽可能将面值大的硬币找给客户 问题的解为 需要找6枚硬币 面值分别为 25分 25分 10分 1分 1分 1分 该解是问题的一个整体最优解 NorthChinaElectricPowerUniversity 设c 1 25 c 2 10 c 3 5 c 4 1 则所述找钱问题可表述为求s i i 1 4 使s是下面的最优化问题的解 min s i 4 i 1 s t s i c i n且s i 为非负整数 4 i 1 1 最优子结构性质 NorthChinaElectricPowerUniversity 2 贪心选择性质 对于所述问题的任一最优解s i i 1 4 s 4 4 s 3 1 s 2 2 NorthChinaElectricPowerUniversity 事实上 若s 4 5 则可用1枚面值为c 3 的硬币去替代5枚面值为c 4 的硬币 当s 3 2时 可用1枚面值为c 2 的硬币去替换2枚面值为c 3 的硬币 当s 2 3时 可用1枚面值为c 1 的硬币和1枚面值为c 3 的硬币去替换3枚面值为c 2 的硬币 这些替换都导致s i i 1 4不是最优解 NorthChinaElectricPowerUniversity 可知 s 1 0 因为若不然 由前面的分析可知 这个表达式的左边最大可能的值是24 即s 2 2 s 3 0 s 4 4 同理可知 当10 n0 当5 n0 当1 n0 即该问题满足贪心选择性质 3Fractionalknapsackproblem Givennitemsofsizess1 s2 sn andvaluesv1 v2 vnandsizeC theknapsackcapacity theobjectiveistofindnonnegativerealnumbersx1 x2 xnthatmaximizethesum NorthChinaElectricPowerUniversity subjecttotheconstraint 0 1knapsackproblemmodel Objectfunction max pixiConstraint wixi C C 0 wi 0 pi 0 1 i nxi 0 1 n i 1 n i 1 NorthChinaElectricPowerUniversity NorthChinaElectricPowerUniversity Theoptimalsubstructureproperty Ifweremoveasizesofoneitemjfromtheoptimalload thentheremainingloadmustbethemostvaluableloadsizingwithmostC sthattheknapsackhasfromthen 1originalitemsplussj spoundsofitemj Thisproblemcaneasilybesolvedusingthefollowinggreedystrategy Foreachitemcomputeyi vi si theratioofitsvaluetoitssize Sorttheitemsbydecreasingratio andfilltheknapsackwithasmuchaspossiblefromthefirstitem thensecond andsoforth NorthChinaElectricPowerUniversity 例 Knapsackproblem n 3 C 40 w1 w2 w3 28 15 24 p1 p2 p3 35 25 24 Thereare5feasiblesolutionsasfollow x1 x2 x3 wixi pixi n i 1 n i 1 1 4 5 0 4055 1 2 1 1 3 3750 5 1 28 1 1 4050 254 5 7 1 5 24 40555 25 28 1 0 4056 25 3greedymethods 1 choosethemostvaluableitemeverytime x1 x2 x3 1 4 5 0 totalvalue 55 2 choosethelowestweightitemeverytime x1 x2 x3 1 28 1 1 totalvalue 50 25 3 choosethemostvaluableiteminaunitweighteverytime x1 x2 x3 25 28 1 0 totalvalue 56 25 NorthChinaElectricPowerUniversity Thealgorithm voidgreedy knapsack float s float v float x intn floatC s 1 n andv 1 n hasbeensortedsuchthats i v i s i 1 v i 1 for i 1 i n i x i 0 cu C i 1 while i n NorthChinaElectricPowerUniversity Thisproblemrevealsmanyofthecharacteristicsofagreedyalgorithmdiscussedabove Thealgorithmconsistsofasimplestiterationprocedurethatselectsthatitemwhichproducesthelargestimmediategainwhilemaintaingfeasibility ExampleofFractionalKnapsack Bothknapsackproblemsexhibittheoptimalsubstructureproperty 1 For0 1knapsackproblem ifweremoveitemjfromthisload theremainingloadmustbeatmostvaluableitemsweighingatmostC wjfromn 1items 2 Forfractionalone ifweremoveaweightwofoneitemjfromtheoptimalload thentheremainingloadmustbethemostvaluableloadweighingatmostC wthatthethiefcantakefromthen 1originalitemspluswj wpoundsofitemj NorthChinaElectricPowerUniversity NorthChinaElectricPowerUniversity 4Theshortestpathproblem LetG V E beadirectedgraphinwhicheachedgehasanonnegativelength andadistinguishedvertexscalledthesource Thesingle sourceshortestpathproblem orsimplytheshortestpathproblem istodeterminethedistancefromstoeveryothervertexinV wherethedistanceformvertexstovertexxisdefinedasthelengthofashortestpathfromstox Forsimplicity wewillassumethatV 1 2 n ands 1 ThisproblemcanbesolvedusingagreedytechniqueknownasDijkstra salgorithm Initially thesetofverticesispartitionedintotwosetsX 1 andY 2 3 n TheintentionisthatXcontainsthesetofverticeswhosedistancefromthesourcehasbeendedetermined NorthChinaElectricPowerUniversity Ateachstep weselectavertexy YwhosedistanceformthesourcevertexhasbeenfoundandmoveittoX AssociatedwitheachvertexyinYisalabel y whichisthelengthofashortestpaththatpassesonlythroughverticesinX Onceavertexy Yismovedto thelabelofeachvertexw Ythatisadjacenttoyisupdatedindicatingthatashorterpathtowviayhasbeendiscovered Throughoutthissection foranyvertexv V v willdenotethedistanceformthesourcevertextov Aswillbeshownlater attheendofthealgorithm v v foreachvertexv V Asketchofthealgorithmisgivenbelow NorthChinaElectricPowerUniversity X 1 Y V 1 fory 2tonifyisadjacentto1elseendforforj 1ton 1letbesuchthatisminimumforeachedge y w ifandthenendforendfor Example NorthChinaElectricPowerUniversity a 1 12 4 10 19 17 8 13 17 voidshortpath floatcost intv1 intn costistheadjacentmatrixofG i isthecurrentshortestfromv1toi path i isthecorrespondingpath maxis for y 2 i n i y cost 1 y if y max path y v1 y elsepath y X v1 num 0 while num n 1 wm max y v1 for j 2 j n j selecttheminimumof y if jinX ifjisnotbelongtoSif j wm y j wm j selectybaseon j X X y addytoXfor w 2 w n w modify andpath if winX if y cost y w w w y cost y w path w path y w num NorthChinaElectricPowerUniversity Correctness Lemma InalgorithmDijkstra whenavertexyischoseninstep8 ifitslabelisfinitethen ProofByinductionontheordersinwhichverticesleavethesetYandenterX Thefirstvertextoleaveis1andwehave AssumethatthestatementistrueforallverticeswhichleftYbeforey Sinceisfinite theremustexistsapathfrom1toywhoselengthis Now weshowthat Letbeashortestpathfrom1toy wherexistherightmostvertextoleaveYbeforey Wehave TheoremGivenadirectedgraphwithnonnegativeweightsonitsedgesandasourcevertexs AlgorithmDijkstrafindsthelengthofthedistancefromstoeveryothervertexin n2 time NorthChinaElectricPowerUniversity 5Minimumcostspanningtreesproblem Definition LetG V E beaconnectedundirectedgraphwithweightsonitsedges Aspanningtree V T ofGisatreewhichcontainsalltheverticesofG IfthesumoftheweightsoftheedgesinTisminimum then V T iscalledaminimumcostspanningtreeorsimplyaminimumspanningtree Therearemanysituationsinwhichminimumspanningtressmustbefound Wheneveronewantstofindthecheapestwaytoconnectasetofterminals bethecities electricalterminalscomputersorfactoriesbyusing say roads wires ortelephonelines asolutionisaminimumspanningtreeforthegraphwithanedgeforeachpossibleconnectionweightedbythecostofthatconnection NorthChinaElectricPowerUniversity NorthChinaElectricPowerUniversity NorthChinaElectricPowerUniversity Example NorthChinaElectricPowerUniversity Algorithm sortingtheedgesinnondecreasingorderbyweight foreachedge VMakeset endforT while T n 1let x y bethenextedgeofEiffind x find y thenadding x y toTUNION x y endifendwhile defineVnum defineEnumstructTreeEdge intstart 边中第一个顶点的编号intend 边中另外一个顶点的编号floatweight 边上的权值 voidKruskal graphg TreeEdgetree intn n为图中的顶点数 intComponent Vnum 判断新选择的边是否和已有的边构成回路TreeEdgeedge Enum for i 1 i n i Component i i m 0 m为图中的边数for i 1 i n 1 i for j i 1 j n j 无向图的连接矩阵为对称阵 只扫描其上三角部分 if g arcs i j maxint m edge m start i edge m end j edge m weight g arcs i j Sort edge m 对m条边按照权值从小到大排序v 1 当前考察的边的序号floatsum 0 for k 1 k n 1 k while Component edge v start Component edge v end v 如果该边的两个顶点同属一个连通分量 则考察下一条边tree k edge v 将当前扫描到的边加入到生成树中sum sum tree k weight for j 1 j n j 将两个连通分量合并为一个连通分量if Component j Component edge v end Component j Component edge v start v cout 最小生成树中的边如下 n 起点终点权值 n for i 1 i n 1 i cout tree i start tree i end tree i weight cout 最小生成树上各边的权值之和为 sum NorthChinaElectricPowerUniversity Weobservethatcost e cost e forotherwisee wouldhavebeenaddedbeforesinceitdoesnotcreateacyclewiththeedgesofT whichcontainstheedgesofT Ifwenowconstruct wenoticethat Moreover T isthesetofedgesinaminimumcostspanningtreesinceeisofminimumcostamongalledgesconnectingtheverticesXwiththoseinV X NorthChinaElectricPowerUniversity Prim sAlgorithm Thealgorithmgrowsthespanningtreestartingfromanarbitraryvertex LetG V E whereforsimplicityVistakentobethesetofintegers 1 2 n Thealgorithmbeginsbycreatingtwosetofvertices X 1 andY 2 3 n Then itgrowsaspanningtree oneedgeatatime Ateachstep itfindsanedge x y ofminimumweight whereandandmovesyfromYtoX ThisedgeisaddedtothecurrentminimumspanningtreeedgesinT ThisstepisrepeateduntilYbecomesempty Thealgorithmisoutlinedbelow ItfindsthesetofedgesTofaminimumcostspanningtree NorthChinaElectricPowerUniversity Example NorthChinaElectricPowerUniversity Thecostofanedge x y denotedbyc x y isstoredatthenodeforyintheadjacencylistcorrespondingofx TwosetsXandYwillbeimplementedasbooleanvectorsX 1 n andY 1 n Initially X 1 1andY 1 0 andforalli 2 i nX i 0 Y i 1 Thus operationisimplementedbysettingX y to1 andtheoperationisimplementedbysettingY y to0 If x y isanedgesuchthatand wewillcallyaborderingvertex BorderingverticesarecandidatesforbeingmovedfromYtoX Letybeaborderingvertex Thenthereisatleastonevertexthatisadjacenttoy Wedefinetheneighborofy denotedbyN y tobethatvertexxinXwiththepropertythatc x y isminimumamongallverticesadjacenttoyinX WealsodefineC y c y N y Thus N y isthenearestneighbortoyinxandC y isthecostoftheedgeconnectingyandN y NorthChinaElectricPowerUniversity T X 1 Y V 1 fory 2tonifyisadjacentto1thenelseendforforj 1ton 1LetbesuchthatC y isminimumforeachvertexthatisadjacenttoyifc y w C w thenendforendfor NorthChinaElectricPowerUniversity Algorithm voidPrim graphg TreeEdgetree intn intm intv g为图的邻接矩阵表示 n为图中的顶点个数 m为图中的边数 v为初始加入的顶点 floatLowerCost Vnum 用于保存V T 与V V T 中各顶点构成的边中权值最小的边的集合intCloseVertex Vnum 用于保存在V T 中依附于该边的顶点的集合floatsum 0 从图中第v个顶点出发 按照Prim算法生成最小生成树for i 1 i n i LowerCost i g arcs v i CloseVertex i v LowerCost v 0 CloseVertex v v for i 1 i n i 寻找一个顶点属于V T 而另一个顶点不属于V T 的边中权值最小的边mincost maxint j 1 k 1 while j n if LowerCost j 0 Correctness WeprovebyinductiononthesizeofTthat X T isasubtreeofaminimumcostspanningtree Initially T andthestatementistriviallytrue Assumethestatementistruebeforeaddingtheedgee x y inStep9ofthealgorithm whereand Letand WewillshowthatG X T isalsoasubsetofsomeofminimumcostspanningtree First WeshowthatG isatree SinceeisconnectedtoexactlyonevertexinX namelyx andsincebytheinductionhypothesis X T isatree G isconnectedandhasnocycles i e atree NorthChinaElectricPowerUniversity WenowshowthatG isasubtreeofaminimumcostspanningtree Bytheinductionhypothesis whereT isthesetofedgesinaminimumspanningtreeG V T IfT containse thenthereisnothingprove Otherwise containsexactlyonecyclewithebeingoneofitsedges Sincee x y connectsonevertexinXtoanothervertexinY T mustalsocontainanotheredgee w z suchthatand Ifwenowconstruct wenoticethat Moreover T isthesetofedgesinaminimumcostspanningtreesinceeisofminimumcostamongalledgesconnectingtheverticesinXandthoseinY NorthChinaElectricPowerUniversity 6汽车加油问题 已知 一辆汽车加满油后可行使n公里 而旅途中有若干个加油站 试设计一个有效算法 指出应该在那个加油站停靠加油 使沿途加油次数最少 然后证明算法能产生最优解 分析与解答 用1 2 m表示旅途中的m个加油站 0表示出发地 用m 1表示目的地 s 0 m 1 表示加油站至出发地距离 s 0 s 1 s 2 s m s m 1 求解目标 求整数数列1 i1 i2 ik m 使汽车在加油站i1 i2 ik 依次停靠加油 并且加油次数最少 即k最小 问题具有最优子结构性质 设1 i1 i2 ik m是所述问题的一个最优解 容易看出i2 ik是当前出发地为i1时的一个最优解 否则将导致i1 i2 ik不是原问题的最优解 NorthChinaElectricPowerUniversity 贪心选择性质 采用汽车每次加满油后行使尽可能远的贪心选择策略 设1 i1 i2 ik m 是一个最优解 如果汽车在加油站i1不停靠加油还可以行使至i1以后的加油站j1再加油 则我们在j1站停靠加油 其后再按最优解提供的停靠站