《8算法第八章回溯法概要》由会员分享，可在线阅读，更多相关《8算法第八章回溯法概要（41页珍藏版）》请在金锄头文库上搜索。
1、第八章 回溯法,目录,8.1 一般方法 8.2 8-皇后问题 8.3 子集和数问题(略) 8.4 图的着色(略) 8.5 哈密顿环(略) 8.6 背包问题(略),8.1 一般方法,回溯的一般方法 解向量构造方式 回溯求解的基本概念 8-皇后问题,回溯的一般方法,回溯法是一种搜索算法。 回溯法是以深度优先的方式系统地搜索问题的解, 它适用于解一些组合数较大的问题。 回溯法要求问题的解可以用一个n元组(x1, , xn)来表示，其中的xi取自于某个有穷集Si。 通常，需要求取一个使得某一规范函数P(x1, , xn)取极值或满足其条件的向量。有时还要找出满足规范函数P的所有向量。,界限函数,解向量
2、构造方式,硬性处理： |Si|=mi,向量个数m=m1m2mn,对这m个n元组逐一检测是否满足P，从而找出问题的所有最优解。 回溯法： 不断地用修改过的限界函数Pi(x1,xi)去测试正在构造中的n元组的部分向量(x1,xi), 看是否可能导致最优解, 如果不能, 就将可能要测试的mi+1 mn个向量略去。,测试次数比硬性处理的m次要少得多,回溯求解的基本概念,显式约束：限定每个x只从一个给定的集合上取值。 隐式约束：描述了xi必须彼此相关的情况。 解空间：满足显式约束条件的所有元组。 可行解：解空间中满足隐式约束条件的决策序列。 解空间树：基于解空间画成的树形状。,xi=0 , Si=所有非
3、负实数 xi=0或1，Si=0,1,可能与问题实例有关，也可能无关。,与问题实例有关。,例8.1 8皇后问题,在一个8*8棋盘上放8个皇后, 使每两个皇后之间都不能互相“攻击”, 即使得每两个皇后都不能在同一行、同一列及同一条斜角线上。 将定皇后i放在行i上，8皇后问题可以表示为8-元组(x1,x8)，其中xi是放置皇后i所在的列号。 显式约束条件: Si=1, 2, 3, 4, 5, 6, 7, 8, 1i8 隐式约束条件: 没有两个xi可以相同, 且没有两个皇后可以在同一条斜角线上。,解空间：88,解空间：8！,(4,6,8,2,7,1,3,5),例8.2 子集和数问题,已知n+1个正数:
4、 wi(1in)和M, 要求找出wi的和数是M的所有子集。 用wi的下标来表示解向量。一般情况下，所有的解都是k元组(x1,xk)，1kn，不同的解k值不同。 显式约束条件: xi j | j是wj的下标值, 1jn 。 隐式约束条件: 要求没有两个xi是相同的, 且相应的wj的和等于M。 为避免产生重复情况(如(1,2,4)和(1,4,2), 附加一个隐式约束条件: xixi+1, 1in。,(1, 2, 4),(3, 4),例: n=4 , (w1, w2, w3, w4 )= (11,13,24,7), M=31。满足要求的子集是(11,13,7)和(24,7)。,另一种表示方法：采用n
5、元组表达(x1,x2,xn), xi=0/1。 解向量(1, 2, 4)和(3, 4)可表示为(1,1,0,1)和(0,0,1,1)。,例8.3 n-皇后问题的解空间树,在一个n*n的棋盘上放n个皇后, 使每两个皇后之间都不能互相“攻击”。 n=4时，叶节点个数=4！=24，解空间是从根节点到叶节点的所有路径。,返回,例8.4 子集和数问题的解空间树,解空间是树中根节点到任何节点的所有路径。 根结点到自身的空路径对应一个空向量( )。,树中红色的路径分别对应向量:,( ),(1),(1, 2),(1, 2, 3),(1, 2, 3, 4),返回,子集和数问题的另一种列式表示：每一个解的子集由一
6、个大小固定的n-元组(x1, , xn)所表示, xi0,1,1in ; 如果选择wi , 则xi=1 ; 否则xi=0。 n=4时,叶节点2n=24=16。,从根结点到叶结点的一条路径确定解空间中的一个元组,树中红色路径表示元组(1,1,0,1)。,返回,回溯法的一些特点,回溯法在求问题的所有解时, 要遍历树才能结束。 回溯法在求问题的任一解时, 只要搜索到问题的一个解就可以结束。 回溯法按深度优先策略, 从根结点出发搜索解空间树。 回溯法搜索至解空间树的任一结点时, 先判断该结点是否一定不包含问题的解。如果一定不包含, 则跳过以该结点为根的子树, 逐层向其祖先结点回溯。否则就进入该子树,
7、继续按深度优先的策略进行搜索。,解空间树中的一些概念,问题状态(problem state): 树中的每一个结点确定所求解问题的一个问题状态。 状态空间(state space): 由根结点到其他结点的所有路径确定了这个问题的状态空间。 解状态(solution states): 是这样一些问题状态S, 对于这些问题状态, 由根到S的那条路径确定了这个解空间中的一个元组。 答案状态(answer states): 是这样的一些解状态S, 对于这些解状态而言, 由根到S的这条路径确定了这问题的一个解。,静态树(static trees): 树结构与所要解决问题的实例无关。 动态树(dynamic
8、 trees): 树结构是与实例相关的, 且树结构是动态确定的。 活结点: 自己已经生成而其所有的儿子结点还没有全部生成的结点。 E-结点(正在扩展的结点): 当前正在生成其儿子结点的活结点。 死结点: 不再进一步扩展或者其儿子结点已全部生成的结点。,问题状态的生成,第一种状态生成方法: 当前的E-结点R 一旦生成一个新的儿子结点C, 这个C结点就变成一个新的E-结点, 当检测完了子树C后, R结点就再次成为E-结点, 生成下一个儿子结点。(该方法也称为深度优先结点生成法)。 第二种状态生成方法: 一个E-结点一直保持到变成死结点为止。它又分为两种方法: 宽度优先生成(队列方法)和D-检索(栈
9、方法)。 第一种状态生成方法对应回溯法。 第二种状态生成方法对应分枝-限界法。,例8.5 4-皇后问题,开始把根结点作为唯一的活结点, 根结点就成为E-结点而且路径为( ); 接着生成儿子结点, 假定按自然数递增的次序来生成儿子结点, 那么结点2被生成, 这条路径为(1), 即把皇后1放在第1列上。,1,kill,结点2变成E-结点, 它再生成结点3, 路径变为(1, 2), 即皇后1在第1列上, 皇后2在第2列上, 所以结点3被杀死, 此时应回溯。,回溯到结点2生成结点8, 路径变为(1, 3), 则结点8成为E-结点, 它生成结点9和结点11都会被杀死(即它的儿子表示不可能导致答案的棋盘格
10、局), 所以结点8也被杀死, 应回溯。,kill,kill,回溯到结点2生成结点13, 路径变为(1, 4), 结点13成为E-结点, 由于它的儿子表示的是一些不可能导致答案结点的棋盘格局, 因此结点13也被杀死, 应回溯。,kill,kill,结点2的所有儿子表示的都是不可能导致答案的棋盘格局, 因此结点2也被杀死; 再回溯到结点1生成结点18, 路径变为(2)。,kill,kill,结点18的儿子结点19、结点24被杀死, 应回溯。,结点18生成结点29, 结点29成为E-结点, 路径变为(2,4)。,结点29生成结点30, 路径变为(2,4,1)。,结点30生成结点31, 路径变为(2,
11、4,1,3), 找到一个4-皇后问题的可行解。,可行解,回溯算法的三个步骤,针对所给问题定义出问题的解空间。 确定易于搜索的解空间树结构。 以深度优先方式搜索解空间树, 并在搜索过程中使用限界函数避免无效搜索。 首先根结点成为一个活结点, 同时也是当前的扩展结点。沿当前扩展结点向纵深方向移至一个新结点, 该新结点成为一个新的活结点, 并成为当前扩展结点。 如果当前扩展结点不能再向纵深方向移动, 则其成为死结点。此时回溯至最近的一个活结点, 并使该活结点成为当前的扩展结点。,回溯法递归地在解空间中搜索, 直至找到所要求的解或解空间中已没有活结点时为止。,T(X1),回溯算法的形式化描述,假设要找
12、出所有的答案结点; 设(x1,x2,xi-1)是状态空间树中由根到一个结点的路径; T(x1,xi-1)是下述所有结点xi的集合，它使得对于每一个xi，(x1,x2,xi)是一条由根到结点xi的路径; 假定存在一些限界函数Bi,如果路径(x1,x2,xi)不可能延伸到一个答案结点,则Bi(x1,x2,xi)取假值,否则取真值; 解向量X(1:n)中的第i个分量就是那些选自集合T(x1,xi-1)且使Bi为真的xi 。,X1,算法8.1 回溯的一般方法,procedure BACKTRACK(n) int k, n local X(1: n) k 1 while (k0) do if (还剩有没
13、检验的X(k)使得X(k)T(X(1)X(k-1) and B(X(1)X(k)=TRUE) then if (X(1) X(k)是一条抵达答案结点的路径) then print ( X(1)X(k) endif k k+1 else k k-1 endif repeat end BACKTRACK,/打印数组X,/考虑下一个集合,/回溯的先前的集合,限界函数B(X(1)X(k)判断哪些X(k)满足隐式约束条件。,15,1,9,8,procedure BACKTRACK(n) int k, n local X(1: n) k 1 while (k0) do if (还剩有没检验的X(k) 使得
14、X(k)T(X(1)X(k-1) and B(X(1)X(k)=TRUE) then if (X(1) X(k)是一条 抵达答案结点的路径) then print ( X(1)X(k) endif k k+1 else k k-1 endif repeat end BACKTRACK,k=2,k=3,k=4,只需要一个解，则怎样修改算法。,B值为假,B值为真,k=1,算法8.2 递归回溯算法,procedure RBACKTRACK(k) global X(1:n); int k, n; for ( 满足下式的每个X(k), X(k) T(X(1)X(k-1) and B(X(1),X(k)=
15、true) do if (X(1),X(k)是一条抵达答案结点的路径 then print (X(1)X(k) endif call RBACKTRACK(k+1) repeat end RBACKTRACK,进入算法时, 解向量X中的前k-1个分量X(1) X(k-1)已经被赋值,决定回溯法效率的因素,回溯法的效率主要取决于四种因素: 生成下一个X(k)的时间 满足显式约束条件的X(k)的数目 限界函数Bi的计算时间 对于所有的i，满足Bi的X(k)的数目 Bi能够大大减少生成的节点数，但在计算时间和减少程度上要进行折中。,生成节点的时间,子节点的数量,检验节点的时间,通过检验的节点数量,一
16、旦选定了一种状态空间树结构, 前三种因素对于所要解决的实例没有多大的关系, 只有第四种因素,对于问题的不同实例, 生成的结点数是不相同的。,如果解空间的结点数是2n或n!，易知，回溯算法最坏情况下的时间复杂度为O(p(n)2n)或O(q(n)n!)，其中p(n)和q(n)为n的多项式 由于回溯法对同一问题不同实例的巨大差异，在n很大时，对某些实例是十分有效的。因此，在采用回溯法计算某个实例之前，应估算其工作能效 用回溯算法处理一棵树所要生成的节点数，可以用蒙特卡罗方法估算出来,回溯法的效率估计,蒙特卡罗方法的一般思想,在状态空间中生成一条随机路径。 设x是这条路径上的位于第i级的一个节点。 设限界函数确定x的可用儿子节点的数目为mi。 从这mi个儿子节点
