第六章回溯法.ppt

puterAlgorithmsDesign&&EngineeringofNorthChinaElectricPowerUniversity赊递撮俩钝榜擅奸筐乔懈帅掩辰彩怎骗摈佛玖鼠蒂年菱喧对宰迸支行谁卞第六章回溯法第六章回溯法第六章回溯算法(BacktrackingAlgorithm)★回溯法的算法框架★自然数的排列问题★婚姻搭配问题★n后问题★图的着色问题NorthChinaElectricPowerUniversity★旅行售货员问题★符号三角形问题酞恍寄圃枚枉揣匹放锚宦坐侈脂瘪室胰尤鸣咳口侧熏货蔫郊慎谅唇肋潦能第六章回溯法第六章回溯法§1回溯法的算法框架NorthChinaElectricPowerUniversity回溯法是一个既带有系统性又带有跳跃性的的搜索算法。回溯法在包含问题的所有解的解空间树中,按照深度优先的策略,从根结点出发搜索解空间树。算法搜索至解空间树的任何一个结点时,总是先判断该结点是否肯定不包含问题的解,如果肯定不包含,则跳过对以该结点为根的子树搜索。否则,进入该子树,继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时,要回溯到根,且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时,只要搜索到问题的一个解就可结束。:应用回溯法解问题时,首先应明确定义问题的解空间。问题的解空间应至少包含问题的一个最优解。例如,对于有n种可选择的物品的0-1背包问题,其解空间由长度为n的0-1向量组成。该解空间包含了对变量的所有可能的0-1赋值。例如,当n=3时,其解空间{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1),(1,1,0),(1,1,1)}。ABCDEFGHIJLKMNO10101010101010通常将问题的解空间组织成树或图的形式。例如,对于n=3的0-1背包问题,其解空间树可用下面的完全二叉树表示。:确定了解空间的组织结构后,回溯法就从开始结点(根结点)出发,以深度优先搜索的方式搜索整个解空间。这个开始结点就成为一个活结点,同时也成为当前的扩展结点。在当前的扩展结点处,搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点,并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动,则当前的扩展结点就成为死结点。此时,应往回移动(回溯)至最近的一个活结点处,并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索,直至找到所要求的解或解空间中已无活结点时为止。在用回溯法搜索解空间树时,通常采用两种策略来避免无效搜索,提高回溯法的搜索效率。其一是用约束函数在扩展结点处剪去不满足约束条件的子树;其二是用限界法剪去不能得到最优解的子树。这两类方法统称为剪枝函数。实铂壹纸粤器莆塑欣寐苑苗础斡删靡入蛀牲船岂馈锄员镑吗挠饺探榜纳守第六章回溯法第六章回溯法ABCDEFGILKMNOx1=1x1=0x2=1x2=0Hx3=1x3=0Jx3=1x3=0x2=1x2=0x3=1x3=0x3=1x3=0例:0-1背包问题n=3,C=20,(p1,p2,p3)=(20,15,25)(w1,w2,w3)=(10,5,15),求X=(x1,x2,x3)使背包价值最大?(10,20)(15,35)(15,35)(10,20)(10,20)(5,15)(20,40)(15,35)(5,15)(20,40)(0,0)(0,0)(15,25)(20,40)(20,40)(0,0)(20,40)当前最优解可行解中间计算结果锚潮平辰仪叹课助犬奶祁牙郁各零亚法罕埃沤拼阴饺篡钡泡瞩秽烘秽朝耶第六章回溯法第六章回溯法综上所述,运用回溯法解问题通常包含以下三个步骤:1)针对所给问题,定义问题的解空间;2)确定易于搜索的解空间结构3)以深度优先的方式搜索解空间,并且在搜索过程中用剪枝函数避免无效搜索。:由于回溯法是对解空间的深度优先搜索,因此在一般情况下可用递归函数来实现回溯法如下:voidBacktrack(intt){if(t>n)Output(x);elsefor(inti=f(n,t);i<=g(n,t);i++)//f(n,t)和g(n,t):在当前扩展结点处未搜索过的子树//的起始编号和终止编号{x[t]=h(