第五章----回溯法--基本概念--n后问题.ppt

1、第五章 回溯法,1,第五章 回溯法（Backtrack）,回溯法有“通用的解题法”之称。用它可以求出问题的所有解或任一解。 回溯法是一个既带有系统性又带有跳跃性的搜索法。它在包含问题所有解的解空间树中，按照深度优先的策略，从根出发进行搜索。搜索每到达解空间树的一个结点，总是先判断以该结点为根的子树是否肯定不包含问题的解。如果肯定不包含，则跳过对该子树的系统搜索，一层一层地向它的祖先回溯，直到遇上一个还有未被搜索过的儿子的结点，才转向该结点的一个未曾搜索过的儿子结点，继续搜索；否则，进入该子树，继续按深优先的策略进行搜索。,第五章 回溯法,2,一、回溯法的算法框架,1. 问题的解空间 应用回溯法

2、解问题时，首先应明确定义问题的解空间。问题的解空间应至少包含问题的一个（最优）解。 例： 对于有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),第五章 回溯法,3,通常把解空间组织成解空间树或图。例如：对于n=3时的0-1背包问题，其解空间用一棵完全二叉树表示，如下图所示。,第五章 回溯法,4,例： n=3时的0-1背包问题，W=16，15，15，p=45，25，25

3、，C=30。在其解空间树上搜索最优解的过程如下图所示。,图5- 在0-1背包问题的解空间树上搜索最优解,1,A,B,C,0,D,E,F,G,H,I,J,K,L,M,N,O,1,1,1,1,1,1,0,0,0,0,0,0,A,B,D,E,J,K,45,E,B,C,F,L,50,M,25,F,G,N,25,O,0,G,C,A,第五章 回溯法,5,2. 回溯法的基本思想,确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为

4、当前的扩展结点。如果当前的扩展结点处不能再向纵深方向移动，则当前的扩展结点就成为死结点。此时应回溯到最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已无活结点时为止。,第五章 回溯法,6,例：旅行售货员问题：某售货员要到若干城市推销商 品，已知各城市间的路程（或旅费）。他要选一条从驻地出发，经过每个城市一遍，最后回到驻地的路线，使总的路程（总的旅费）最小。,图5-3 四个顶点的带权图,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,1,2,3,4,3,4,2,4,2,3,4,3,4,2,3,2,图

5、5-4 旅行售货员问题的可行解空间树,A,B,C,F,L,59,F,G,M,60+659,G,C,D,H,N,H,I,25,2625,D,E,J,P,19+6=25,J,K,Q,29+3025,K,E,B,A,第五章 回溯法,7,综上所述，回溯法解题包含以下步骤: (1) 针对所给的问题，定义问题的解空间； (2) 确定易于搜索的解空间结构解空间树； (3) 以深度优先的方式搜索解空间树，并在搜索过程中用剪枝函数（约束函数或限界函数）避免无效搜索。,第五章 回溯法,8,3. 递归回溯 由于回溯法是对解空间的深度优先搜索，因此，一般可用递归函数实现回溯法如下： void Backtack(int

6、 t) if ( t n ) Output(x); /t表示递归深度 else for (int i = f(n,t); i=g(n,t); i+) / f(n,t),g(n,t)：分别表示当前可扩展结点未搜索过的 子树的起始编号和终止编号. xt =h(i); /h(i )：在当前扩展结点处xt的第i个可取值 if (Constrain(t) ,第五章 回溯法,9,用回溯法解题的一个显著特征： 问题的解空间是在搜索过程中动态生成的。在任何时刻，算法只保存从根结点到当前扩展结点的路径。若解空间树中从根到叶的最长路径长度为h(n)，则回溯法所需的计算空间通常为O(h(n)。显式存储整个解空间则需

7、要O(2 h(n)。,第五章 回溯法,10,4.子集树与排列树,图5-1和图5-4中的两棵解空间树是回溯法解题时常遇到的两类典型的解空间树。 当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树。 例如，n个物品的0-1背包问题相应的解空间树称为子集树。子集树通常有2n个叶结点，其结点总个数为2n+1-1。 遍历子集树的任何算法均需(2n)的计算时间。,第五章 回溯法,11,用回溯法搜索子集树的一般算法可描述如下： void Backtrack(int t) if (t n) Output(x); else for (int i=0; i=1; i+) xt=i

8、; if (Constraint(t) ,第五章 回溯法,12,当所给的问题确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。 例如，旅行售货员问题相应的解空间树称为排列树。排列树通常有n！个叶结点。遍历子集树的任何算法均需(n!)的计算时间。,第五章 回溯法,13,用回溯法搜索排列树的一般算法可描述如下： void Backtrack(int t) if (t n) Output(x); else for (int i=t; i=n; i+) Swap(xt,xi); if (Constraint(t) 注意：在调用Backtrack(1)执行此回溯算法之前，先将变量数组x初始化为

9、单位排列(1,2,n)。,第五章 回溯法,14,二、n后问题 (p154),1. 问题描述 n后问题要求在一个n*n格的棋盘上放置n个皇后，使得她们彼此不受攻击。一个皇后可以攻击与之在同一行或同一斜线上的其他任何棋子。因此，n后问题等价于： 任何两个皇后不能在同行、同列、同一斜线上。 例子：四皇后问题: 给4*4棋盘的行和列分别从左到右和从上到下编号为1，2，3，4，同时也给4个皇后分别编号为1，2，3，4。由于要求不同的皇后不能放在同一行，不失一般性，可设皇后i只放在第i行。,第五章 回溯法,15,1,2,87,172,257,3,24,66,45,72,73,74,75,76,1,2,3,

10、4,1,2,3,4,1,1,1,2,3,4,151,152,156,1,2,3,4,四后问题的解空间树,1,2,3,4,2,3,24,45,66,67,67,72,73,74,75,76,72,77,82,77,82,66,2,87,88,109,130,88,109,130,151,152,153,154,155,153,154,155,2,3,4,46,51,56,61,46,51,56,61,45,有2个可行解： （2，4，1，3）、（3，1，4，2）,1,第五章 回溯法,16,2. 算法设计,对n后问题，可用n元组x1:n表示它的解。其中，xi表示皇后i放在棋盘的第i行的第xi列。 若

11、2个皇后放置的位置分别是(i,j)和(k,l)，则 约束条件为： xixk (不在同一列) i+jk+l, i-kj-l (不在同一斜线) 即|i- k|j- l| 用回溯法解n后问题时，可以用一棵完全n叉树来表示其解空间。用可行性约束函数Place可剪去不满足行、列和斜线约束的子树。,第五章 回溯法,17,n后问题的回溯算法 void Backtrack(int t) if (t n) sum+; for (int i=1;i=n;i+) cout xi ; cout endl; else for (int i=1;i=n;i+) xt=i; if (Place(t) ) Backtrack(t+1) ; ,bool Queen:Place(i