计算机算法设计与分析-第八章.ppt

计算机算法设计与分析Chapter 8. 回溯（Backtracking）与分枝限界（Branch & Bound）技术v 8.1 8.1 回溯和分枝限界的基本思想回溯和分枝限界的基本思想v 8.2 0-18.2 0-1背包（背包（0-1 Knapsack0-1 Knapsack）问题的回溯算法）问题的回溯算法v 8 8.3 .3 无向图的团集（无向图的团集（CliqueClique）问题）问题v 8 8. .4 4 旅行商（旅行商（Traveling SalesmanTraveling Salesman）问题的回溯算法）问题的回溯算法v 8 8. .5 5 分枝限界算法思路的特征分枝限界算法思路的特征回溯与分枝限界技术都是基于穷举方法，即按照一定规律，把问题所有可能的解组织成某种树结构，形成可能解空间或状态空间（state space）树然后按照具体问题的约束条件，通过遍历可能解空间树的方法，搜索满足问题条件的解（有时称为最优解）搜索过程中常常需要“剪枝”，从而加速求解过程穷举剪枝过程，大致可分为四个环节： 确定问题的可能解空间，相当于找出进行穷举的搜索范围； 以一种便于搜索的方式组织所有的可能解，一般是生成可能解空间树； 以某种方式搜索可能解空间树，有两种基本方式，即： 深度优先搜索（DFS）方式，即回溯技术。

广度优先搜索（BFS）方式，即分枝限界技术 在搜索过程中利用判定函数（也称代价函数或限界函数），通过“剪枝”来加速搜索过程8.1 回溯和分枝限界的基本思想8.1.1 八皇后（8-Queens）问题 在在 国国 际际 象象 棋棋 （ chess） 的的88=64格格棋棋盘盘上上放放置置8个个皇皇后后，使使任任意意两两个个皇皇后后不不在在同同一一行行、同同一一列列和和同同一一斜斜线线上上（即即不不能能互互相相攻攻杀杀）Fig.8.1给给出出了了八八皇后问题的一个满足条件的解皇后问题的一个满足条件的解可以把八皇后问题扩展为n皇后问题，表现为另一种形式，即求n元向量(x1,x2,xn),xi 1n, i 1n,每一行可以而且必须放置一个皇后，且第i个皇后放在第i行的xi位置上x1x2xn)应是的一个(1,2,n)排列，即不可有两个皇后在同一列空间大小nn把满足上述条件的向量(x1x2xn)称为一个可能解，因此n皇后问题的可能解集合恰为(1,2,n)的全部可能排列的个数，共有n!个设n=4，即四皇后问题，可以构造一个状态空间树（state space tree），如Fig.8.2所示结点的编号是按DFS（深度优先搜索）方式排列的，也是按回溯方式遍历搜索的次序。

结点8代表的部分解(1,3)满足问题的约束条件，即：xixj(i-j), i2n, j1i-1可以向结点9继续搜索由结点36代表的部分解（3,1,2）可以推导出x3=x2+1，已不满足约束条件，算法进行回溯，返回到结点35后，再向结点38继续搜索4-Queens问题的回溯算法的搜索过程如Fig.8.3所示由于在所有结点上表示的解或部分解已满足每个皇后占据不同的行与列，因此只需检查新放置的皇后的位置xi与前面已放置的i-1个皇后不在同一斜线上，就满足条件了如果i=4，就找到了所求的解判别条件为：xixj(i-j), i2n, j1i-1 (a) 从结点1到结点2，满足条件，放置皇后x1=1，继续向前；(b) 结点3不满足条件，回溯到结点2；再向下搜索到结点8，满足条件，放置皇后x2=3，继续向前；(c) 结点9不满足条件，回溯搜索到结点11，仍不满足条件；这时经结点8，回溯到结点2；(d) 向下搜索到结点13，满足条件，放置第二个皇后x2=4；继续向下搜索到结点14，满足条件，放置第三个皇后x3=2；(e) 向前搜索至结点15，不满足条件（只测试x4=3的情形），回溯搜索至结点16，仍不满足条件；(f) 回溯至结点1后，向下搜索至结点18，令x1=2；(g) 结点19不满足条件；回溯至结点24后，也不满足条件；回溯至结点29之后满足条件，令x2=4；(h) 结点30满足条件，令x3=1；向前搜索至结点31，满足条件，令x4=3，此时i=4，找到有效解。

8.1.2 子集合（subset sum）问题 子集合问题是0-1Knapsack问题的简化形式已知：由n个正整数s1,s2,sn组成的集合和正整数C求：是否存在这个整数集合的子集，其元素和恰为C子集合（subset sum）问题有两种不同形式：(1)subset sum问题的判定问题（Decision Problem）；(2)优化问题（Optimization Problem），即求其元素和不超过C且和数最大的子集 Subset sum问题的所有可能解可以用两种形式表示，Fig.8.4为第一型解空间树，Fig.8.5为第二型解空间树（solution space tree）设n=4在这个解空间树中，16个叶结点表示16个可能解，每个内部结点表示一个部分解例如，结点14表示向量（x1x2x3）取值为(0,1,1)，即子集中包含s2、s3，而s4是否包含在子集中尚未确定 这个空间树把问题的16个可能解，即集合S=s1,s2,s3,s4的所有可能子集，按4个元素出现在子集中的顺序排列整理而成，这个树的每一个结点表示一个可能解例如，结点1为空集，结点4为s3，结点14为s1,s3,s4，因此称之为第二型（可能）解空间树，结点是按BFS（广度优先搜索）次序排列的。

BFS搜索过程可以显示出分枝限界方法与回溯方法的不同，算法自始至终管理着一个活动结点表ANL（active node list）搜索过程如下：(S=45,27,9,16,C=25) (0) 初始：ANL=1，结点1为一空集，子集和为0C，被删除；(2) ANL=3,4,5，包含3个活动结点，处理结点3，其和为27C，被删除；(3) ANL=4,5，包含2个活动结点，处理结点4，其和为9C，ANL扩展为4的子结点11；(4) ANL=5,11，包含2个活动结点，处理结点5，其和为16C，因为结点5无子结点，又不是解，所以被删除；(5) ABL=11，包含1个活动结点，处理结点11，其和为25=C，即为所求如果令C=26，活动结点表最终为空，说明此实例无解Subset sum问题的优化问题是求S的一个子集，其和不大于C，而且在所有有效解中和是最大的8.1.3 回溯与分枝限界算法的基本思路 1、可能解集合由于算法是基于穷举方法的，确定这个解集合时必须注意： 它包括所有的可能解，不能有遗漏； 可以根据实际问题条件，限制其规模第一个条件是显然的，以8-Queens问题为例说明第二个条件在一个88的棋盘上放置8个皇后，可以有几种不同的方法定义其全部可能解集合： 1)每一个皇后可以放在棋盘的任意位置(i,j)，i，j18,其可能解的总数应为816（n-Queens问题为(n2)n=n2n）； 2)每一个皇后可以放在棋盘的任意位置，但不可重复（即二子不可放在同一位置），其可能解的总数应为：64!/56!=646357； 3)每一行只可放一个皇后，即每个皇后各占一行，在该行可放任意位置，其可能解的总数应为88=16777216； 4)每一行每一列只可放一个皇后，即每个皇后各占一行，且不可占用已放置的皇后所占用的列，其可能解的总数应为8!=40320。

在Fig8.2中，4-Queens问题的解空间树实际上是按照第4种方式定义的，这种方式可以大大缩小可能解集合的规模不过，集合规模最小的方案不一定是最好的例如，在4-Queens问题中采用第三种方案，即在(x1x2x3x4)中，每一个可以分别取1、2、3、4，这时其可能解总数为256，但是算法的程序实现会更简单 2、状态空间树（state space tree）回溯与分枝限界方法的共同思想之一是把问题的部分解、可能解、问题解（也称答案或最优解）之间的关系用树或图的结构连接起来，把树（或图）的每个结点称为一个问题状态（problem state）从一个问题状态转向另一个相邻状态只需很少的计算，当该状态已包含了问题的一个可能解的全部数值时，该状态称为一个解状态（solution state）在Fig8.2和Fig8.4中的树的叶结点和Fig8.5中的树的所有结点都是一个解状态而满足问题条件的解状态即是问题的一个答案（或最优解），称为答案状态（answer state）在Fig8.2和Fig8.4中的树的叶结点和Fig8.5中的树的所有结点都是一个解状态而满足问题条件的解状态即是问题的一个答案（或最优解），称为答案状态（answer state）。

在可能解空间树上，从根结点到任何一个问题状态结点的路径，称为一个状态空间（state space），整个解空间树称为状态空间树（state space tree）在回溯算法中，并不需要真正创建一个状态空间树搜索过程从根结点开始，在算法执行的任一时刻，都只是考察和处理状态空间树的某些局部结点，这些结点根据其状态被称为A-结点、E-结点和D-结点 A-结点：称为活动结点（Active node），是算法正在或准备考察的结点E-结点：称为扩展结点（Expanded node），是正在把自己的子结点加入到活动结点表中的活动结点第一个活动结点是根结点，以后的活动结点都是由活动结点及其子结点“扩展”而来D-结点：称为死结点（Dead node），不能继续扩展或者其所有子结点都已扩展为活动结点的结点在回溯算法中，搜索策略是每当出现D-结点就进行回溯，通过继续扩展父结点产生新的A-结点，直至找到最优解或答案搜索过程涉及的结点只是整个状态空间树的一个子树 4-Queens问题的状态空间树（Fig.8.2）的搜索过程可以用Fig.8.6的子树来表示其搜索过程为：1把根结点选为把根结点选为A-结点结点A；2if P(A) return A；3if B(A) goto 5；4选选A的父结点为的父结点为A-结点结点（回溯），（回溯），goto 3；5if A可扩展（有未选过的子可扩展（有未选过的子结点），选为结点），选为A-结点，结点，goto 2；6if A不是根，不是根，goto 4；7cout“搜索失败搜索失败”。

20对应于Fig.8.6的实际搜索过程可用下面的结点序列表示：(1)A(1)E(2)A(2)E(3)A(3)D(2)E(8)A(8)E(9)A(9)D(8)E(11)A(11)D(8)D(2)E(13)A(13)E(14)A(14)D(13)E(16)A(16)D(13)D(2)D(1)E(18)A(18)E(19)A(19)D(18)E(24)A(24)D(18)E(29)A(29)E(30)A(30)E(31)Areturn.分枝限界算法搜索状态空间树时，同样是从根结点出发，按照BFS顺序检验各个问题状态结点其搜索过程描述如下：1把根结点加入到活动结点表ANL中；2从ANL中取首元为当前A-结点，if ANL= goto 7；3if P(A) return A；4if B(A) goto 6；5从ANL中删去A，goto 2；6从ANL中删去A，把A的子结点从左至右顺序加入ANL，goto 2；7cout“搜索失败”对于Subset sum（n=4）问题的一个实例：S=47,71,19,25，C=44用Fig.8.5作为状态空间树，用分枝限界策略进行求解的过程如Fig.8.7所示，其中活动结点表的变化过程为：3、搜索策略与判定函数问题的状态空间树是虚拟的，并不需要在算法运行时构造一棵真正的树。

按照深度优先搜索(DFS)顺序遍历归结为回溯技术，按广度优先搜索(BFS)顺序遍历归结为分枝限界技术 1，初始，初始，P(1)=false，B(1)=true；2,3,4,5，P(2)=false，B(2)=false；3,4,5，P(3)=false，B(3)=false；4,5，P(4。