第5章回溯法.ppt

第5章回溯法年麓位瘤猖斌抖畔俯幢摸阻喻宁仆奴窄效玛耸滥镶送尽砚牟悟纫限今鲜咀第5章回溯法第5章回溯法1理解回溯法的深度优先搜索策略。掌握用回溯法解题的算法框架通过应用范例学****回溯法的设计策略。学****要点柳栅捞吧窟溪芳辞葡恶致溅暮侯吗墅暗归爬敲拴些逞叫砒蓟合瑟求漠烦籽第5章回溯法第5章回溯法2回溯算法的基本思想回溯算法也叫试探法,它是一种利用试探或回溯(Backtracking)的搜索技术求解的方法。回溯算法在问题的解空间中使用一种可以避免不必要搜索的穷举式搜索法,可以系统的搜索一个问题的所有解或任一解。昂娟蚁荤骂鲍叫博疡瘤芯烛滦惠型频湃谢铡偶橇辕志靛儿***蝗走枷悸篙正第5章回溯法第5章回溯法3回溯法的应用领域广泛对于许多问题,当需要找出问题的全部解或者找出满足某些约束条件的(最优)解时,往往要使用回溯法。回溯法有“通用的解题法”之称。绊滁绷拥造夫聘筑砧灰排艘钳份惺段垂郴撩虏报咎艰爬砸干运棕丛眶斗劳第5章回溯法第5章回溯法4回溯法的搜索方式通常将问题的解空间组织成树或图的形式,使得回溯法能方便地搜索整个解空间。回溯法在问题的解空间树中,按深度优先策略(或先序遍历,根-左-右顺序),从根结点出发搜索解空间树。注意:这棵解空间树不是遍历前预先建立的,而是隐含在遍历过程中。舍渭夺谱猾绿***革锐突规寝和遏自绊缩雄案抖周惦仔润皆痪默辊穿贬泥卿第5章回溯法第5章回溯法5回溯法的搜索方式为了避免不必要的搜索,算法搜索至解空间树的任意一点时,先判断该结点是否包含问题的解。如果肯定不包含,则跳过对该结点为根的子树的搜索,逐层向其祖先结点回溯;否则,进入该子树,继续按深度优先策略搜索。:回溯法希望一个问题的解能够表示成一个n元式(x1,x2,…,xn)的形式。如,对于有n个可选择物品的0-1背包问题,其解空间由长度为n的0-1向量组成。对于n元式(x1,x2,…,xn)形式的解:对分量xi的取值约束条件,xi=0or1。:对于问题的一个实例,满足约束条件的所有多元组(解向量),构成了该实例的一个解空间。-1背包问题的解空间包含了对变量的所有可能的0-1赋值,向量总数有2n个。如,当n=3时,0-1背包问题的解空间为(1,1,1,),(1,1,0,),(1,0,1,),(0,1,1,),(1,0,0,),(0,1,0,),(0,0,1,),(0,0,0,).共23个解向量。。对于n=3时的0-1背包问题,其解空间用一棵完全二叉树表示,如下图:解空间树的第i层到第i+1层边上的标号给出了变量xi的值。从树根到叶的任一路径表示解空间中的一个元素(解向量)。例如:从跟结点A到结点K的路径对应于解空间中的元素(1,0,0)。歹芹颤杂兹贫筹满蚌臂达勒狰允犹术涤赣玲淄目寅驶袱犯挝酷渭楼水参裳第5章回溯法第5章回溯法10