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

《国外算法设计与分析课件16.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、BacktrackingandBranch-and-BoundExpectedOutcomesDescribetheideasofbacktrackingandbranchandboundtechniquesSolvesomedifficultproblemsbythebacktrackingtechnique2ExactSolutionsexhaustivesearch(bruteforce)GenerateALLcandidatesolutionsandidentifyonewithadesiredpropertyusefulonlyforsmall

2、instancesImprovementoverexhaustivesearch:backtrackingandbranch-and-boundTheideaconstructcandidatesolutionsonecomponentatatimebasedonacertainrule.Ifnopotentialvaluesoftheremainingcomponentscanleadtoasolution,theremainingcomponentsarenotgeneratedatall.DifferenceApplytodifferentprob

3、lems(non-optimizationandoptimizationproblems)Thewayanewcomponentisgenerated.Advantageanddisadvantagescutdownonthesearchspaceprovidefastsolutionsforsomeinstancestheworstcaseisstillexponential3BacktrackingConstructthestatespacetree:RootrepresentsaninitialstateNodesreflectspecificch

4、oicesmadeforasolution’scomponents.PromisingandnonpromisingnodesleavesExplorethestatespacetreeusingdepth-firstsearch“Prune”non-promisingnodesdfsstopsexploringsubtreerootedatnodesleadingtonosolutionsand...“backtracks”toitsparentnode4Example:Then-QueenproblemPlacenqueensonannbynches

5、sboardsothatnotwoofthemareonthesamerow,column,ordiagonal5StateSpaceTreeoftheFour-queensProblem6Them-ColoringProblemandHamiltonianProblem2-color3-colorHamiltonianCircuit(usealphabetordertobreaktheties)cdaeb7CommentsExhaustivesearchandbacktrackingExhaustivesearchisguaranteedtobever

6、yslowineveryprobleminstance.Backtrackingprovidesthehopetosolvesomeprobleminstancesofnontrivialsizesbypruningnon-promisingbranchesofthestate-spacetree.Thesuccessofbacktrackingvariesfromproblemtoproblemandfrominstancetoinstance.Backtrackingpossiblygeneratesallpossiblecandidatesinan

7、exponentiallygrowingstate-spacetree.Butstillitprovidesasystematictechniquetodoso.8BranchandBoundAnenhancementofbacktrackingSimilarityAstatespacetreeisusedtosolveaproblem.DifferenceThebranch-and-boundalgorithmdoesnotlimitustoanyparticularwayoftraversingthetreeandisusedonlyforoptim

8、izationproblemsThebacktrackingalgorithmr