2010-5-14 计算机算法设计与分析 1
第五章
回溯法
2010-5-14 计算机算法设计与分析 2
用计算机求解问题
问题空间 现实求解过程 实际
解
状态空间
对象的定义
机器求解过程
算法与程序的设计
机内解
2010-5-14 计算机算法设计与分析 3
计算机求解的过程
? 在状态空间寻找机内解可以看成是从初始状态
出发搜索目标状态 (解所在的状态 )的过程 。
状态空间
初始状态 目标状态搜索
? 搜索的过程可描述为,S0?S1?… ?Sn,其中
S0为初态,Sn为终态。或者说 ψ(S0)且 φ(Sn),这
里 ψ称为初始条件,φ称为终止条件。
2010-5-14 计算机算法设计与分析 4
求解是状态空间的搜索
? 求解的过程可以描述为对状态空间的搜索
S0
S11 S12 … S1k
… … … … … …
Sn1 …… Sni …… Snm
其中 S0为初始状
态，不妨设 Sni为
终止状态
? 于是问题的求解就是通过搜索寻找出一条从初
始状态 S0到终止状态 Sni的路径。
2010-5-14 计算机算法设计与分析 5
0-1背包问题的状态空间树
? 下面是第三章 的 0-1背包问题的状态空间树：
SI0
S0
1
S10
S00
1
S01
0
S10
1
S11
0
S000
1
S001
0
S010
1
S011
0
S100
1
S101
0
S110
1
S111
? 对应第三章 的例子中的终止状态为 S011。
2010-5-14 计算机算法设计与分析 6
几种搜索方法
状态空间的搜索实际上是一种树 /DAG的搜索，
常用的方法有：
? 广度优先的搜索
? 深度优先的搜索
? 启发式的搜索
从初始状态开始，逐层地进行搜索。
从初始状态开始，逐个分枝地进行搜索。
从初始状态开始，每次选择最有可能达到终
止状态的结点进行搜索。
2010-5-14 计算机算法设计与分析 7
三种搜索的优劣之处
? 一般来说，三种搜索方法各有优劣之处：
? 广度优先搜索的优点是一定能找到解；缺点是
空间复杂性和时间复杂性都大。
? 深度优先搜索的优点是空间复杂性和时间复杂
性较小；缺点是不一定能找到解。
? 启发式搜索的是最好优先的搜索，优点是一般
来说能较快地找到解，即其时间复杂性更小；
缺点是需要设计一个评价函数，并且评价函数
的优劣决定了启发式搜索的优劣。
2010-5-14 计算机算法设计与分析 8
树搜索的一般形式
? SearchTree(Space T)//表 L用来存放待考察的结点
? {unfinish = true; L = T.initial;
? // unfinish表示搜索未结束，先将初始状态放入 L
? while (unfinish || L≠Φ) {
? a = L.first; //从 L中取出第一个元素
? if (a is goal) unfinish = false //若 a是终态则结束
? else Control-put-in(L,Sons(a));
? } //否则，将 a的儿子们 以某种控制方式 放入 L中
2010-5-14 计算机算法设计与分析 9
三种搜索的不同之处
树的三种搜索方法的不同就在于它们对
表 L使用了不同控制方式：
? L是一个队列
? L是一个栈
? L的元素按照
某方式排序
? 广度优先搜索
? 深度优先搜索
? 启发式搜索
? 其中，深度优先搜索就是回溯法。
2010-5-14 计算机算法设计与分析 10
递归回溯法的一般形式
? Try(s){
? 做挑选候选者的准备；
? while (未成功且还有候选者 ) {
? 挑选下一个候选者 next；
? if (next可接受 ) {
? 记录 next；
? if (满足成功条件 ) {成功并输出结果 }
? else Try(s+1);
? if (不成功 ) 删去 next的记录 ; }}
? return 成功与否 }
2010-5-14 计算机算法设计与分析 11
迭代回溯法的一般形式
? 先让我们回顾解空间搜索的一般形式：? SearchTree(Space T)//表 L用来存放待考察的结点
? {unfinish = true; L = T.initial;
? // unfinish表示搜索未结束，先将初始状态放入 L
? while (unfinish || L≠Φ) {
? a = L.first; //从 L中取出第一个元素
? if (a is goal) finish = false //若 a是终态则结束
? else Control-put-in(L,Sons(a));
? } //否则，将 a的儿子们 以某种控制方式 放入 L中
回溯法中表 L为栈，将初始状态压入栈中。
弹出栈顶元素
在通常求解问题时，
解是由逐个状态构
成的。因此，这里
还需要判断状态是
否可接受，并进行
纪录路径等工作。
如果 a可接收但未终
止，则要将 a的后继
压入栈中。如果要
抛弃状态 a,当 a是
最后一个儿子时，
还需要消除原有的
纪录甚至回溯一步。
2010-5-14 计算机算法设计与分析 12
如何判断最后一个儿子？
? 若只要遍历解空间树上的结点，那么将各个结
点按栈的方式控制便可实现深度为主的搜索。
? 但是在求解问题时，需要记录解的路径，在回
溯时还需要删除结点和修改相应的信息。
? 栈中的结点是分层次的，而现在没有区分它们
的层次。这就增加了回溯判断和操作的困难。
那么怎么办？? 采用一个简洁有效的方法：设计一个末
尾标记，每次压栈时，先压入末尾标记。
2010-5-14 计算机算法设计与分析 13
用末尾标记的迭代回溯
? Backtrack(Tree T) {
? unfinish = true; L.Push(T.root);
? while (unfinish || L≠Φ) {
? a = L.Pop( );
? if (a is the last mark) backastep( );
? if (a is good) {record(a);
? if (a is goal) {unfinish = false; output( );}
? else if (a has sons) L.Push-Sons(a)
? else move-off(a);}}}
若栈顶元素是
末尾标记，说
明这个路径已
经到头了，需
要回溯一步。
若 a是可以接
受的，则将 a
加入求解的路
径中 。
若 a是目标节
点，则结束搜
索并输出求解
的路径 。
若 a不是目标
节点且 a有后
即，则将 a的
后继压入栈
中。
这里的 L.Push-
Sons(a)要先压
入末尾标记，
然后再压入后
继结点。
若 不是目标
节点又没有
后继, 则将 a
从解的路径
中删除 。
2010-5-14 计算机算法设计与分析 14
不可接受的结点
? 破坏了解的相容条件的结点
? 超出了状态空间的范围，或者说不满足
约束条件，的结点；
? 评价值很差的结点，即已经知道不可能
获得解的结点；
? 已经存在于被考察的路径之中的结点，
这种结点会造成搜索的死循环 。
2010-5-14 计算机算法设计与分析 15
N后问题
? 要求在一个 n× n的棋盘上放置 n个皇后，使得
她们彼此不受攻击。
? 按照国际象棋的规则，一个皇后可以攻击与之
同一行或同一列或同一斜线上的任何棋子。
? 因此,N后问题等价于：要求在一个 n× n的棋
盘上放置 n个皇后，使得任意两个皇后不得在
同一行或同一列或同一斜线上。
2010-5-14 计算机算法设计与分析 16
用递归回溯法求 N后问题
? Try(s){
? 做挑选候选者的准备；
? while (未成功且还有候选者 ) {
? 挑选下一个候选者 next；
? if (next可接受 ) {
? 记录 next；
? if (满足成功条件 ) {成功并输出结果 }
? else Try(s+1);
? if (不成功 ) 删去 next的记录 ; }}
? return 成功与否 }
先回顾递归回溯法的一般形式,
2010-5-14 计算机算法设计与分析 17
用递归回溯法求 N后问题
? Try(s){
? 做挑选候选者的准备；
? while (未成功且还有候选者 ) {
? 挑选下一个候选者 next；
? if (next可接受 ) {
? 记录 next；
? if (满足成功条件 ) {成功并输出结果 }
? else Try(s+1);
? if (不成功 ) 删去 next的记录 ; }}
? return 成功与否 }
s为准备放置后的行数 候选者为 1到 n列。
j = 0; q = 0; 令列标记 j = 0； q表示未成功。
列数不到 n就还有候选者
!q && j < n ) {
列数加 1
j++;
各后都安全，便可接受
Safe(s,j)) {
记下该行后的位置 (列数 )
Record(s,j);
n行后都放完就成功了
(s = = n) {q = 1; output( );}
不成功，删
去后在该行
的位置。
(!q) Move-Off(s,j); }}}
q }
2010-5-14 计算机算法设计与分析 18
求解 N后问题中的数据表示
? 数组 B[n]表示棋盘。若 B[i]=j,1≤i,j≤n,表示
棋盘的第 i行第 j列上有皇后。
? 数组 C[j]=1表示第 j列上无皇后, 1≤j≤n。
? 数组 D[k]=1表示第 k条下行
(↘ )对角线上无皇后。
1
2
3
4
5
6
1 2 3 4 5 6
k = i + j, 2≤k≤2n。
这里，
2010-5-14 计算机算法设计与分析 19
求解 N后问题中的数据表示
? 数组 B[n]表示棋盘。若 B[i] = j,1≤i,j≤n,表
示棋盘的第 i行第 j列上有皇后。
? 数组 C[j] = 1表示第 j列上无皇后, 1≤j≤n。
? 数组 D[k] = 1表示第 k条下行
(↘ )对角线上无皇后。
k = i + j, 2≤k≤2n。
这里，
? 数组 U[k] = 1表示第 k条上行
(↗ )对角线上无皇后。 12
3
4
5
6
1 2 3 4 5 6k = i – j, –n+1≤k≤n–1。
这里，
2010-5-14 计算机算法设计与分析 20
求解 N后问题中的子程序
? Record(s,j) { k = s – j + n – 1;
B[s] = j; C[j] = 0; D[s + j – 1] = 0; U[k] = 0; }
? Move-Off(s,j) {k = s – j + n – 1;
B[s] = 0; C[j] = 1; D[s + j – 1] = 1; U[k] = 1; }
? Safe(s,j) {k = s – j + n – 1;
if (C[j] && U[k] && D[s + j – 1]) return true
else return false; }
2010-5-14 计算机算法设计与分析 21
求解 N后问题的主程序
? N-Queens( ) {
? int B[n + 1],C[n + 1],D[2n],U[2n];
? for (j = 1,j < n + 1; j++) {
? B[j] = 0; C[j] = 1;
? U[2j] = 1; U[2j – 1] = 1;
? D[2j] = 1; D[2j – 1] = 1;}
? try(1);
? output(B); }
将数组 B[n],
C[n],U[2n]
和 D[2n]都
赋予初值。
从第一行开始递归
2010-5-14 计算机算法设计与分析 22
N后问题的迭代程序
? 先看看迭代回溯法的一般形式：? Backtrack(Tree T) {
? unfinish = true; L.Push(T.root);
? while (unfinish || L≠Φ) {
? a = L.Pop( );
? if (a is the last mark) backastep( );
? if (a is good) {record(a);
? if (a is goal) {unfinish = false; output( );}
? else if (a has sons) L.Push-Sons(a)
? else move-off(a);}}}
迭代从第一行开始，
将第一行的 1~n列
和 0压入栈中，这
里 0作为末尾标记 。
i = 1; L.Push(1,2,…,n,0) ;
a是末尾标记则回溯。
(a == 0) backastep;
回溯需要
做什么？回溯需要退回一行，即 i–– ； 同时删除
该行的原纪录。{i––; a = B[i]; Move-Off(i,a); }
如果 safe(i,a)，
则放下后。
(Safe(i,a)) Record(i,a);
如果到了第 n
行，则成功。
(i == n)
当行 i < n时，则
必定有后继 。 无
需考虑此情况。
{i++; L.Pu h(1,2,…,n,0);}
}}}
2010-5-14 计算机算法设计与分析 23
N后问题的迭代程序
? Backtrack(Tree T) {
? unfinish = true; i = 1; L.Push(1,2,…,n) ;
? while (unfinish || L≠Φ) {
? a = L.Pop( );
? if (a == 0) {i– –; a = B[i]; Move-Off(i,a);}
? if (Safe(i,a)) {Record(i,a);
? if (i = = n) {unfinish = false; output(B);}
? else {i++; L.Push(1,2,…,n,0);}
? }}}
2010-5-14 计算机算法设计与分析 24
迭代回溯解 N后问题的主程序
? N-Queens(n) {
? int B[n + 1],C[n + 1],D[2n],U[2n];
? for (j = 1,j < n + 1; j++) {
? B[j] = 0; C[j] = 1;
? U[2j] = 1; U[2j – 1] = 1;
? D[2j] = 1; D[2j – 1] = 1;}
? Backtrack(n,B);
? }
2010-5-14 计算机算法设计与分析 25
N后问题的时间复杂性
? 如果只要找出 N后问题的一个解，那么这
是一个求路径的问题。
? 求路径：只需要找到一条路径便可以得
到解。设每个状态有 k个后继，其搜索树
为 K叉树，其结点总数为 kn+1–1,遍历的
时间为 O(kn),这里 n为找到解的路径长度。
? N后问题的路径深度为 n,可选择的后继
有 n个，所以时间复杂性为 O(nn)。
2010-5-14 计算机算法设计与分析 26
旅行售货员问题
? TSP,某售货员到若干城市去推销商品，已知
各城市之间的路程 (或旅费 )。他要选定一条路
线，经过每个城市一遍最后回到驻地的路线，
使得总的路程 (或总旅费 )最小。
? 设 G=(V,E)是一个带权图。图中各边的费用 (权
值 )为正。图中一条周游路线是包括 V中所有顶
点的回路。一条周游路线的费用是该路线上所
有边的费用之和。所谓旅行售货员问题就是要
在图 G中找出一条最小费用的周游路线。
2010-5-14 计算机算法设计与分析 27
? Try(s){
? 做挑选候选者的准备；
? while (未成功且还有候选者 ){
? 挑选下一个候选者 next；
? if (next可接受 ) {
? 记录 next；
? if (满足成功条件 ) {成功并输出结果 }
? else Try(s+1);
? if (不成功 ) 删去 next的记录 ; }}
? return 成功与否 }
线路上的第 s个结点 这里只需依次考
察 n–1个结点，即
for (i=2; i<=n; i++)
下一个候选就是 i。结点 i尚未在路线中且总耗费值不大。
考虑 TSP的递归回溯算法
就是将结点 i放入路
线中并修改耗费值
s == n
若新线路更好，就用
新线路取代老线路。
这里无所谓成功与否，
因为每一条周游路线
都要进行比较。
2010-5-14 计算机算法设计与分析 28
TSP的递归回溯算法
? Try(s){
? for (i = 2; i <= n; i++)
? if (Accept(i)) {
? Record(s,i)；
? if (s = = n)
? if (better) TakeNewPath( ) ;
? else Try(s+1);
? Move-off(s,i)}
? return }
2010-5-14 计算机算法设计与分析 29
求解 TSP的数据结构
? 用数组 C[n][n]存放个城市间的费用值。
? 用数组 P[n]记录已经找到的费用最小的周游路
线,C为其相应的费用,C初值为 ∞。
? 用数组 N[n]记录目前正在寻找的周游路线,NC
为其相应的费用；
? 如果 NC+C[N[n]][1]小于 C,则路线 N更佳，于
是 P[] = N[],Cost = NC+C[N[n]][1]。
? 如果结点 next不是 N中已有的结点，且 Cost大于
NC+C[N[i]][next],则结点 next是可接受的。
2010-5-14 计算机算法设计与分析 30
TSP的递归程序 Try
? Try(s){
? for (i = 2; i <= n; i++)
? if (Accept(i)) {
? Record(s,i)；
? if (s = = n)
? if (better) TakeNewPath( ) ;
? else Try(s+1);
? Move-off(s,i)}
? return }
(C–NC >C[N[s]][i] &&T[i]) {
数组 T[]表示结点 i尚未被选
(C >NC+C[ [s]][1]) TakeNewPath( );
2010-5-14 计算机算法设计与分析 31
Try中的子程序
? Record(s,i);
{NC = NC + C[N[s]][i]; T[i] = 0; N[s] = i; }
? Move-off(s,i);
{NC = NC – C[N[s]][i]; T[i] = 1; N[s] = 0;}
? TakeNewPath( ) {
? for (i=1; i<=n; i++) P[i] = N[i];
? C = NC + C[N[s]][1];}
2010-5-14 计算机算法设计与分析 32
递归回溯求 TSP的主程序
? TSP(n,C[n][n]) {
? for (i = 1; i <= n; i++)
? {N[i]=0; P[i] = 0; T[i] = 1}
? NC = 0； C = ∞; N[1]=1; T[1] = 0;
? Try(1);
? Output(P)；
? }
2010-5-14 计算机算法设计与分析 33
考虑 TSP的迭代程序
? 为了便于迭代程序中回溯的判断，我们
将城市结点编号为 1 ~ n,用编号 0作为末
尾的标记。
? 先回顾一下采用末尾标记的迭代回溯法：
2010-5-14 计算机算法设计与分析 34
考虑 TSP的迭代程序
? Backtrack(Tree T) {
? unfinish = true; L.Push(T.root);
? while (unfinish || L≠Φ) {
? a = L.Pop( );
? if (a is the last mark) backastep( );
? else if (a is good) {Record(a);
? if (a is goal) {unfinish = false; output( );}
? else if (a has sons) L.Push-Sons(a)
? else Move-off(a);}}}
要比较所有路径，无需此句。
L≠Φ ) {
初始化后压入第一个结点。
j = 1; N[j] = 1; L.Push-Sons(1
末尾标记为 0。
(a == 0) back step( );
删除第 j个结点，然后 j– –。
{Move-off(N[j–1],N[j]); j––;}
a不在路线中且新
增后的费用仍低。
T[a]&&C–NC>C[N[i]][a]){Record(N[j],a);
已经 n个结点且新
路线的费用更低。
这个判断不需要了。
(s = = n ) if (C >NC+C[a][1])
{TakeNewPath( ); Move-off(N[j],a);}}
els {j++; L.Push-Sons(a)}}}
2010-5-14 计算机算法设计与分析 35
TSP的迭代回溯
? Backtrack(n,C) {
? j = 1; N[j] = 1; L.Push-Sons(1);
? while (L≠Φ) { a = L.Pop( );
? if (a == 0) {Move-off(N[j–1],N[j]); j––;}
? else if (T[a] && C – NC > C[N[i]][a]) {
? Record(N[j],a)；
? if (s = = n ) if (C >NC+C[a][1])
? {TakeNewPath( ); Move-off(N[j],a);}}
? else {j++; L.Push-Sons(a)}}}
2010-5-14 计算机算法设计与分析 36
迭代回溯求 TSP的主程序
? TSP(n,C[n][n]) {
? for (i = 1; i <= n; i++)
? {N[i]=0; P[i] = 0; T[i] = 1}
? NC = 0； C = ∞; N[1]=1; T[1] = 0;
? Backtrack(n,C);
? Output(P)；
? }
2010-5-14 计算机算法设计与分析 37
求解 TSP的时间复杂性
? 显然 TSP是一个求排列的问题。
? 求排列：确定 n个元素的满足某种性质的
排列。其搜索树称为排列树，通常有 n!
个叶结点，因此遍历排列树需要时间为
O(n!)。
? 所以 TSP问题的时间复杂性为 O(n!)
2010-5-14 计算机算法设计与分析 38
用回溯法解 0-1背包问题
? 类似于旅行售货员问题，用一个数组 P[n]存放
目前取得的最优解，用变量 V表示其价值；再
用一个数组 N[n]来产生新的解，用变量 NV表示
其价值，用变量 W表示其重量 。 如果新解更优，
则替代原来的最优解，否则就丢弃新解。然后
回溯寻找下一个新解。
? 为此，我们先回顾一下回溯法的一般递归算法：
2010-5-14 计算机算法设计与分析 39
用回溯法解 0-1背包问题
? Try(s){
? 做挑选候选者的准备；
? while (未成功且还有候选者 ){
? 挑选下一个候选者 next；
? if (next可接受 ) {
? 记录 next；
? if (满足成功条件 ) {成功并输出结果 }
? else Try(s+1);
? if (不成功 ) 删去 next的记录 ; }}
? return 成功与否 }
考察的第 s个物品
只需考两种情况，
选或不选，即
for (i=0; i<2; i++)
下个候选就是 i。物体 s可放入背包中 ；
将 s放入背包中并
修改权重与容量 ；
s = = n
这里无论成功与
否都要继续考察,记录” 的
逆操作
2010-5-14 计算机算法设计与分析 40
用回溯法解 0-1背包问题
? Try(s){
? for (i = 0; i < 2; i++)
? if (Accept(i)) {
? Record(s,i)；
? if (s = = n) {if ( better ) TakeNewChoice( );}
? else Try(s+1);
? Move-off(s,i);}
? return }
(W+w[s]*i <= C) {
(NV > V)
2010-5-14 计算机算法设计与分析 41
0-1背包问题中的几个子程序
? Record(s,i){ N[s] = i; W=W + w[s]*i;
NV = NV + v[s]*i;}
? Move-off(s,i){N[s] = 0; W = W – w[s]*i;
NV = NV – v[s]*i;}
? TakeNewChoice( ) {
? for (i=1; i<=n; i++) {
? P[i] = N[i]; V = NV;}}
2010-5-14 计算机算法设计与分析 42
0-1背包问题的主程序
? Bag(n,C,w[n],v[n]) {
? for (i=1; i<=n; i++)
? {N[i]=0; P[i] = 0; T[i] = 1;}
? NV = 0,W = 0; V = 0;
? Try(1);
? Output(P); }
2010-5-14 计算机算法设计与分析 43
考虑 0-1背包问题的迭代实现
? 先看看回溯法的一般的迭代形式：? Backtrack(Tree T) {
? unfinish = true; L.Push(T.root);
? while (unfinish || L≠Φ) {
? a = L.Pop( );
? if (a is the last mark) backastep( );
? else if (a is good) {Record(a);
? if (a is goal) {unfinish = false; output( );}
? else if (a has sons) L.Push-Sons(a)
? else Move-off(a);}}}
要比较所有组合，无需此句。
(L≠Φ) { 从物品 1开始，压入
物品 1的两种选择。
j = 1; L.Push(–1,0,1);
用 –1作末尾标记 。
== –1) backastep( );
回溯：删除相关记
录，并退回一步。
{Move-off(j,N[j]); j––;}
只要容量没有超过就可以选
(W+w[j]*a <= C) {Record(j,a);
j = n 。
( j == n )
若新的组合更好，
则选取新组合 。
{if (V < NV) TakeNewChoice( );}
只要没选购就可继续
选，故必定有后继 。
else {j++; L.Push(–1,0,1);}
}}}
2010-5-14 计算机算法设计与分析 44
0-1背包问题的迭代实现
? Backtrack(Tree T) {
? j = 1; L.Push(–1,0,1);
? while (L≠Φ) {
? a = L.Pop( );
? if (a == –1) {Move-off(j,N[j]); j– –;}
? else if (W+w[j]*a <= C) {Record(a);
? if (j == n ) {if (V < NV) TakeNewChoice( );}
? else {j++; L.Push(–1,0,1);}
? }}}
2010-5-14 计算机算法设计与分析 45
0-1背包问题的时间复杂性
? 显然 0-1背包问题是一个求子集的问题。
? 求子集：从 n个元素的集合 S中找出满足
某个性质子集。其搜索树称为子集树，
是棵二叉树，通常有 2n个叶结点，遍历
的时间为 O(2n) 。
? 0-1背包问题的时间复杂性为 O(2n)。
2010-5-14 计算机算法设计与分析 46
求排列、求子集、求路径
? 求排列：确定 n个元素的满足某种性质的排列。
其搜索树称为排列树，通常有 n!个叶结点，因
此遍历排列树需要时间为 O(n!)。
? 求子集：从 n个元素的集合 S中找出满足某个性
质子集。其搜索树称为子集树，是棵二叉树，
通常有 2n个叶结点，遍历的时间为 O(2n) 。
? 求路径：只需要找到一条路径便可以得到解。
设每个状态有 k个后继，其搜索树为 K叉树，其
结点总数为 kn+1–1,遍历的时间为 O(kn),这里 n
为找到解的路径长度。
2010-5-14 计算机算法设计与分析 47
构造一个数环
? 请设计一个算法生成这
样的一个数环：此数环
由 2n个 0和 1组成，使得
2n个 n位的二进制数中
的每一个数在数环中恰
出现一次。如右图就是
23个 0和 1组成的环。
0
0
0
1
0
1
1
1
2010-5-14 计算机算法设计与分析 48
用回溯法构造数环
? 自然想到用回溯法来构造数环，那就是：
? 1、先放下 n个 0，即数 0；
? 2、然后，在其后添上一个数字 (0或者 1)，
使得产生的数不重复。
? 3、若成功，就继续像 2中那样添加后面
的数字。若添 0或 1都不行，就回溯一步。
? 4、重复 2,3，直到 2n个数字全部填完。
2010-5-14 计算机算法设计与分析 49
用递归回溯法构造此环
先回顾回溯法的递归实现：
? Try(s){
? 做挑选候选者的准备；
? while (未成功且还有候选者 ) {
? 挑选下一个候选者 next；
? if (next可接受 ) {
? 记录 next；
? if (未完成 ) {
? Try(s+1);
? if (不成功 ) 删去 next的记录 }}}
? return 成功与否 }
2010-5-14 计算机算法设计与分析 50
用递归回溯法构造此环
? Try(s){
? 做挑选候选者的准备；
? while (未成功且还有候选者 ) {
? 挑选下一个候选者 next；
? if (next可接受 ) {
? 记录 next；
? if (未完成 ) {
? Try(s+1);
? if (不成功 ) 删去 next的记录 }}}
? return 成功与否 }
j = 0; q = 0;
(j < 2 && !q) {
j++;
–1;
(accept(s,j)) {
Record(s,j);
(s < 2n) {
if !q) Move-Off(s,j); }}}
q }
2010-5-14 计算机算法设计与分析 51
如何构造 accept(s,j)
? 在第 s步放下数字 j是可接受的，当且仅当
新产生的数与已经产生的数不重复。
? 怎样知道新产生的数不重复呢？一种方法就是用新产生的 n位二进制数去
和已经产生的 n位二进制数逐个比较，看
是否有完全匹配的。如果没有，就是不
重复的。然而，这样做的时间复杂性是
很高的。
另一种方法是用一个布尔数组表示已经
存在的 n位二进制数，对新的 n位二进制
数只要查看该布尔数组便可以知道。如
果没有，就是不重复的，并登记新数。
显然这样做的时间复杂性要低得多。
2010-5-14 计算机算法设计与分析 52
构造此环的数据结构
? 首先，需要一个数据结构来存放所构造
的环。 一维数组 Circle[2n]。
? 其次，需要一个登记已经产生的 n位二进
制数的一维数组 Exist[2n]。
若 Exist[ni] = 1,则数 ni已经存在；
若 Exist[ni] = 0,则数 ni尚未产生。
? 于是,accept(s,j)为查看数组 Exist，即，
accept(s,j)为真当且仅当 Exist[ni] = 0,这
里 ni是第 s个符号填上数字 j所产生的数。
2010-5-14 计算机算法设计与分析 53
如何由数 mi推出数 mi+1
? 设前次产生的 n位二进制数为 mi,本次产
生的 n位二进制数为 mi+1，那么
a1 a2 ?? an
mi
j
mi+1
mi+1是 mi左移
一位后添加
数字 j。
mi+1= (2* mi + j ) mod 2n 。
? 初始化时，令 m0 = 0。
2010-5-14 计算机算法设计与分析 54
构造此环的递归回溯程序
? Try(s){
? j = 0; q = 0;
? while (j < 2 && !q) {
? j++;
? if (accept(s,j)) {
? Record(s,j);
? if (s < 2n) {
? Try(s+1);
? if (!q) Move-Off(s,j); }}}
? return q }
为了便于推算产生的
新数，前次产生的数
最好是作为参数传递。
,m) 在判断 accept之前应
该计算出填上 j以后
所产生的新数。
new = (2* m + j) mod max; accept(s,j)即为Exist[new] = 0。
!Exist[new]) {
Record(s,j)为登记数组
Circle[s]和 Exist[new]。
Cir le[s] = j Exist[new] = 1;
max) {
进行下一步
递归时,new
作为参数传
递下去。,new);
Move-Off(s,j)
为删除数组
Circle[s]和
Exist[new]。{Circle[s] = 0; Exist[new] = 0;}}}
2010-5-14 计算机算法设计与分析 55
构造此环的主程序
? Make-circle(n){
? int i,s,max = 2n;
? int Circle[max],Exist[max];
? for (i = 0,i < max; i++) Exist[i] = 0;
? for (i = 0,i < n; i++) Circle[i] = 0;
? Exist[0] = 1; s = n + 1；
? Try(s,0);}
2010-5-14 计算机算法设计与分析 56
构造此环的时间复杂性
? 显然此环的构造是一个求路径的问题。
? 求路径：只需要找到一条路径便可以得
到解。设每个状态有 k个后继，其搜索树
为 K叉树，结点总数为 km+1–1,遍历的时
间为 O(km),这里 m为找到解的路径长度。
? 构造环的路径的深度为 m = 2n,后继只有
2个，因此其时间复杂性为 O(2m)。
? 不过，构造此环可以不需要回溯！
2010-5-14 计算机算法设计与分析 57
构造此环的无回溯算法
? 这个环其实可以用一种不需要回溯的算
法来构造，而且这个算法很简单：
? 1、先放下 n个 0，即数 0；
? 2、每次先放数字 1，如果不行，即产生
的数重复，就改放数字 0。 (先 1原则 )
? 3、反复执行 2，直至把 2n个数字全部放
完即可。
2010-5-14 计算机算法设计与分析 58
构造此环的无回溯算法
? MakeCircle(int n){
? int s,j,MAX = 2n;
? int Circle[MAX],Exist[MAX];
? for (j = 0; j < MAX; j++)
? {Circle[j] = 0; Exist[j] = 0;}
? j = n; s = 0; Exist[s] = 1;
? while (j < MAX) {
? s = (2*s) mod MAX；
? if (!Exist[s + 1]) {Circle[j] = 1; s = s + 1;}
? Exist[s] = 1; j = j + 1; }}
先将所有数
字都填为 0
第一个
数为 0。
若添 1是新数，则
填 1；否则仍是 0。
2010-5-14 计算机算法设计与分析 59
证明无回溯算法的正确性
? 我们可以证明这个无回溯的算法是正确
的。为此我们需要证明两点：
? 1、算法生成了 2n个不重复的 n位二进制
数，即每个 n位二进制数恰出现一次。
? 2、这样生成的 2n个 n位二进制数恰好构
成了一个环。
2010-5-14 计算机算法设计与分析 60
2n个数中无重复
? 用归纳法来证明这 2n个数中无重复：
? 归纳基础：当 j = 0时,s0 = 0,序列无重复数。
? 归纳假设：设当 j = k时，序列 s0,s1,……,s k没
有重复的数。
? 归纳证明：当 j = k + 1时，由算法可知,sk+1为：
? 1、填上一个数字 1所产生的，由算法中的判断
可知，生成的数 sk+1为新数，该序列没有重复。
? 2、填上一个数字 0所产生的，我们用反证法来
证明 sk+1为新数。
2010-5-14 计算机算法设计与分析 61
反证法证明填 0是新数
? 假设填 0生成的 sk+1为重复数。令 sk+1为 w0,这
里 w为 n–1位二进制符号串。
? 由算法可知 w1也重复。 ∴ 原序列中必有两个子
序列 ?1= w1,?2 = w0。 且 ?1的位置在前。
先 1原则
?1 ?2
w 1 w 0 w 10
? ∴ 原序列中必有三个位置都大于 1的子串 w,即
三个子串 w的前面都至少有一个符号。
a b c
? ∴ 原序列中必有三个子串分别为 aw,bw和 cw。
? 又 ∵ a,b和 c的取值为 0或 1,∴ 三个子串中必
有重复。即原序列有重复。矛盾。证毕。
2010-5-14 计算机算法设计与分析 62
证明构成环
? 要证明算法生成的 2n个数构成环，只需要证明
最后一个数 s = 10…0 = 1 w,w为 n–1个 0。2n
证明：当 2n个数全部生成后，若继续在后面填
上一个数字，则无论是填 1还是填 0，所生成的
第 2n+1个 n位二进制数都必定是个重复的数。
? 由此可知在原序列中必定在三个位置上有相同
的子串 w。 若不然，第 2n+1个数不是重复的。
? 然而原序列中没有重复数。
? 这只能是第一个 w的位置为 1，即在最前面。
? 最前面是 n个 0，所以 w为全 0的符号串。证毕。
2010-5-14 计算机算法设计与分析 63
受到的启迪
? 显然无回溯算法的复杂性只有 O(m),m = 2n。
即回溯算法复杂性是指数函数，而无回溯算法
的仅是 1阶的。后者的效率要高得多！
? 由此我们看到，一个问题除了通用的方法外，
还可能存在着其特有的高效率的算法。
? 从这个算法的正确性证明中，我们看到，如果
对一个算法进行理论上的推证，不仅能够使我
们确信算法是正确的，而且还可以使我们对问
题有本质上的深入认识。
2010-5-14 计算机算法设计与分析 64
回溯法小结
? 回溯法是一种通用的算法，实为深度优先的搜
索方法。
? 回溯法可以 递归实现,也可以 迭代实现 。
? 回溯法通常求解三类问题：
? (1)求排列：时间复杂性为 O(f(n)n!)；
? (2)求子集：时间复杂性为 O(f(n)2n)；
? (3)求路径, 时间复杂性为 O(f(n)kn)。
? 这里 f(n)为处理一个结点的时间复杂性。
第五章
回溯法
2010-5-14 计算机算法设计与分析 2
用计算机求解问题
问题空间 现实求解过程 实际
解
状态空间
对象的定义
机器求解过程
算法与程序的设计
机内解
2010-5-14 计算机算法设计与分析 3
计算机求解的过程
? 在状态空间寻找机内解可以看成是从初始状态
出发搜索目标状态 (解所在的状态 )的过程 。
状态空间
初始状态 目标状态搜索
? 搜索的过程可描述为,S0?S1?… ?Sn,其中
S0为初态,Sn为终态。或者说 ψ(S0)且 φ(Sn),这
里 ψ称为初始条件,φ称为终止条件。
2010-5-14 计算机算法设计与分析 4
求解是状态空间的搜索
? 求解的过程可以描述为对状态空间的搜索
S0
S11 S12 … S1k
… … … … … …
Sn1 …… Sni …… Snm
其中 S0为初始状
态，不妨设 Sni为
终止状态
? 于是问题的求解就是通过搜索寻找出一条从初
始状态 S0到终止状态 Sni的路径。
2010-5-14 计算机算法设计与分析 5
0-1背包问题的状态空间树
? 下面是第三章 的 0-1背包问题的状态空间树：
SI0
S0
1
S10
S00
1
S01
0
S10
1
S11
0
S000
1
S001
0
S010
1
S011
0
S100
1
S101
0
S110
1
S111
? 对应第三章 的例子中的终止状态为 S011。
2010-5-14 计算机算法设计与分析 6
几种搜索方法
状态空间的搜索实际上是一种树 /DAG的搜索，
常用的方法有：
? 广度优先的搜索
? 深度优先的搜索
? 启发式的搜索
从初始状态开始，逐层地进行搜索。
从初始状态开始，逐个分枝地进行搜索。
从初始状态开始，每次选择最有可能达到终
止状态的结点进行搜索。
2010-5-14 计算机算法设计与分析 7
三种搜索的优劣之处
? 一般来说，三种搜索方法各有优劣之处：
? 广度优先搜索的优点是一定能找到解；缺点是
空间复杂性和时间复杂性都大。
? 深度优先搜索的优点是空间复杂性和时间复杂
性较小；缺点是不一定能找到解。
? 启发式搜索的是最好优先的搜索，优点是一般
来说能较快地找到解，即其时间复杂性更小；
缺点是需要设计一个评价函数，并且评价函数
的优劣决定了启发式搜索的优劣。
2010-5-14 计算机算法设计与分析 8
树搜索的一般形式
? SearchTree(Space T)//表 L用来存放待考察的结点
? {unfinish = true; L = T.initial;
? // unfinish表示搜索未结束，先将初始状态放入 L
? while (unfinish || L≠Φ) {
? a = L.first; //从 L中取出第一个元素
? if (a is goal) unfinish = false //若 a是终态则结束
? else Control-put-in(L,Sons(a));
? } //否则，将 a的儿子们 以某种控制方式 放入 L中
2010-5-14 计算机算法设计与分析 9
三种搜索的不同之处
树的三种搜索方法的不同就在于它们对
表 L使用了不同控制方式：
? L是一个队列
? L是一个栈
? L的元素按照
某方式排序
? 广度优先搜索
? 深度优先搜索
? 启发式搜索
? 其中，深度优先搜索就是回溯法。
2010-5-14 计算机算法设计与分析 10
递归回溯法的一般形式
? Try(s){
? 做挑选候选者的准备；
? while (未成功且还有候选者 ) {
? 挑选下一个候选者 next；
? if (next可接受 ) {
? 记录 next；
? if (满足成功条件 ) {成功并输出结果 }
? else Try(s+1);
? if (不成功 ) 删去 next的记录 ; }}
? return 成功与否 }
2010-5-14 计算机算法设计与分析 11
迭代回溯法的一般形式
? 先让我们回顾解空间搜索的一般形式：? SearchTree(Space T)//表 L用来存放待考察的结点
? {unfinish = true; L = T.initial;
? // unfinish表示搜索未结束，先将初始状态放入 L
? while (unfinish || L≠Φ) {
? a = L.first; //从 L中取出第一个元素
? if (a is goal) finish = false //若 a是终态则结束
? else Control-put-in(L,Sons(a));
? } //否则，将 a的儿子们 以某种控制方式 放入 L中
回溯法中表 L为栈，将初始状态压入栈中。
弹出栈顶元素
在通常求解问题时，
解是由逐个状态构
成的。因此，这里
还需要判断状态是
否可接受，并进行
纪录路径等工作。
如果 a可接收但未终
止，则要将 a的后继
压入栈中。如果要
抛弃状态 a,当 a是
最后一个儿子时，
还需要消除原有的
纪录甚至回溯一步。
2010-5-14 计算机算法设计与分析 12
如何判断最后一个儿子？
? 若只要遍历解空间树上的结点，那么将各个结
点按栈的方式控制便可实现深度为主的搜索。
? 但是在求解问题时，需要记录解的路径，在回
溯时还需要删除结点和修改相应的信息。
? 栈中的结点是分层次的，而现在没有区分它们
的层次。这就增加了回溯判断和操作的困难。
那么怎么办？? 采用一个简洁有效的方法：设计一个末
尾标记，每次压栈时，先压入末尾标记。
2010-5-14 计算机算法设计与分析 13
用末尾标记的迭代回溯
? Backtrack(Tree T) {
? unfinish = true; L.Push(T.root);
? while (unfinish || L≠Φ) {
? a = L.Pop( );
? if (a is the last mark) backastep( );
? if (a is good) {record(a);
? if (a is goal) {unfinish = false; output( );}
? else if (a has sons) L.Push-Sons(a)
? else move-off(a);}}}
若栈顶元素是
末尾标记，说
明这个路径已
经到头了，需
要回溯一步。
若 a是可以接
受的，则将 a
加入求解的路
径中 。
若 a是目标节
点，则结束搜
索并输出求解
的路径 。
若 a不是目标
节点且 a有后
即，则将 a的
后继压入栈
中。
这里的 L.Push-
Sons(a)要先压
入末尾标记，
然后再压入后
继结点。
若 不是目标
节点又没有
后继, 则将 a
从解的路径
中删除 。
2010-5-14 计算机算法设计与分析 14
不可接受的结点
? 破坏了解的相容条件的结点
? 超出了状态空间的范围，或者说不满足
约束条件，的结点；
? 评价值很差的结点，即已经知道不可能
获得解的结点；
? 已经存在于被考察的路径之中的结点，
这种结点会造成搜索的死循环 。
2010-5-14 计算机算法设计与分析 15
N后问题
? 要求在一个 n× n的棋盘上放置 n个皇后，使得
她们彼此不受攻击。
? 按照国际象棋的规则，一个皇后可以攻击与之
同一行或同一列或同一斜线上的任何棋子。
? 因此,N后问题等价于：要求在一个 n× n的棋
盘上放置 n个皇后，使得任意两个皇后不得在
同一行或同一列或同一斜线上。
2010-5-14 计算机算法设计与分析 16
用递归回溯法求 N后问题
? Try(s){
? 做挑选候选者的准备；
? while (未成功且还有候选者 ) {
? 挑选下一个候选者 next；
? if (next可接受 ) {
? 记录 next；
? if (满足成功条件 ) {成功并输出结果 }
? else Try(s+1);
? if (不成功 ) 删去 next的记录 ; }}
? return 成功与否 }
先回顾递归回溯法的一般形式,
2010-5-14 计算机算法设计与分析 17
用递归回溯法求 N后问题
? Try(s){
? 做挑选候选者的准备；
? while (未成功且还有候选者 ) {
? 挑选下一个候选者 next；
? if (next可接受 ) {
? 记录 next；
? if (满足成功条件 ) {成功并输出结果 }
? else Try(s+1);
? if (不成功 ) 删去 next的记录 ; }}
? return 成功与否 }
s为准备放置后的行数 候选者为 1到 n列。
j = 0; q = 0; 令列标记 j = 0； q表示未成功。
列数不到 n就还有候选者
!q && j < n ) {
列数加 1
j++;
各后都安全，便可接受
Safe(s,j)) {
记下该行后的位置 (列数 )
Record(s,j);
n行后都放完就成功了
(s = = n) {q = 1; output( );}
不成功，删
去后在该行
的位置。
(!q) Move-Off(s,j); }}}
q }
2010-5-14 计算机算法设计与分析 18
求解 N后问题中的数据表示
? 数组 B[n]表示棋盘。若 B[i]=j,1≤i,j≤n,表示
棋盘的第 i行第 j列上有皇后。
? 数组 C[j]=1表示第 j列上无皇后, 1≤j≤n。
? 数组 D[k]=1表示第 k条下行
(↘ )对角线上无皇后。
1
2
3
4
5
6
1 2 3 4 5 6
k = i + j, 2≤k≤2n。
这里，
2010-5-14 计算机算法设计与分析 19
求解 N后问题中的数据表示
? 数组 B[n]表示棋盘。若 B[i] = j,1≤i,j≤n,表
示棋盘的第 i行第 j列上有皇后。
? 数组 C[j] = 1表示第 j列上无皇后, 1≤j≤n。
? 数组 D[k] = 1表示第 k条下行
(↘ )对角线上无皇后。
k = i + j, 2≤k≤2n。
这里，
? 数组 U[k] = 1表示第 k条上行
(↗ )对角线上无皇后。 12
3
4
5
6
1 2 3 4 5 6k = i – j, –n+1≤k≤n–1。
这里，
2010-5-14 计算机算法设计与分析 20
求解 N后问题中的子程序
? Record(s,j) { k = s – j + n – 1;
B[s] = j; C[j] = 0; D[s + j – 1] = 0; U[k] = 0; }
? Move-Off(s,j) {k = s – j + n – 1;
B[s] = 0; C[j] = 1; D[s + j – 1] = 1; U[k] = 1; }
? Safe(s,j) {k = s – j + n – 1;
if (C[j] && U[k] && D[s + j – 1]) return true
else return false; }
2010-5-14 计算机算法设计与分析 21
求解 N后问题的主程序
? N-Queens( ) {
? int B[n + 1],C[n + 1],D[2n],U[2n];
? for (j = 1,j < n + 1; j++) {
? B[j] = 0; C[j] = 1;
? U[2j] = 1; U[2j – 1] = 1;
? D[2j] = 1; D[2j – 1] = 1;}
? try(1);
? output(B); }
将数组 B[n],
C[n],U[2n]
和 D[2n]都
赋予初值。
从第一行开始递归
2010-5-14 计算机算法设计与分析 22
N后问题的迭代程序
? 先看看迭代回溯法的一般形式：? Backtrack(Tree T) {
? unfinish = true; L.Push(T.root);
? while (unfinish || L≠Φ) {
? a = L.Pop( );
? if (a is the last mark) backastep( );
? if (a is good) {record(a);
? if (a is goal) {unfinish = false; output( );}
? else if (a has sons) L.Push-Sons(a)
? else move-off(a);}}}
迭代从第一行开始，
将第一行的 1~n列
和 0压入栈中，这
里 0作为末尾标记 。
i = 1; L.Push(1,2,…,n,0) ;
a是末尾标记则回溯。
(a == 0) backastep;
回溯需要
做什么？回溯需要退回一行，即 i–– ； 同时删除
该行的原纪录。{i––; a = B[i]; Move-Off(i,a); }
如果 safe(i,a)，
则放下后。
(Safe(i,a)) Record(i,a);
如果到了第 n
行，则成功。
(i == n)
当行 i < n时，则
必定有后继 。 无
需考虑此情况。
{i++; L.Pu h(1,2,…,n,0);}
}}}
2010-5-14 计算机算法设计与分析 23
N后问题的迭代程序
? Backtrack(Tree T) {
? unfinish = true; i = 1; L.Push(1,2,…,n) ;
? while (unfinish || L≠Φ) {
? a = L.Pop( );
? if (a == 0) {i– –; a = B[i]; Move-Off(i,a);}
? if (Safe(i,a)) {Record(i,a);
? if (i = = n) {unfinish = false; output(B);}
? else {i++; L.Push(1,2,…,n,0);}
? }}}
2010-5-14 计算机算法设计与分析 24
迭代回溯解 N后问题的主程序
? N-Queens(n) {
? int B[n + 1],C[n + 1],D[2n],U[2n];
? for (j = 1,j < n + 1; j++) {
? B[j] = 0; C[j] = 1;
? U[2j] = 1; U[2j – 1] = 1;
? D[2j] = 1; D[2j – 1] = 1;}
? Backtrack(n,B);
? }
2010-5-14 计算机算法设计与分析 25
N后问题的时间复杂性
? 如果只要找出 N后问题的一个解，那么这
是一个求路径的问题。
? 求路径：只需要找到一条路径便可以得
到解。设每个状态有 k个后继，其搜索树
为 K叉树，其结点总数为 kn+1–1,遍历的
时间为 O(kn),这里 n为找到解的路径长度。
? N后问题的路径深度为 n,可选择的后继
有 n个，所以时间复杂性为 O(nn)。
2010-5-14 计算机算法设计与分析 26
旅行售货员问题
? TSP,某售货员到若干城市去推销商品，已知
各城市之间的路程 (或旅费 )。他要选定一条路
线，经过每个城市一遍最后回到驻地的路线，
使得总的路程 (或总旅费 )最小。
? 设 G=(V,E)是一个带权图。图中各边的费用 (权
值 )为正。图中一条周游路线是包括 V中所有顶
点的回路。一条周游路线的费用是该路线上所
有边的费用之和。所谓旅行售货员问题就是要
在图 G中找出一条最小费用的周游路线。
2010-5-14 计算机算法设计与分析 27
? Try(s){
? 做挑选候选者的准备；
? while (未成功且还有候选者 ){
? 挑选下一个候选者 next；
? if (next可接受 ) {
? 记录 next；
? if (满足成功条件 ) {成功并输出结果 }
? else Try(s+1);
? if (不成功 ) 删去 next的记录 ; }}
? return 成功与否 }
线路上的第 s个结点 这里只需依次考
察 n–1个结点，即
for (i=2; i<=n; i++)
下一个候选就是 i。结点 i尚未在路线中且总耗费值不大。
考虑 TSP的递归回溯算法
就是将结点 i放入路
线中并修改耗费值
s == n
若新线路更好，就用
新线路取代老线路。
这里无所谓成功与否，
因为每一条周游路线
都要进行比较。
2010-5-14 计算机算法设计与分析 28
TSP的递归回溯算法
? Try(s){
? for (i = 2; i <= n; i++)
? if (Accept(i)) {
? Record(s,i)；
? if (s = = n)
? if (better) TakeNewPath( ) ;
? else Try(s+1);
? Move-off(s,i)}
? return }
2010-5-14 计算机算法设计与分析 29
求解 TSP的数据结构
? 用数组 C[n][n]存放个城市间的费用值。
? 用数组 P[n]记录已经找到的费用最小的周游路
线,C为其相应的费用,C初值为 ∞。
? 用数组 N[n]记录目前正在寻找的周游路线,NC
为其相应的费用；
? 如果 NC+C[N[n]][1]小于 C,则路线 N更佳，于
是 P[] = N[],Cost = NC+C[N[n]][1]。
? 如果结点 next不是 N中已有的结点，且 Cost大于
NC+C[N[i]][next],则结点 next是可接受的。
2010-5-14 计算机算法设计与分析 30
TSP的递归程序 Try
? Try(s){
? for (i = 2; i <= n; i++)
? if (Accept(i)) {
? Record(s,i)；
? if (s = = n)
? if (better) TakeNewPath( ) ;
? else Try(s+1);
? Move-off(s,i)}
? return }
(C–NC >C[N[s]][i] &&T[i]) {
数组 T[]表示结点 i尚未被选
(C >NC+C[ [s]][1]) TakeNewPath( );
2010-5-14 计算机算法设计与分析 31
Try中的子程序
? Record(s,i);
{NC = NC + C[N[s]][i]; T[i] = 0; N[s] = i; }
? Move-off(s,i);
{NC = NC – C[N[s]][i]; T[i] = 1; N[s] = 0;}
? TakeNewPath( ) {
? for (i=1; i<=n; i++) P[i] = N[i];
? C = NC + C[N[s]][1];}
2010-5-14 计算机算法设计与分析 32
递归回溯求 TSP的主程序
? TSP(n,C[n][n]) {
? for (i = 1; i <= n; i++)
? {N[i]=0; P[i] = 0; T[i] = 1}
? NC = 0； C = ∞; N[1]=1; T[1] = 0;
? Try(1);
? Output(P)；
? }
2010-5-14 计算机算法设计与分析 33
考虑 TSP的迭代程序
? 为了便于迭代程序中回溯的判断，我们
将城市结点编号为 1 ~ n,用编号 0作为末
尾的标记。
? 先回顾一下采用末尾标记的迭代回溯法：
2010-5-14 计算机算法设计与分析 34
考虑 TSP的迭代程序
? Backtrack(Tree T) {
? unfinish = true; L.Push(T.root);
? while (unfinish || L≠Φ) {
? a = L.Pop( );
? if (a is the last mark) backastep( );
? else if (a is good) {Record(a);
? if (a is goal) {unfinish = false; output( );}
? else if (a has sons) L.Push-Sons(a)
? else Move-off(a);}}}
要比较所有路径，无需此句。
L≠Φ ) {
初始化后压入第一个结点。
j = 1; N[j] = 1; L.Push-Sons(1
末尾标记为 0。
(a == 0) back step( );
删除第 j个结点，然后 j– –。
{Move-off(N[j–1],N[j]); j––;}
a不在路线中且新
增后的费用仍低。
T[a]&&C–NC>C[N[i]][a]){Record(N[j],a);
已经 n个结点且新
路线的费用更低。
这个判断不需要了。
(s = = n ) if (C >NC+C[a][1])
{TakeNewPath( ); Move-off(N[j],a);}}
els {j++; L.Push-Sons(a)}}}
2010-5-14 计算机算法设计与分析 35
TSP的迭代回溯
? Backtrack(n,C) {
? j = 1; N[j] = 1; L.Push-Sons(1);
? while (L≠Φ) { a = L.Pop( );
? if (a == 0) {Move-off(N[j–1],N[j]); j––;}
? else if (T[a] && C – NC > C[N[i]][a]) {
? Record(N[j],a)；
? if (s = = n ) if (C >NC+C[a][1])
? {TakeNewPath( ); Move-off(N[j],a);}}
? else {j++; L.Push-Sons(a)}}}
2010-5-14 计算机算法设计与分析 36
迭代回溯求 TSP的主程序
? TSP(n,C[n][n]) {
? for (i = 1; i <= n; i++)
? {N[i]=0; P[i] = 0; T[i] = 1}
? NC = 0； C = ∞; N[1]=1; T[1] = 0;
? Backtrack(n,C);
? Output(P)；
? }
2010-5-14 计算机算法设计与分析 37
求解 TSP的时间复杂性
? 显然 TSP是一个求排列的问题。
? 求排列：确定 n个元素的满足某种性质的
排列。其搜索树称为排列树，通常有 n!
个叶结点，因此遍历排列树需要时间为
O(n!)。
? 所以 TSP问题的时间复杂性为 O(n!)
2010-5-14 计算机算法设计与分析 38
用回溯法解 0-1背包问题
? 类似于旅行售货员问题，用一个数组 P[n]存放
目前取得的最优解，用变量 V表示其价值；再
用一个数组 N[n]来产生新的解，用变量 NV表示
其价值，用变量 W表示其重量 。 如果新解更优，
则替代原来的最优解，否则就丢弃新解。然后
回溯寻找下一个新解。
? 为此，我们先回顾一下回溯法的一般递归算法：
2010-5-14 计算机算法设计与分析 39
用回溯法解 0-1背包问题
? Try(s){
? 做挑选候选者的准备；
? while (未成功且还有候选者 ){
? 挑选下一个候选者 next；
? if (next可接受 ) {
? 记录 next；
? if (满足成功条件 ) {成功并输出结果 }
? else Try(s+1);
? if (不成功 ) 删去 next的记录 ; }}
? return 成功与否 }
考察的第 s个物品
只需考两种情况，
选或不选，即
for (i=0; i<2; i++)
下个候选就是 i。物体 s可放入背包中 ；
将 s放入背包中并
修改权重与容量 ；
s = = n
这里无论成功与
否都要继续考察,记录” 的
逆操作
2010-5-14 计算机算法设计与分析 40
用回溯法解 0-1背包问题
? Try(s){
? for (i = 0; i < 2; i++)
? if (Accept(i)) {
? Record(s,i)；
? if (s = = n) {if ( better ) TakeNewChoice( );}
? else Try(s+1);
? Move-off(s,i);}
? return }
(W+w[s]*i <= C) {
(NV > V)
2010-5-14 计算机算法设计与分析 41
0-1背包问题中的几个子程序
? Record(s,i){ N[s] = i; W=W + w[s]*i;
NV = NV + v[s]*i;}
? Move-off(s,i){N[s] = 0; W = W – w[s]*i;
NV = NV – v[s]*i;}
? TakeNewChoice( ) {
? for (i=1; i<=n; i++) {
? P[i] = N[i]; V = NV;}}
2010-5-14 计算机算法设计与分析 42
0-1背包问题的主程序
? Bag(n,C,w[n],v[n]) {
? for (i=1; i<=n; i++)
? {N[i]=0; P[i] = 0; T[i] = 1;}
? NV = 0,W = 0; V = 0;
? Try(1);
? Output(P); }
2010-5-14 计算机算法设计与分析 43
考虑 0-1背包问题的迭代实现
? 先看看回溯法的一般的迭代形式：? Backtrack(Tree T) {
? unfinish = true; L.Push(T.root);
? while (unfinish || L≠Φ) {
? a = L.Pop( );
? if (a is the last mark) backastep( );
? else if (a is good) {Record(a);
? if (a is goal) {unfinish = false; output( );}
? else if (a has sons) L.Push-Sons(a)
? else Move-off(a);}}}
要比较所有组合，无需此句。
(L≠Φ) { 从物品 1开始，压入
物品 1的两种选择。
j = 1; L.Push(–1,0,1);
用 –1作末尾标记 。
== –1) backastep( );
回溯：删除相关记
录，并退回一步。
{Move-off(j,N[j]); j––;}
只要容量没有超过就可以选
(W+w[j]*a <= C) {Record(j,a);
j = n 。
( j == n )
若新的组合更好，
则选取新组合 。
{if (V < NV) TakeNewChoice( );}
只要没选购就可继续
选，故必定有后继 。
else {j++; L.Push(–1,0,1);}
}}}
2010-5-14 计算机算法设计与分析 44
0-1背包问题的迭代实现
? Backtrack(Tree T) {
? j = 1; L.Push(–1,0,1);
? while (L≠Φ) {
? a = L.Pop( );
? if (a == –1) {Move-off(j,N[j]); j– –;}
? else if (W+w[j]*a <= C) {Record(a);
? if (j == n ) {if (V < NV) TakeNewChoice( );}
? else {j++; L.Push(–1,0,1);}
? }}}
2010-5-14 计算机算法设计与分析 45
0-1背包问题的时间复杂性
? 显然 0-1背包问题是一个求子集的问题。
? 求子集：从 n个元素的集合 S中找出满足
某个性质子集。其搜索树称为子集树，
是棵二叉树，通常有 2n个叶结点，遍历
的时间为 O(2n) 。
? 0-1背包问题的时间复杂性为 O(2n)。
2010-5-14 计算机算法设计与分析 46
求排列、求子集、求路径
? 求排列：确定 n个元素的满足某种性质的排列。
其搜索树称为排列树，通常有 n!个叶结点，因
此遍历排列树需要时间为 O(n!)。
? 求子集：从 n个元素的集合 S中找出满足某个性
质子集。其搜索树称为子集树，是棵二叉树，
通常有 2n个叶结点，遍历的时间为 O(2n) 。
? 求路径：只需要找到一条路径便可以得到解。
设每个状态有 k个后继，其搜索树为 K叉树，其
结点总数为 kn+1–1,遍历的时间为 O(kn),这里 n
为找到解的路径长度。
2010-5-14 计算机算法设计与分析 47
构造一个数环
? 请设计一个算法生成这
样的一个数环：此数环
由 2n个 0和 1组成，使得
2n个 n位的二进制数中
的每一个数在数环中恰
出现一次。如右图就是
23个 0和 1组成的环。
0
0
0
1
0
1
1
1
2010-5-14 计算机算法设计与分析 48
用回溯法构造数环
? 自然想到用回溯法来构造数环，那就是：
? 1、先放下 n个 0，即数 0；
? 2、然后，在其后添上一个数字 (0或者 1)，
使得产生的数不重复。
? 3、若成功，就继续像 2中那样添加后面
的数字。若添 0或 1都不行，就回溯一步。
? 4、重复 2,3，直到 2n个数字全部填完。
2010-5-14 计算机算法设计与分析 49
用递归回溯法构造此环
先回顾回溯法的递归实现：
? Try(s){
? 做挑选候选者的准备；
? while (未成功且还有候选者 ) {
? 挑选下一个候选者 next；
? if (next可接受 ) {
? 记录 next；
? if (未完成 ) {
? Try(s+1);
? if (不成功 ) 删去 next的记录 }}}
? return 成功与否 }
2010-5-14 计算机算法设计与分析 50
用递归回溯法构造此环
? Try(s){
? 做挑选候选者的准备；
? while (未成功且还有候选者 ) {
? 挑选下一个候选者 next；
? if (next可接受 ) {
? 记录 next；
? if (未完成 ) {
? Try(s+1);
? if (不成功 ) 删去 next的记录 }}}
? return 成功与否 }
j = 0; q = 0;
(j < 2 && !q) {
j++;
–1;
(accept(s,j)) {
Record(s,j);
(s < 2n) {
if !q) Move-Off(s,j); }}}
q }
2010-5-14 计算机算法设计与分析 51
如何构造 accept(s,j)
? 在第 s步放下数字 j是可接受的，当且仅当
新产生的数与已经产生的数不重复。
? 怎样知道新产生的数不重复呢？一种方法就是用新产生的 n位二进制数去
和已经产生的 n位二进制数逐个比较，看
是否有完全匹配的。如果没有，就是不
重复的。然而，这样做的时间复杂性是
很高的。
另一种方法是用一个布尔数组表示已经
存在的 n位二进制数，对新的 n位二进制
数只要查看该布尔数组便可以知道。如
果没有，就是不重复的，并登记新数。
显然这样做的时间复杂性要低得多。
2010-5-14 计算机算法设计与分析 52
构造此环的数据结构
? 首先，需要一个数据结构来存放所构造
的环。 一维数组 Circle[2n]。
? 其次，需要一个登记已经产生的 n位二进
制数的一维数组 Exist[2n]。
若 Exist[ni] = 1,则数 ni已经存在；
若 Exist[ni] = 0,则数 ni尚未产生。
? 于是,accept(s,j)为查看数组 Exist，即，
accept(s,j)为真当且仅当 Exist[ni] = 0,这
里 ni是第 s个符号填上数字 j所产生的数。
2010-5-14 计算机算法设计与分析 53
如何由数 mi推出数 mi+1
? 设前次产生的 n位二进制数为 mi,本次产
生的 n位二进制数为 mi+1，那么
a1 a2 ?? an
mi
j
mi+1
mi+1是 mi左移
一位后添加
数字 j。
mi+1= (2* mi + j ) mod 2n 。
? 初始化时，令 m0 = 0。
2010-5-14 计算机算法设计与分析 54
构造此环的递归回溯程序
? Try(s){
? j = 0; q = 0;
? while (j < 2 && !q) {
? j++;
? if (accept(s,j)) {
? Record(s,j);
? if (s < 2n) {
? Try(s+1);
? if (!q) Move-Off(s,j); }}}
? return q }
为了便于推算产生的
新数，前次产生的数
最好是作为参数传递。
,m) 在判断 accept之前应
该计算出填上 j以后
所产生的新数。
new = (2* m + j) mod max; accept(s,j)即为Exist[new] = 0。
!Exist[new]) {
Record(s,j)为登记数组
Circle[s]和 Exist[new]。
Cir le[s] = j Exist[new] = 1;
max) {
进行下一步
递归时,new
作为参数传
递下去。,new);
Move-Off(s,j)
为删除数组
Circle[s]和
Exist[new]。{Circle[s] = 0; Exist[new] = 0;}}}
2010-5-14 计算机算法设计与分析 55
构造此环的主程序
? Make-circle(n){
? int i,s,max = 2n;
? int Circle[max],Exist[max];
? for (i = 0,i < max; i++) Exist[i] = 0;
? for (i = 0,i < n; i++) Circle[i] = 0;
? Exist[0] = 1; s = n + 1；
? Try(s,0);}
2010-5-14 计算机算法设计与分析 56
构造此环的时间复杂性
? 显然此环的构造是一个求路径的问题。
? 求路径：只需要找到一条路径便可以得
到解。设每个状态有 k个后继，其搜索树
为 K叉树，结点总数为 km+1–1,遍历的时
间为 O(km),这里 m为找到解的路径长度。
? 构造环的路径的深度为 m = 2n,后继只有
2个，因此其时间复杂性为 O(2m)。
? 不过，构造此环可以不需要回溯！
2010-5-14 计算机算法设计与分析 57
构造此环的无回溯算法
? 这个环其实可以用一种不需要回溯的算
法来构造，而且这个算法很简单：
? 1、先放下 n个 0，即数 0；
? 2、每次先放数字 1，如果不行，即产生
的数重复，就改放数字 0。 (先 1原则 )
? 3、反复执行 2，直至把 2n个数字全部放
完即可。
2010-5-14 计算机算法设计与分析 58
构造此环的无回溯算法
? MakeCircle(int n){
? int s,j,MAX = 2n;
? int Circle[MAX],Exist[MAX];
? for (j = 0; j < MAX; j++)
? {Circle[j] = 0; Exist[j] = 0;}
? j = n; s = 0; Exist[s] = 1;
? while (j < MAX) {
? s = (2*s) mod MAX；
? if (!Exist[s + 1]) {Circle[j] = 1; s = s + 1;}
? Exist[s] = 1; j = j + 1; }}
先将所有数
字都填为 0
第一个
数为 0。
若添 1是新数，则
填 1；否则仍是 0。
2010-5-14 计算机算法设计与分析 59
证明无回溯算法的正确性
? 我们可以证明这个无回溯的算法是正确
的。为此我们需要证明两点：
? 1、算法生成了 2n个不重复的 n位二进制
数，即每个 n位二进制数恰出现一次。
? 2、这样生成的 2n个 n位二进制数恰好构
成了一个环。
2010-5-14 计算机算法设计与分析 60
2n个数中无重复
? 用归纳法来证明这 2n个数中无重复：
? 归纳基础：当 j = 0时,s0 = 0,序列无重复数。
? 归纳假设：设当 j = k时，序列 s0,s1,……,s k没
有重复的数。
? 归纳证明：当 j = k + 1时，由算法可知,sk+1为：
? 1、填上一个数字 1所产生的，由算法中的判断
可知，生成的数 sk+1为新数，该序列没有重复。
? 2、填上一个数字 0所产生的，我们用反证法来
证明 sk+1为新数。
2010-5-14 计算机算法设计与分析 61
反证法证明填 0是新数
? 假设填 0生成的 sk+1为重复数。令 sk+1为 w0,这
里 w为 n–1位二进制符号串。
? 由算法可知 w1也重复。 ∴ 原序列中必有两个子
序列 ?1= w1,?2 = w0。 且 ?1的位置在前。
先 1原则
?1 ?2
w 1 w 0 w 10
? ∴ 原序列中必有三个位置都大于 1的子串 w,即
三个子串 w的前面都至少有一个符号。
a b c
? ∴ 原序列中必有三个子串分别为 aw,bw和 cw。
? 又 ∵ a,b和 c的取值为 0或 1,∴ 三个子串中必
有重复。即原序列有重复。矛盾。证毕。
2010-5-14 计算机算法设计与分析 62
证明构成环
? 要证明算法生成的 2n个数构成环，只需要证明
最后一个数 s = 10…0 = 1 w,w为 n–1个 0。2n
证明：当 2n个数全部生成后，若继续在后面填
上一个数字，则无论是填 1还是填 0，所生成的
第 2n+1个 n位二进制数都必定是个重复的数。
? 由此可知在原序列中必定在三个位置上有相同
的子串 w。 若不然，第 2n+1个数不是重复的。
? 然而原序列中没有重复数。
? 这只能是第一个 w的位置为 1，即在最前面。
? 最前面是 n个 0，所以 w为全 0的符号串。证毕。
2010-5-14 计算机算法设计与分析 63
受到的启迪
? 显然无回溯算法的复杂性只有 O(m),m = 2n。
即回溯算法复杂性是指数函数，而无回溯算法
的仅是 1阶的。后者的效率要高得多！
? 由此我们看到，一个问题除了通用的方法外，
还可能存在着其特有的高效率的算法。
? 从这个算法的正确性证明中，我们看到，如果
对一个算法进行理论上的推证，不仅能够使我
们确信算法是正确的，而且还可以使我们对问
题有本质上的深入认识。
2010-5-14 计算机算法设计与分析 64
回溯法小结
? 回溯法是一种通用的算法，实为深度优先的搜
索方法。
? 回溯法可以 递归实现,也可以 迭代实现 。
? 回溯法通常求解三类问题：
? (1)求排列：时间复杂性为 O(f(n)n!)；
? (2)求子集：时间复杂性为 O(f(n)2n)；
? (3)求路径, 时间复杂性为 O(f(n)kn)。
? 这里 f(n)为处理一个结点的时间复杂性。
