计算机算法设计与分析第5章回溯法

《计算机算法设计与分析第5章回溯法》由会员分享，可在线阅读，更多相关《计算机算法设计与分析第5章回溯法（66页珍藏版）》请在金锄头文库上搜索。

1、1,第5章 回溯法,2,理解回溯法的深度优先搜索策略。 掌握用回溯法解题的算法框架 通过应用范例学习回溯法的设计策略。,学习要点,3,回溯算法的基本思想,回溯算法也叫试探法，它是一种利用试探或回溯(Backtracking)的搜索技术求解的方法。 回溯算法在问题的解空间中使用一种可以避免不必要搜索的穷举式搜索法，可以系统的搜索一个问题的所有解或任一解。,4,回溯法的应用领域广泛,对于许多问题，当需要找出问题的全部解或者找出满足某些约束条件的（最优）解时，往往要使用回溯法。 回溯法有“通用的解题法”之称。,5,回溯法的搜索方式,通常将问题的解空间组织成树或图的形式，使得回溯法能方便地搜索整个解空

2、间。 回溯法在问题的解空间树中，按深度优先策略（或先序遍历，根-左-右顺序），从根结点出发搜索解空间树。 注意：这棵解空间树不是遍历前预先建立的，而是隐含在遍历过程中。,6,回溯法的搜索方式,为了避免不必要的搜索，算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。 如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯； 否则，进入该子树，继续按深度优先策略搜索。,7,5.1 回溯法的算法框架 1.问题的解空间,问题的解向量：回溯法希望一个问题的解能够表示成一个n元式(x1,x2,xn)的形式。 如，对于有n个可选择物品的0-1背包问题，其解空间由长度为n的0-1向量

3、组成。 对于n元式(x1,x2,xn)形式的解： 对分量xi的取值约束条件， xi=0 or 1。,8,5.1 回溯法的算法框架 1.问题的解空间,解空间：对于问题的一个实例，满足约束条件的所有多元组(解向量)，构成了该实例的一个解空间。,9,5.1 回溯法的算法框架 1.问题的解空间,0-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个解向量。,10,1.问

4、题的解空间,在此将解空间组织成树的形式。 对于n=3时的0-1背包问题，其解空间用一棵完全二叉树表示，如下图：,解空间树的第i层到第i+1层边上的标号给出了变量xi的值。,从树根到叶的任一路径表示解空间中的一个元素(解向量)。,例如：从跟结点A到结点K的路径对应于解空间中的元素(1,0,0)。,11,5.1 回溯法的算法框架 2.回溯法的基本思想,用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。 确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索（动态产生）整个解空间。,12,5.1 回溯法的算法框架 2.回溯法的基本思想,从开始结点（根结点）出发，

5、 这个开始结点就成为一个活结点，同时也成为当前的扩展结点。 活结点:一个自身已生成但其儿子还没有全部生成的节点称做活结点。 扩展结点:一个正在产生儿子的结点称为扩展结点。,13,5.1 回溯法的算法框架 2.回溯法的基本思想,在当前扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。 如果在当前扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。 死结点:一个所有儿子已经全部产生的结点称做死结点。,14,5.1 回溯法的算法框架 2.回溯法的基本思想,当前扩展结点成为死结点时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展

6、结点。 回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解，或解空间中已无活结点时终止。,15,2.回溯法的基本思想 例1： 0-1背包,以n=3时的0-1背包为例，考虑如下实例：w=16,15,15,p=45,25,25,c=30。 从其解空间树的根结点开始搜索其解空间。 开始时，根结点A是唯一的活结点，也是当前扩展结点。 在当前扩展结点A处，可纵深移至B或C。,16,2.回溯法的基本思想 例1： 0-1背包,在当前扩展结点A处，可纵深移至B或C。 选择先移至B，即选取物品w1，此时，A、B均为活结点，B成为当前扩展结点。在B处剩余背包容量是r=30-16=14，获取价值45。

7、从B可纵深移至D或E，先考虑移至D，但现仅有的背包容量容不下物品w2，故移至D导致一个不可行解。 而从B移至E不占用背包容量，因而可行。从而我们选择移至E。此时E成为新的扩展结点。,17,2.回溯法的基本思想 例1： 0-1背包,此时，A、B和E是活结点。在E处容量仍为14，所得价值仍为45。 从E可以移至J和K。移至J会导致一个不可行解，而移向K是可行的，于是移至K，K成为新的扩展结点。 由于K是一个叶结点，所以我们得到一个可行解(1,0,0),v=45。,18,2.回溯法的基本思想 例1： 0-1背包,由于从K已无法纵深扩展，故K成为一个死结点，所以返回（回溯）至E（离K最近的一个活结点）

8、。 而E也没有可扩展的结点，也成为了死结点。接下来，再继续回溯，返回至B处，同样B也成为死结点。再返回 A，从A可扩展移至C。 从A移至C，r=30,获取价值0。,19,2.回溯法的基本思想 例1： 0-1背包,从C可移至F或G，令先移至F，则F成为新的扩展结点，此时有活结点A,C,F。在F有r=30-w2=15,获取价值25。 从F向纵深移至L处，有r=0,获取价值25+25=50。L是叶结点，即获得一可行解，又获取了至今最高价值，因此记录该可行解。,20,2.回溯法的基本思想 例1： 0-1背包,L不可扩展，返回F处。按此方式继续搜索，可搜索遍整个解空间。 搜索结束后找到的最好解是相应0-

9、1背包问题的最优解。,21,2.回溯法的基本思想 例2： 旅行售货员问题,旅行售货员问题： 某售货员要到若干城市去推销商品，已知各城市之间的路程（或旅费）。他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程最短（或旅费最少） 。 该问题可以用图论的语言来进行形式化描述。,22,2.回溯法的基本思想 例2： 旅行售货员问题,设G=(V,E)是一个带权图。图中各边的费用（权）为一正数。图中一条周游路线是包括V中每个顶点在内的一条回路。其费用就是该路线上所有边的费用总和。 所谓旅行售货员问题就是要在图G中找出一条有最小费用的周游路线。,23,2.回溯法的基本思想 例2： 旅行售

10、货员问题,给定一个有n个顶点的带权图G，旅行售货员问题就是要找出G的费用（权）最小的周游路线。,左图是一个4顶点无向带权图。如：顶点序列1,2,4,3,1；1,3,2,4,1和1,4,3,2,1是该图中3条不同的周游路线。,24,2.回溯法的基本思想 例2： 旅行售货员问题,该问题的解空间可以组织成一棵树。 树的第i层到第i+1层的边上的标号给出xi的值（城市标号）。 从树的根结点到任一叶结点的路径定义了图G的一条周游路线。 如右图为当n=4时这种树结构的示例。,25,2.回溯法的基本思想 例2： 旅行售货员问题,从根结点A到叶结点L的路径上边的标号组成了一条周游路线1,2,3,4,1。 图G

11、的每一条周游路线都恰好对应于解空间树中一条从根到叶的路径。 因此，该解空间树中叶子个数为(n-1)!。（即元素2,3,4的全排列个数）,26,2.回溯法的基本思想 例2： 旅行售货员问题,对于图G，用回溯法找最小费用周游路线时，从A出发，搜索至B,C,F,L。在叶子L处记录找到的周游路线1,2,3,4,1,该周游路线费用为59。 从L处返回最近活结点F，F已无可扩展结点，因此回到C。从C可移至G后又到达M，得到周游路线1,2,4,3,1,费用66，这个费用不比已有路线1,2,3,4,1的费用小，因此舍弃该结点。,27,2.回溯法的基本思想 例2： 旅行售货员问题,算法又依次返回结点G,C,B。

12、从结点B又可以继续搜索D,H,N. 在N处，相应的周游路线1,3,2,4,1的费用为25。是迄今为止找到的最好的一条周游路线。 依次继续搜索遍整个解空间，可找到两条最小费用周游路线： 1 3 2 4 1和1 4 2 3 1,28,2.回溯法的基本思想,在用回溯法搜索解空间树时，通常采用两种策略来避免无效搜索，提高回溯法的搜索效率。 a.用约束函数在扩展结点处剪去不满足约束的子树； b.用限界函数剪去得不到最优解的子树。 这两类函数统称为剪枝函数。,29,2.回溯法的基本思想,如在解0-1背包问题（在有限容量内得到最多价值）的回溯法中，用剪枝函数减去导致不可行解（超出容量限制）的子树。 又如，在

13、旅行售货员问题的回溯法中，如果从根结点到当前扩展结点处的部分周游路线的费用已超过当前找到的最少的周游路线费用，则可断定该结点为根的子树中不含最优解，即可减去该子树。,约束函数,限界函数,30,2.回溯法的基本思想,运用回溯法解题通常包含以下三个步骤： (1)定义问题的解空间； (2)确定易于搜索的解空间结构； (3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。,31,3、递归回溯,由于回溯法对解空间作深度优先搜索，因此，在一般情况下用递归方法实现回溯法（回溯法也是设计递归过程的一种重要方法）。 void backtrack (int t) /形参t表示递归深度，n是问题规模

14、if (tn) output(x); /搜索到一个叶结点elsefor (int i=f(n,t);i0) if (f(n,t)=g(n,t) for (int i=f(n,t);i=g(n,t);i+) xt=h(i); /取第i个可选值if (constraint(t) /返回t-1层,该算法中h,f,g,constraint,bound等的含义同递归回溯中的含义。,34,4、迭代回溯,该算法描述中，函数Solution(t)用来判断在当前扩展结点处是否已经得到了一个可行解，若返回T,表示在当前扩展结点处x1:t是问题的一个可行解。此时，由output对可行解x进行记录或输出。 否则， x1:t还只是问题的一个部分解，还需向纵深方向继续搜索。,35,小结,用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。 在任何时刻，算法只保存从根结点到当前扩展结点的路径，由x1:t保存该路径上边的取值 。,