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

JinZheng,CentralSouthUniversity1Branch-and-boundJinZheng,CentralSouthUniversity2BranchandBoundAnenhancementofbacktrackingSimilarityAstatespacetreeisusedtosolveaproblemDifferenceusedonlyforoptimizationproblems.ThebacktrackingrequirestheusingofDFStraversalandisusedfornonoptimizationproblems.Branchandbound:doesnotlimitustoanyparticularwayoftraversingthetree(Best-first)JinZheng,CentralSouthUniversity3Branchandbound(cont.)Branchingstrategy:howtopartitionsolutionspaceNodeselectionstrategy:sequenceofexploringnodes:depthfirst(triestoobtainasolutionfast)breadth/bestboundfirst(triestofindthebestsolution)whichnodestoexploreSelectingthenodewiththebestestimatedcostamongallnodes.Combinedepth-firstsearchandbreadth-firstsearch.JinZheng,CentralSouthUniversity4BranchandBoundComparedtobacktracking,branch-and-boundrequirestwoadditionalitems.Awaytoprovide,foreverynodeofastate-space-tree,aboundonthebestvalueoftheobjectivefunctiononanysolutionthatcanbeobtainedbyaddingfurtheromponentstothepartialsolutionrepresentedbythenode.Thevalueofthebestsolutionseensofar.JinZheng,CentralSouthUniversity5ThemainideaSetupaboundingfunction,whichisusedtocomputeabound(forthevalueoftheobjectivefunction)atanodeonastate-spacetreeanddetermineifitispromisingPromising(iftheboundisbetterthanthevalueofthebestsolutionsofar:expandbeyondthenode.Nonpromising(iftheboundisnobetterthanthevalueofthebestsolutionsofar--:notsmallerforaminimizationproblemandnotlargerforamaxmizationproblem):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边界（下界）的选择：初始节点边界：包括最优解在内，任何解的成本都不会小于矩阵每行中的最小元素的和。节点其它边界：实际产生的成本+还要付出的最小成本（估计）JinZheng,CentralSouthUniversity7Givenasetofpointsandtheirpairwisedistances,thetaskistofindashortesttourthatvisitseachpointexactlyonce.ItisNP-complete.ThetravelingsalespersonoptimizationproblemJinZheng,CentralSouthUniversity8TravelingSalesmanProblem—BoundingFunction边界（下界）函数的选择：初如节点边界：对于每一个城市，求出该城市到距离其最近的另外两个城市的距离之和，并把所有城市的该距离和除以2取整。其它节点边界：实际产生的成本+还要付出的最小成本（估计）JinZheng,CentralSouthUniversity9TravelingsalesmanaIb=14a,bIb=14a,ca,dIb=16a,eIb=19012345679a,b,cIb=16a,b,eIb=19a,b,dIb=168a,b,c,d,e,al=241011bisnotbeforeca,b,c,e,d,al=19a,b,d,c,e,aI=24a,b,d,e,c,aI=16JinZheng,CentralSouthUniversity10NotesFindingagoodboundingisnotasimpletask.Ontheonehand.Wewantthisfunctiontobeeasytocompute.Ontheotherhand,itcann’tbetoosimplistic.—otherwise,itwouldfailinitsprincipaltasktopruneasmanybranchesofastate-spacetreeassoonaspossible.JinZheng,CentralSouthUniversity11The0/1knapsackproblemPositiveintegerP1,P2,…,Pn(profit)W1,W2,…,Wn(weight)M(capacity)maximizePXiiin1subjecttoWXMiiin1Xi=0or1,i=1,…,n.JinZheng,CentralSouthUniversity12Knapsackproblem先按单位价值对待处理的物品进行排序v1/w1≥v2/w2≥…≥vn/wnboundfunction（边界函数（上界））:ub=v+(W-w)(vi+1/wi+1)即：已经选择物品的总价值v+背包的剩余承重W-w与剩下物品的最佳单位回报vi+1/wi+1的乘积。JinZheng,CentralSouthUniversity13ExampleItemweightvaluevalue/weight144010274263525543124W=10JinZheng,CentralSouthUniversity14w=0,v=0Ub=100w=4,v=40Ub=76w=0,v=0Ub=60w=11w=4,v=40Ub=70w=9,v=65Ub=69w=4,v=40Ub=64w=12w=9,v=65Value=65With1W/o1JinZheng,CentralSouthUniversity15HomeworkExercise11.2:5,7