1、第五章 回溯法1第五章 回溯法2 1. 1. 问题的解空间问题的解空间 应用回溯法解问题时，首先应明确定义问题的解空应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应至少包含问题的一个（最优）解。间。问题的解空间应至少包含问题的一个（最优）解。 例例： 对于有对于有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
2、), (1,0,1), (1,1,0), (1,1,1)第五章 回溯法3 1ABC0DEFGHIJKLMNO图图5-15-1 0-1背包问题的解空间树背包问题的解空间树 111111000000第五章 回溯法4n=3时的时的0-1背包问题背包问题，W=16，15，15，p=45，25，25，C=30。在其解空间树上搜索最在其解空间树上搜索最优解的过程如下图所示。优解的过程如下图所示。 图图5-5- 在在0-10-1背包问题的解空间树上搜索最优解背包问题的解空间树上搜索最优解1ABC0DEFGHIJKLMNO111111000000ABDEJK45EBCFL50M25FGN25O0GCA第五章
3、回溯法52. 2. 回溯法的基本思想回溯法的基本思想 确定了解空间的组织结构后，回溯法就从开始确定了解空间的组织结构后，回溯法就从开始结点结点（根结点）出发（根结点）出发，以，以深度优先的方式搜索解深度优先的方式搜索解空间空间。这个开始结点就成为一个。这个开始结点就成为一个活结点活结点，同时也，同时也成为当前的成为当前的扩展结点扩展结点。在当前的扩展结点处，搜。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前的扩展结点。如为一个新的活结点，并成为当前的扩展结点。如果当前的扩展结点处不能再向纵深方向移动，则果当
4、前的扩展结点处不能再向纵深方向移动，则当前的扩展结点就成为当前的扩展结点就成为死结点死结点。此时应回溯到最。此时应回溯到最近的一个活结点处，并使这个活结点成为当前的近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已空间中搜索，直至找到所要求的解或解空间中已无活结点时为止。无活结点时为止。 第五章 回溯法6例：例：旅行售货员问题：旅行售货员问题：某售货员要到若干城市推销商某售货员要到若干城市推销商 品，已知各城市间的路程（或旅费）。他要选一条从品，已知各城市间的路程（或旅费）。他
5、要选一条从驻地出发，经过每个城市一遍，最后回到驻地的路线，驻地出发，经过每个城市一遍，最后回到驻地的路线，使总的路程（总的旅费）最小。使总的路程（总的旅费）最小。1234306541020图图5-3 5-3 四个顶点的带权四个顶点的带权图图ABCDEFGHIJKLMNOPQ1234342423434232图图5-4 5-4 旅行售货员问题的可行解空间树旅行售货员问题的可行解空间树 ABCFL59FGM60+659GCDHNHI252625DEJP19+6=25JKQ29+3025KEBA第五章 回溯法7综上所述，综上所述，回溯法解题包含以下步骤回溯法解题包含以下步骤: :(1) (1) 针对所
6、给的问题，定义问题的解空间；针对所给的问题，定义问题的解空间；(2) (2) 确定易于搜索的解空间结构确定易于搜索的解空间结构解空间树；解空间树；(3) (3) 以深度优先的方式搜索解空间树，并在搜索以深度优先的方式搜索解空间树，并在搜索过程中用过程中用剪枝函数剪枝函数（约束函数约束函数或或限界函数限界函数）避免无效搜索。避免无效搜索。 第五章 回溯法8 3. 3. 递归回溯递归回溯 由于回溯法是对解空间的深度优先搜索，因此，一由于回溯法是对解空间的深度优先搜索，因此，一般可用递归函数实现回溯法如下：般可用递归函数实现回溯法如下：void Backtack(int t) if ( t n )
7、Output(x); /t/t表示递归深度表示递归深度 else for (int i = f(n,t); i n) Output(x); else for (int i=0; i n) Output(x); else for (int i=t; i=n; i+) Swap(xt,xi); if (Constraint(t) & (Bound(t) Backtrack(t+1); Swap(xt,xi); 注意注意：在调用在调用Backtrack(1)执行此回溯算法之前，执行此回溯算法之前，先将变量数组先将变量数组x x初始化为单位排列初始化为单位排列(1,2,n)。 第五章 回溯法141.
8、1. 问题描述问题描述 n后问题要求在一个后问题要求在一个n*n格的棋盘上放置格的棋盘上放置n个皇后，使个皇后，使得她们彼此不受攻击。一个皇后可以攻击与之在同一行或得她们彼此不受攻击。一个皇后可以攻击与之在同一行或同一斜线上的其他任何棋子。因此，同一斜线上的其他任何棋子。因此，n n后问题等价于后问题等价于： 任何两个皇后不能在同行、同列、同一斜线上。任何两个皇后不能在同行、同列、同一斜线上。 例子：四皇后问题例子：四皇后问题: 给给4*4棋盘的行和列分别从左到右和从上到下编号为棋盘的行和列分别从左到右和从上到下编号为1，2，3，4，同时也给，同时也给4个皇后分别编号为个皇后分别编号为1，2，
9、3，4。由于要求不同的皇后不能放在同一行，不失一般性，可设由于要求不同的皇后不能放在同一行，不失一般性，可设皇后皇后i只放在第只放在第i行。行。 第五章 回溯法15128717225732466457273747576123412341112 341511521561 234四后问题的解空间树四后问题的解空间树1234232445666767727374757672778277826628788109 13088109 130151152153 154 155153 154 155234465156 61465156 6145 有有2 2个可行解个可行解：（2，4，1，3）、（）、（3，1，4
10、，2）1第五章 回溯法16 对对n后问题，可用后问题，可用n元组元组x1:n表示它的解。表示它的解。其中，其中，xi表示皇后表示皇后i i放在棋盘的第放在棋盘的第i i行的第行的第xi列。列。 若若2 2个皇后放置的位置分别是个皇后放置的位置分别是(i,j)和和(k,l)，则，则约束条件为：约束条件为： xixk ( (不在同一列不在同一列) ) i+jk+l, i-kj-l ( (不在同一斜线不在同一斜线) ) 即即|i- k|j- l| 用回溯法解用回溯法解n后问题时，可以用一棵完全后问题时，可以用一棵完全n叉树叉树来表示其解空间。用可行性约束函数来表示其解空间。用可行性约束函数Place可剪可剪去不满足行、列和斜线约束的子树。去不满足行、列和斜线约束的子树。 第五章 回溯法17 算法分析算法分析解空间树中内结点个数解空间树中内结点个数：对每个内结点，函数对每个内结点，函数Place检查当前检查当前扩展结点的每一个儿子是否可放扩展结点的每一个儿子是否可放当前列需耗时当前列需耗时O(n2)。总的时间耗费是总的时间耗费是= =O(nn+1) 10niin)(210nnnii
