else for (int i=t; i<=n; i++) { Swap(x[t],x[i]); if (Constraint(t) && (Bound(t)) Backtrack(t+1)); Swap(x[t],x[i]); }
}
注意：在调用Backtrack(1)执行此回溯算法之前， 先将变量数组x初始化为单位排列(1,2,…,n)。
第五章 回溯法
9
用回溯法搜索子集树的一般算法可描述如下：
void Backtrack(int t) { if (t > n) Output(x);
else for (int i=0; i<=1; i++) { x[t]=i; if (Constraint(t) && (Bound(t)) Backtrack(t+1)); }
{ x[t] =h(i); //h(i )：在当前扩展结点处x[t]的第i个可取值
if (Constrain(t) && Bound (t)) Backtrack(t+1); }
}
第五章 回溯法
7
用回溯法解题的一个显著特征：
问题的解空间是在搜索过程中动态生成的。 在任何时刻，算法只保存从根结点到当前扩展 结点的路径。若解空间树中从根到叶的最长路 径长度为h(n)，则回溯法所需的计算空间通 常为O(h(n))。显式存储整个解空间则需要 O(2 h(n))。
成为当前的扩展结点。在当前的扩展结点处，搜
索向纵深方向移至一个新结点。这个新结点就成
为一个新的活结点，并成为当前的扩展结点。如
果当前的扩展结点处不能再向纵深方向移动，则
当前的扩展结点就成为死结点。此时应回溯到最
近的一个活结点处，并使这个活结点成为当前的
扩展结点。回溯法即以这种工作方式递归地在解
空间中搜索，直至找到所要求的解或解空间中已
第五章 回溯法
8
4.子集树与排列树
图5-1和图5-4中的两棵解空间树是回溯法解题时常 遇到的两类典型的解空间树。 当所给的问题是从n个元素的集合S中找出满足某种 性质的子集时，相应的解空间树称为子集树。
例如，n个物品的0-1背包问题相应的解空间树称
为子集树。子集树通常有2n个叶结点，其结点总个 数为2n+1-1。 遍历子集树的任何算法均需Ω(2n)的计算时间。
优解的过程如下图所示。
1
B
1
0
D 10
E 1
A
0
1
0
C 1
F 0
0 G
1
H
IJ
K
L
M
N
45
50
25
25
图5-２ 在0-1背包问题的解空间树上搜索最优解
第五章 回溯法
0 O
0
3
2. 回溯法的基本思想
确定了解空间的组织结构后，回溯法就从开始
结点（根结点）出发，以深度优先的方式搜索解
空间。这个开始结点就成为一个活结点，同时也
2，3，4，同时也给4个皇后分别编号为1，2，3，4。 由于要求不同的皇后不能放在同一行，不失一般性，可设 皇后i只放在第i行。
第五章 回溯法
13
╳ ╳
╳
╳ ╳
╳ ╳
1
1
23 4
2 12 3 4 3 24 45
87
172
1 23 4
66 88 109 130 151
257
1 46 51 56 61 2 3 4
过程中用剪枝函数（约束函数或限界函数） 避免无效搜索。
第五章 回溯法
6
3. 递归回溯
由于回溯法是对解空间的深度优先搜索，因此，一 般可用递归函数实现回溯法如下：
void Backtack(int 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)：分别表示当前可扩展结点未搜索过的 子树的起始编号和终止编号.
若2个皇后放置的位置分别是(i,j)和(k,l)，则
67 72 77 82 152
123 4 73 74 75 76
12 3 4 153 154 155 156
四后问题的解空间树
有2个可行解：
（2，第4五，章 1回，溯法3）、（3，1，4，2）14
2. 算法设计
对n后问题，可用n元组x[1:n]表示它的解。 其中，x[i]表示皇后i放在棋盘的第i行的第x[i] 列。
无活结点时为止。
第五章 回溯法
4
例：旅行售货员问题：某售货员要到若干城市推销商 品，已知各城市间的路程（或旅费）。他要选一条从 驻地出发，经过每个城市一遍，最后回到驻地的路线， 使总的路程（总的旅费）最小。
AA
1 30 2
1
6
5 10
4
B
2
34
3 20 4
C
DD
图5-3 四个顶点的带权图 3
4
2
4
}
第五章 回溯法
10
当所给的问题确定n个元素满足某种性质的排 列时，相应的解空间树称为排列树。
例如，旅行售货员问题相应的解空间树称为排
列树。排列树通常有n！个叶结点。遍历子集 树的任何算法均需Ω(n!)的计算时间。
第五章 回溯法
11
用回溯法搜索排列树的一般算法可描述如下：
void Backtrack(int t) { if (t > n) Output(x);
第五章 回溯法
12
二、n后问题 (p154)
1. 问题描述
n后问题要求在一个n*n格的棋盘上放置n个皇后，使 得她们彼此不受攻击。一个皇后可以攻击与之在同一行或 同一斜线上的其他任何棋子。因此，n后问题等价于：
任何两个皇后不能在同行、同列、同一斜线上。
例子：四皇后问题: 给4*4棋盘的行和列分别从左到右和从上到下编号为1，
E
2
3
F
GG HH
IJ
K
26>25
4
3
4
2
3
2
L
MM NN
OP
QQ
59 60+6>59 25
19+6=25 29+30>25
图5-4 旅行售货员问题的可行解空间树
第五章 回溯法
5
综上所述，回溯法解题包含以下步骤:
(1) 针对所给的问题，定义问题的解空间； (2) 确定易于搜索的解空间结构—解空间树； (3) 以深度优先的方式搜索解空间树，并在搜索
第五章----回溯法--基本概念-n后问题
通常把解空间组织成解空间树或图。例如：对于 n=3时的0-1背包问题，其解空间用一棵完全二叉 树表示，如下图所示。
A
1
0
B
1
0
C
1
0
D 10
E
10F10 NhomakorabeaG
1
0
H
IJ
K
L
MN
O
图5-1 0-1背包问题的解空间树
第五章 回溯法
2
例： n=3时的0-1背包问题，W={16，15，15}， p={45，25，25}，C=30。在其解空间树上搜索最