《算法导论课件第13讲回溯法》由会员分享，可在线阅读，更多相关《算法导论课件第13讲回溯法（41页珍藏版）》请在金锄头文库上搜索。
1、1,Back-Tracking Algorithms 回溯法,第五章,2,什么是回溯法,回溯法有“通用的解题法”之称。 应用回溯法解问题时，首先应该明确问题的解空间。 一个复杂问题的解决往往由多部分构成，即，一个大的解决方案可以看作是由若干个小的决策组成。很多时候它们构成一个决策序列。 解决一个问题的所有可能的决策序列构成该问题的解空间。解空间中满足约束条件的决策序列称为可行解。一般说来，解任何问题都有一个目标，在约束条件下使目标达到最优的可行解称为该问题的最优解。,3,Back-Tracking Paradigm,A design technique, like divide-and-con
2、quer. Useful for optimization problems and finding feasible solutions. Solution to a problem is defined as an n-tuple: (x1, x2, , xn), where xi is taken from a finite set Si . Generally, we need to: finding a vector which maximize (or minimize) a specific objective function P(x1, x2, , xn). finding
3、a (or all) vector(s) that satisfy a specific criterion function P(x1, x2, , xn).,4,一般方法,什么是回溯法： 问题的解可以用一个n元组(x1,xn)来表示，其中的xi取自于某个有穷集Si，并且这些解必须使得某一规范函数P(x1,xn)取极值。 假设集合Si的大小是mi，于是就有m= m1 m2 mn个n-元组可能满足函数P。 所谓硬性处理就是构造出这m个n-元组并逐一测试它们是否满足函数P，从而找出该问题的所有最优解。,5,回溯法的基本思想：不断地用修改过的规范函数Pi(x1,xi)去测试正在构造的n元组的部分向
4、量(x1,xi) ，看是否可能导致最优解。 如果判定(x1,xi)不能导致最优解，那么就将可能要测试的mi+1mn个向量略去。 因此回溯法的测试次数比硬性处理作的测试次数要少得多。,一般方法,6,Back-TrackingGeneral Method,Constraints Explicit Constraints constrain values of each component xi; All tuples that satisfy explicit constraints make up a possible solution space. Implicit Constraints:
5、inter-components constraints; Implicit constraints identify those satisfying the criterion function in the solution space.,7,回溯法的解需要满足一组综合的约束条件，通常分为：显式约束和隐式约束 显式约束条件限定每个x只从一个给定的集合上取值，例如： xi=0 即si=所有非负实数 xi=0或xi=1 即 si=0,1 l=xi=u 即si=a:l=a=u 满足显式约束的所有元组确定的一个可能的解空间。 隐式约束描述了xi必须彼此相关的情况。,一般方法,8,例：8皇后问题
6、在一个8*8棋盘上放置8个皇后，且使得每两个之间都不能互相“攻击”，也就是使得每两个都不能在同一行、同一列及同一条斜角线上。 8皇后问题可以表示为8-元组(x1,x8) ，其中xi是放置皇后i所在的列号。 显式约束条件是si=1,2,3,4,5,6,7,8, 1i8 隐式约束条件是，没有两个xi可以相同且没有两个皇后可以在同一条斜角线上。,一般方法,9,8-Queen problem,Place 8 queens on a 88 chessboard, yielding that any two of them do not conflict, i.e. any two of them do
7、not reside in the same row, column or diagonal.,10,8-Queen problem,Label the rows and columns by 1 to 8, and the queens too. Assume that queen i resides in row i. Solutions can be defined as a 8-tuple (x1, x2, , x8), where xi is the column number of queen i. The solution above is (4，6，8，2，7，1，3，5).,
8、11,8-Queen problem,Explicit Constraints: xi Si，Si=1,2,3,4,5,6,7,8, 1 i 8. The solution space consists of 88 8-tuples. Implicit Constraints: any two of them do not reside in the same row, column( any two of xi differ ) or diagonal.,12,什么是回溯法,回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。 回溯法在用来求问题的任一解时，只要搜
9、索到问题的一个解就可以结束。 回溯法是以深度优先的方式系统地搜索问题的解的算法，它适用于解一些组合数较大的问题。,13,状态空间树,树的边由xi的可能值所标记。 由1级到2级结点的边给出x1的值。 最左子树包含着x1=1的所有解。 由i级到i+1级的边用xi的值标记。 解空间则由从根结点到叶结点的所有路径所定义。,n=3时的0-1背包问题用完全二叉树表示的解空间,14,The solution space consists of all the paths from the root to each leaf, e.g.（4，2，3，1）。,State Space Tree,15,Proble
10、m State Each node in the tree identifies a problem state when solving the problem.,State Space Tree,16,State Space All the paths from the root to each node,State Space Tree,17,State Space Tree The above tree of the solution space,State Space Tree,18,Solution States Those problem states to which the
11、path from the root identifies a vector in the solution space (Satisfying explicit constraints).,only leaves in this problem.,State Space Tree,19,Answer States Those solution states to which the path from the root identifies an answer (Satisfying implicit constraints).,State Space Tree,20,state space
12、 tree,problem state,state space,solution states,answer states,State Space Tree,21,状态空间树,几个概念： 问题状态(problem state)：树中的每一个结点确定所求解问题的一个问题状态。 状态空间(state space)：由根结点到其他结点的所有路径则确定了这个问题的状态空间。 解状态(solution states)：是这样一些问题状态S，对于这些问题状态，由根到S的那条路径确定了这解空间中的一个元组。有的问题所有的结点都是解状态，有的只有叶结点才是解状态。 答案状态(answer states)：是这
13、样的一些解状态S，对于这些解状态而言，由根到S的这条路径确定了这问题的一个解。,22,静态树(static trees)：树结构与所要解决的问题的实例无关。 动态树(dynamic trees)：根据不同的实例而使用不同的树结构。 活结点：自己已经生成而其所有的儿子结点还没有全部生成的结点。 E-结点（正在扩展的结点）：当前正在生成其儿子结点的活结点。 死结点：不再进一步扩展或者其儿子结点已全部生成的生成结点。,状态空间树,23,回溯法的基本思想,常用剪枝函数： 用约束函数在扩展结点处剪去不满足约束的子树； 用限界函数剪去得不到最优解的子树。,用回溯法解题的一个显著特征是在搜索过程中动态产生问
14、题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为O(h(n)。而显式地存储整个解空间则需要O(2h(n)或O(h(n)!)内存空间。,(1)针对所给问题，定义问题的解空间； (2)确定易于搜索的解空间结构； (3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。,24,递归回溯,回溯法对解空间作深度优先搜索，因此，在一般情况下用递归方法实现回溯法。 void backtrack (int t) if (tn) output(x); else for (int i=f(n,t);
15、i=g(n,t);i+) xt=h(i); if (constraint(t) ,25,迭代回溯,采用树的非递归深度优先遍历算法，可将回溯法表示为一个非递归迭代过程。 void iterativeBacktrack () int t=1; while (t0) if (f(n,t)=g(n,t) for (int i=f(n,t);i=g(n,t);i+) xt=h(i); if (constraint(t) ,26,问题状态的生成,解决问题可采用两种不同的方法： 1、问题状态的深度优先生成(回溯法)：当前的E-结点R 一旦生成一个新的儿子结点C，这个儿子结点就变成一个新的E-结点，当检测完了
16、子树C后，R结点就再次成为E-结点，生成下一个儿子结点。 2、分枝-限界法：一个E-结点一直保持到变成死结点为止。,27,State Space Tree,Identify state space tree,Begin,Generate problem state,Is solution state?,Is answer state?,End,All states?,Yes,No,DFS in back Tracking paradigm,Trying to generate all problem states?,No! using bound functions to kill alive nodes,28,回溯法的算法,算法的三个步骤： 针对所给问题，定义问题的解空间； 应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应至少包含问题的一个（最优）解。 确定易于搜索的解空间结构； 以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效
