国外算法设计与分析课件16

BacktrackingandBranch-and-Bound2ExpectedOutcomesDescribetheideasofbacktrackingandbranchandboundtechniquesSolvesomedifficultproblemsbythebacktrackingtechnique3ExactSolutionsexhaustivesearch(bruteforce)GenerateALLcandidatesolutionsandidentifyonewithadesiredpropertyusefulonlyforsmallinstancesImprovementoverexhaustivesearch:backtrackingandbranch-and-boundTheideaconstructcandidatesolutionsonecomponentatatimebasedonacertainrule.Ifnopotentialvaluesoftheremainingcomponentscanleadtoasolution,theremainingcomponentsarenotgeneratedatall.DifferenceApplytodifferentproblems(non-optimizationandoptimizationproblems)Thewayanewcomponentisgenerated.Advantageanddisadvantagescutdownonthesearchspaceprovidefastsolutionsforsomeinstancestheworstcaseisstillexponential4BacktrackingConstructthestatespacetree:RootrepresentsaninitialstateNodesreflectspecificchoicesmadeforasolution’scomponents.PromisingandnonpromisingnodesleavesExplorethestatespacetreeusingdepth-firstsearch“Prune”non-promisingnodesdfsstopsexploringsubtreerootedatnodesleadingtonosolutionsand...“backtracks”toitsparentnode5Example:Then-QueenproblemPlacenqueensonannbynchessboardsothatnotwoofthemareonthesamerow,column,ordiagonal6StateSpaceTreeoftheFour-queensProblem7Them-ColoringProblemandHamiltonianProblem2-color3-colorHamiltonianCircuit(usealphabetordertobreaktheties)cdaeb8CommentsExhaustivesearchandbacktrackingExhaustivesearchisguaranteedtobeveryslowineveryprobleminstance.Backtrackingprovidesthehopetosolvesomeprobleminstancesofnontrivialsizesbypruningnon-promisingbranchesofthestate-spacetree.Thesuccessofbacktrackingvariesfromproblemtoproblemandfrominstancetoinstance.Backtrackingpossiblygeneratesallpossiblecandidatesinanexponentiallygrowingstate-spacetree.Butstillitprovidesasystematictechniquetodoso.9BranchandBoundAnenhancementofbacktrackingSimilarityAstatespacetreeisusedtosolveaproblem.DifferenceThebranch-and-boundalgorithmdoesnotlimitustoanyparticularwayoftraversingthetreeandisusedonlyforoptimizationproblemsThebacktrackingalgorithmrequirestheusingofDFStraversalandisusedfornonoptimizationproblems.10BranchandBoundTheideaSetupaboundingfunction,whichisusedtocomputeabound(forthevalueoftheobjectivefunction)atanodeonastate-spacetreeanddetermineifitispromisingPromising(iftheboundisbetterthanthevalueofthebestsolutonsofar):expandbeyondthenode.Nonpromising(iftheboundisnobetterthanthevalueofthebestsolutionsofar):notexpandbeyondthenode(pruningthestate-spacetree).11TravelingSalesmanProblemAnobviouswaytoconstructthestate-spacetreeAnode:anodeinthestate-spacetree;avertex:avertexinthegraph.Anodethatisnotaleafrepresentsallthetoursthatstartwiththepathstoredatthatnode;eachleafrepresentsatour(ornonpromisingnode).Branch-and-bound:weneedtodeterminealowerboundforeachnodeForexample,todeterminealowerboundfornode[1,2]meanstodeterminealowerboundonthelengthofanytourthatstartswithedge1—2.Expandeachpromisingnode,andstopwhenallthepromisingnodeshavebeenexpanded.Duringthisprocedure,pruneallthenonpromisingnodes.Promisingnode:thenode’slowerboundislessthancurrentminimumtourlength.Nonpromisingnode:thenode’slowerboundisNOlessthancurrentminimumtourlength.12TravelingSalesmanProblem—BoundingFunction1Becauseatourmustleaveeveryvertexexactlyonce,alowerboundonthelengthofatouristhesumoftheminimum(lowerbound)costofleavingeveryvertex.Thelowerboundonthecostofleavingvertexv1isgivenbytheminimumofallthenonzeroentriesinrow1oftheadjacencymatrix.…Thelowerboundonthecostofleavingvertexvnisgivenbytheminimumofallthenonzeroentriesinrownoftheadjacencymatrix.Note:Thisisnottosaytha