中南大学算法分析与设计复习课件.ppt

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

1、JinZheng,CentralSouthUniversity1Branch-and-boundJinZheng,CentralSouthUniversity2BranchandBoundAnenhancementofbacktrackingSimilarityAstatespacetreeisusedtosolveaproblemDifferenceusedonlyforoptimizationproblems.ThebacktrackingrequirestheusingofDFStraversalandisusedfornonoptimizationpro

2、blems.Branchandbound:doesnotlimitustoanyparticularwayoftraversingthetree(Best-first)JinZheng,CentralSouthUniversity3Branchandbound(cont.)Branchingstrategy:howtopartitionsolutionspaceNodeselectionstrategy:sequenceofexploringnodes:depthfirst(triestoobtainasolutionfast)breadth/bestbound

3、first(triestofindthebestsolution)whichnodestoexploreSelectingthenodewiththebestestimatedcostamongallnodes.Combinedepth-firstsearchandbreadth-firstsearch.JinZheng,CentralSouthUniversity4BranchandBoundComparedtobacktracking,branch-and-boundrequirestwoadditionalitems.Awaytoprovide,forev

4、erynodeofastate-space-tree,aboundonthebestvalueoftheobjectivefunctiononanysolutionthatcanbeobtainedbyaddingfurtheromponentstothepartialsolutionrepresentedbythenode.Thevalueofthebestsolutionseensofar.JinZheng,CentralSouthUniversity5ThemainideaSetupaboundingfunction,whichisusedtocomput

5、eabound(forthevalueoftheobjectivefunction)atanodeonastate-spacetreeanddetermineifitispromisingPromising(iftheboundisbetterthanthevalueofthebestsolutionsofar:expandbeyondthenode.Nonpromising(iftheboundisnobetterthanthevalueofthebestsolutionsofar--:notsmallerforaminimizationproblemandn

6、otlargerforamaxmizationproblem):notexpandbeyondthenode(pruningthestate-spacetree).JinZheng,CentralSouthUniversity6StartIb=10a￫1Ib=17a￫2Ib=10a￫3Ib=20a￫4Ib=18b￫1Ib=13b￫3Ib=14b￫4Ib=17c￫3Ib=13c￫4Ib=20d￫4Cost=13012345678910边界（下界）的选择：初始节点边界：包括最优解在内，任何解的成本都不会小于矩阵每行中的最小元素的和。节点其它边界：实际产生的成本+还要

7、付出的最小成本（估计）JinZheng,CentralSouthUniversity7Givenasetofpointsandtheirpairwisedistances,thetaskistofindashortesttourthatvisitseachpointexactlyonce.ItisNP-complete.ThetravelingsalespersonoptimizationproblemJinZheng,CentralSouthUniversity8TravelingSalesmanProblem—BoundingFunction边界（下界）函数

8、的选择：初如节点边界：对