当前位置：文档之家 › 第五章----回溯法--基本概念--n后问题只是课件

第五章----回溯法--基本概念--n后问题只是课件

  • 格式：ppt
  • 大小：319.50 KB
  • 文档页数：9

下载文档原格式

  / 9

合集下载

第5章-回溯法-New剖析

第5章-回溯法-New剖析

第5章 回溯法
回溯法的基本思想
回溯法是带优化的穷举法。 回溯法的基本思想：在一棵含有问题全部可 能解的状态空间树上进行深度优先搜索，解为叶 子结点。搜索过程中，每到达一个结点时，则判 断该结点为根的子树是否含有问题的解，如果可 以确定该子树中不含有问题的解，则放弃对该子 树的搜索，退回到上层父结点，继续下一步深度 优先搜索过程。 在回溯法中，并不是先构造出整棵状态空间 树，再进行搜索，而是在搜索过程中逐步构造出 状态空间树，即边搜索，边构造。
}
遍历排列树需要O(n!)计算时间
第5章 回溯法
八皇后问题
是一个古老而著名的问题。该问题是十九 世纪著名的数学家高斯1850年提出。 在8X8格的国际象棋上摆放八个皇后，使 其不能互相攻击，即任意两个皇后都不能 处于同一行、同一列或同一斜线上，问有 多少种摆法。 高斯认为有76种方案。1854年在柏林的 象棋杂志上不同的作者发表了40种不同的 解，后来有人用图论的方法解出92种结果。
第5章 回溯法
第5章 回溯法
引入问题
回溯是重要的算法之一 要求找到一组解，或要求找到一个满足某些限制 的最优解。 ->通过彻底的搜索方法来解决。
*彻底搜索的运算量很大，有时大到计算机承受 不了的程度。
*彻底的搜索，以进行大量的比较、舍弃、运算 时间为代价。因此，用穷举法解某些实际问题是不 现实的. ->使用回溯法可以大大减少实际的搜索。例如，迷 宫问题，八皇后问题，骑士周游世界问题。
第5章 回溯法
N皇后问题
[问题描述] 在Ｎ*Ｎ的棋盘上，放置Ｎ个皇后，要求每 一横行，每一列，每一对角线上均只能放置一个皇后， 求可能的方案及方案数。
问题的状态即棋盘的布局状态，状态空间树的根为空 棋盘，每个布局的下一步可能布局为该布局结点的子 结点；

回溯法_ppt课件

回溯法_ppt课件
//h(i)表示在当前扩展节点处x[t]的第i个可选值
实 现 递 归
} }
if (Constraint(t) &&Bound(t) ) { if (Solution(t)) Output(x); else t ++; } else t --;
if (Constraint(t) &&Bound(t) ) { if (Solution(t)) Output(x); else t ++; } else t --; 分析：
算法设计与分析 >回溯法
5、回溯法解题步骤: 1).针对所给问题,定义问题的解空间 2).确定解空间结构. 3).以深度优先方式搜索解空间.
算法模式 Procedure BACKTRACK(n)； {k:=l； repeat if TK (x1,x2,...xK-1 )中的值未取遍 then { xK:＝TK (x1，x2，..., x K-1 )中未取过的一个值； if BK (x1, x2, ..., x K) then //状态结点(x1,...xk)被激活 if k＝n then output(x1, x2, ..., xk) //输出度优先 e1se k:＝k-l； //回溯 until k＝0； end；{BACKTRACK}
if (Constraint(t)&&Bound(t) ) Backtrack(t + 1)； if语句含义：Constraint(t)和Bound(t)表示当前扩展 节点处的约束函数和限界函数。 Constraint(t): 返回值为true时，在当前扩展节点处 x[1:t]的取值问题的约束条件，否则不满足问题的约束条 件，可剪去相应的子树 Bound(t): 返回的值为true时，在当前扩展节点处 x[1：t]的取值为时目标函数越界，还需由Backtrack(t+1) 对其相应的子树做进一步搜索。否则，当前扩展节点处 x[1：t]的取值是目标函数越界，可剪去相应的子树 for循环作用：搜索遍当前扩展的所有未搜索过的 子树。 递归出口：Backtrack(t)执行完毕，返回t-1层继续 执行，对还没有测试过的x[t-1]的值继续搜索。当t=1时， 若以测试完x[1]的所有可选值，外层调用就全部结束。

第5章回溯法PPT课件

第5章回溯法PPT课件

二、回溯的一般描述
一旦某个j元组（x1，x2，…，xj）违反D中仅涉及 x1，x2，…，xj 的一个约束，就可以肯定，以（x1， x2，…，xj）为前缀的任何n元组
（x1，x2，…，xj，xj+1，…，xn）都不会是问题P 的解。
三、回溯的一般步骤
回溯法正是针对这类问题，利用这类问题的 上述性质而提出来的比枚举法效率更高的算 法。
由于这是第一次用计算机证明数学定理，所以哈肯 和阿佩尔的工作，不仅是解决了一个难题，而且从 根本上拓展了人们对“证明”的理解，引发了数学 家从数学及哲学方面对“证明”的思考。
实例—n皇后问题
在一个n×n的棋盘上放置n个国际象棋中 的皇后，要求所有的皇后之间都不形成攻 击。请你给出所有可能的排布方案数。
n
4
5
6
7
8
总数
2
10
4
40
92
n皇后问题
对于n皇后问题而言，我们很难找出很合适的方法 来快速的得到解，因此，我们只能采取最基本的枚 举法来求解。
但我们知道，在n×n的棋盘上放置n个棋子的所有
回溯算法（一）
什么是回溯
入口回溯
▪迷宫游戏
回溯
➢什么是回溯法
回溯
▪回溯法是一个既带
有系统性又带有跳跃
性的的搜索算法
回溯
▪回溯法是以深度优先的方式系统地搜索问题 出口 的解, 它适用于解一些组合数较大的问题。
回溯(Trackback)是什么？
为什么回溯？
怎样回溯？
What
Why
How
一、回溯的概念
解问题P的最朴素的方法就是枚举法，即对E 中的所有n元组逐一地检测其是否满足D的全 部约束，显然，其计算量是相当大的。

回溯PPT课件

回溯PPT课件
第 5 章 回溯
➢教学要求
➢ 了解回溯算法的概念与回溯设计要领 ➢ 掌握应用回溯算法求解桥本分数式、素数环、
数码串珠以及情侣拍照等典型案例
➢本章重点
➢ 理解回溯法 “向前走，碰壁回头”的实现
5.1 回溯概述
1. 回溯的概念
(1) 回溯法（Backtracking method）有“通用解题法”之 美称，是一种比枚举“聪明”的效率更高的搜索技术。
void iterativeBacktrack () {
int t=1; while (t>0) {
if (f(n,t)<=g(n,t)) for (int i=f(n,t);i<=g(n,t);i++) { x[t]=h(i); if (constraint(t)&&bound(t)) { if (solution(t)) output(x); else t++;} }
宽度优先的问题状态生成法：在一个扩展结点变成死结 点之前，它一直是扩展结点
回溯法：为了避免生成那些不可能产生最佳解的问题状 态，要不断地利用限界函数(bounding function)来处 死那些实际上不可能产生所需解的活结点，以减少问题 的计算量。具有限界函数的深度优先生成法称为回溯法8
子集树与排列树
从解的角度理解，回溯法将问题的候选解按某种顺序进行枚举和 检验。当发现当前候选解不可能是解时，就选择下一个候选解。 在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回 溯。若当前候选解除了不满足问题规模要求外，满足所有其他要 求时，继续扩大当前候选解的规模，并继续试探。如果当前候选 解满足包括问题规模在内的所有要求时，该候选解就是问题的一 个解。

第5章 回溯法

第5章 回溯法

O(h(n)!)内存空间。
子集树
排列树
递归回溯
回溯法
南京邮电大学 通信与信息工程学院
迭代回溯
课件制作：王金元
递归回溯
回溯法对解空间作深度优先搜oid backtrack (int t) {
递归深度>n，算法搜索 到叶结点，输出可行解x
h(i)表示当前扩 展结点处x(t)的
Jn … J2 J1
南京邮电大学 通信与信息工程学院
机器1
机器2
课件制作：王金元
例子
tji 作业1 作业2 作业3
机器1 2 3 2
机器2 1 1 3
以1,2,3为例: 作业1在机器1上完成的时间为2,
在机器2上完成的时间为3 作业2在机器1上完成的时间为5,
在机器2上完成的时间为6 作业3在机器1上完成的时间为7,
} 南京邮电大学 通信与信息工程学院
课件制作：王金元
5.6. 批处理作业调度
给定n个作业的集合{J1,J2,…,Jn}。每个作业必须先由机器 1处理，然后由机器2处理。作业Ji需要机器j的处理时间为 tji。对于一个确定的作业调度，设Fji是作业i在机器j上完 成处理的时间。所有作业在机器2上完成处理的时间和称为 该作业调度的完成时间和。问题要求对于给定的n个作业， 制定最佳作业调度方案，使其完成时间和达到最小。
解空间：排列树
void Flowshop::Backtrack(int i)
{ if (i > n) {
搜索到叶节点，更新最优值
for (int j = 1; j <= n; j++)
bestx[j] = x[j];
bestf = f; } else

算法设计与分析课件--回溯法-n皇后问题

算法设计与分析课件--回溯法-n皇后问题

8
5.5 n皇后问题
对于n皇后问题,搜索树有1+n+n2+…+nn个结点。 1+n+n2+…+nn= (nn+1 -1)/(n-1) <= (nn+1)/(n/2) = 2nn(n>=2) 在每个结点处，要判断该位置的皇后是否与已经放置的皇后相 互攻击，最多要看3n个位置(沿列的方向、主与副对角线方向)是 否已有皇后，故n皇后问题的该算法最坏时间复杂度为 O(3n*2nn)=O(nn+1),这是个粗略的估计。
1个皇后所在的列，即仅有n-i+1个位置可供选择。令 S={1,2,…,n}，则xi∈S-{x1,x2,…,xi-1}。显然，满足显式约束的n 元组共有n!种，它构成n皇后问题的解空间。 排列树
10
5.5 n皇后问题
n皇后问题的分析： • 解空间树 – 排列树。这里n=4。
11
5.5 n皇后问题
9
5.5 n皇后问题
n皇后问题的分析（二）：
✓ 问题解的形式：表示为n元组(x1, x2,…, xn)的形式，其中xi(i=1, 2,…, n)表示第i个皇后放置在第i行第xi列；
✓ 显式约束：n个皇后不同行且不同列； ✓ 隐式约束：n个皇后不在正反对角线上； ✓ 解空间：根据显式约束，第i(i=1,2,…,n)个皇后不能放置在前i-
if t > n then
OUTPUT(x);
else
for i 1 to n do
x[t] i;
//第t个皇后放到第i列，不去判断列是否冲突
if PLACE(t) then
BACKTRACK-NQUEEN1-REC(t+1);

计算机算法设计与分析第5章 回溯算法PPT课件

计算机算法设计与分析第5章 回溯算法PPT课件
注意：同一个问题可以有多种表示，有些 表示方法更简单，所需表示的状态空间更 小（存储量少，搜索方法简单）。
22.09.2020
15
5.1.1 问题的解空间
为了用回溯法求解一个具有n个输入的问题，一 般情况下，将其可能解表示为满足某个约束条 件的等长向量X=(x1, x2, …, xn)，其中分量xi (1≤i≤n) 的取值范围是某个有限集合Si={ai1, ai2, …, airi}， 所有可能的解向量构成了问题的解空间。
22.09.2020
2
提纲
一、回溯法的算法框架 二、装载问题 三、n后问题 四、0-1背包问题 五、最大团问题 六、图的m着色问题 七、旅行售货员问题
22.09.2020
3
提纲
一、回溯法的算法框架 二、装载问题 三、n后问题 四、0-1背包问题 五、最大团问题 六、图的m着色问题 七、旅行售货员问题
17
2 旅行售货员问题
问题描述：某售货员 要到若干城市去推销 商品，一直各城市之 间的路程，他要选定 一条从驻地出发，经 过每个城市一遍，最 后回到住地的路线， 使总的路程最短。
(a) 二维搜索空间无解
(b) 三维搜索空间的解
错误的解空间将不能搜索到正确答案！
22.09.2020
13
5.1.1 问题的解空间
对于任何一个问题，可能解的表示方式和它相应的 解释隐含了解空间及其大小。
例如，对于有n个物品的0/1背包问题，其可能解的 表示方式可以有以下两种：
（1）可能解由一个不等长向量组成，当物品i(1≤i≤n)装入 背包时，解向量中包含分量i，否则，解向量中不包含分 量i，当n=3时，其解空间是：
计算机算法设计与分析
Design and Analysis of Computer Algorithms

第五章 回溯法

第五章 回溯法

• Cr=C=30，V=0
C为容量，Cr为剩余空间，V为价值。 • A为唯一活结点，也是当前扩展结点。
H D 1 0 I 1
1 B 0 E 1 0 J K
A
0 C 1 F 1 0 L M N 0 G 1 0 O
5.1 回溯法的算法框架
• n=3, C=30, w={16,15,15}, v={45,25,25}
理论上
寻找问题的解的一种可靠的方法是首先列出所有候选解，然后依次检查每一个， 在检查完所有或部分候选解后，即可找到所需要的解。
但是
当候选解数量有限并且通过检查所有或部分候选解能够得到所需解时，上述方
法是可行的。
若候选解的数量非常大（指数级，大数阶乘），即便采用最快的计算机也只能 解决规模很小的问题。
显约束
对分量xi的取值限定。
隐约束 为满足问题的解而对不同分量之间施加的约束。
5.1 回溯法的算法框架
解空间（Solution Space）
对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该 实例的一个解空间。 注意：同一问题可有多种表示，有些表示更简单，所需状态空间更小（存储 量少，搜索方法简单）。
回溯法引言
以深度优先的方式系统地搜索问题的解的算法称为回溯法 使用场合
对于许多问题，当需要找出它的解的集合或者要求回答什么解是满足某些
约束条件的最佳解时，往往要使用回溯法。 这种方法适用于解一些组合数相当大的问题，具有“通用解题法”之称。 回溯法的基本做法 是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。
一个正在产生儿子的结点称为扩展结点
活结点（L-结点,Live Node）
一个自身已生成但其儿子还没有全部生成的节点称做活结点

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

第五章 回溯法1--基本概念--n后问题
1 6 4 3 20 4 3 30 5 A A 2 10 2 1
B
3 4
C
4 G G 3 M M 2 H H 4 N N
D D
4 26>25 2 I I 3 P P 2 J J
E
3
图1 四个顶点的带权图
F
4 L L 59
K
2 Q Q
O
60+6>59 25
第五章 回溯法
19+6=25 29+30>25
活结点 当前扩展结点 死结点 D B 1 A
0 1 F 0
K
45
1
0
E
C 0 G 0 1 N
25
死结点 1
1
H
0
I
1
J
0 O
0
4
L
50
M
25
图5-２ 在0-1背包问题的解空间树上搜索最优解
第五章 回溯法
例2：旅行售货员问题：某售货员要到若干城市推销商 品，已知各城市间的路程（或旅费）。他要选一条从 驻地出发，经过每个城市一遍，最后回到驻地的路线 使总的路程（总的旅费）最小。
第五章 回溯法 2
2. 解空间树
通常把解空间组织成解空间树。 例如：对于n=3时的0-1背包问题，其解空间用一 棵完全二叉树表示，如下图所示。
1
A
0
B
1 0 1
C
0
D 1 H
0 1
E
0
F
1 0 1
G
0
I
J
K
L
M
N
O
0-1背包问题的解空间树
第五章 回溯法
3
3. 搜索解空间树的过程

回溯法ppt课件

回溯法ppt课件
分析：
可能解由一个等长向量（x1, x2, …, xn）组成， 其中
xi＝1(1≤i≤n)表示物品i装入背包 xi＝0(1≤i≤n)表示物品i没有装入背包
如：
当n＝3时，其解空间是：
{ (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)}
第5章 回溯法
学习要点
5.1 回溯法概述 5.2 回溯法的典型示例 5.3 回溯法的效率分析 本章小结
1
5.1 回溯法概述
5.1.1 问题的解空间 问题的解空间 两类典型的解空间
5.1.2 回溯法的基本思想 回溯法的基本思想 算法的框架 例：排列与组合 小结
15
排列树
分析
求赋权图G的具有最小权的Hamilton圈1
1解空间30：
2
2 34
64
5 10
3 42 4 2 3
3
4
20
4
34
23
2
当起点1固定时，上图有3!个周游路线（排列问题）
16
回溯法的基本思想
回溯法
回溯法是一种选优搜索法，按选优条件向前搜 索，以达到目标。
但当探索到某一步时，发现原先选择并不优或 达不到目标，就退回一步重新选择，这种走不 通就退回再走的技术为回溯法，而满足回溯条 件的某个状态的点称为“回溯点”。
若(x1, x2,… xi xi+1)满足约束条件, 则继续添加 xi+2 ；
若所有可能的xi+1 si+1均不满足约束条件,则去 掉xi , 回溯到(x1, x2,… xi-1), 添加尚未考虑过的xi；

[计算机软件及应用]第5章算法分析回溯法ppt课件

[计算机软件及应用]第5章算法分析回溯法ppt课件

• template<typename Type>
• void Loading<Type>::Backtrack(int i) //搜索第i层结点
•{
Байду номын сангаас
• if(i>n) //到达叶结点
•{
•
if(cw>bestw)
•
bestw=cw;
•
return;
•}
• if(cw+w[i]<=c) //进入左子树，x[i]=1
•{
•
cw+=w[i];
•
Backtrack(i+1); //继续搜索下一层
•
cw-=w[i]; //退出左子树
•}
• Backtrack(i+1); //进入右子树，x[i]=0
•}
template<typename Type> Type MaxLoading(Type w[],Type c,int n) //前往最优载分
A
1
0
B
1
0
C
1
0
D
1
0
E
1
0
F
1
0
G
1
0
H
I
J
K
L
M
N
O
• template<typename Type> • class Loading •{ • template<typename T> • friend T MaxLoading(T [],T,int);
• private: • void Backtrack(int i); • int n; //集装箱数 • Type *w; //集装箱分量数组 • Type c; //第1艘轮船的载分量 • Type cw; //当前载分量 • Type bestw; //当前最优载分量 • };

第5章回溯法(YZW)

第5章回溯法(YZW)
搜索过程直到找到问题的解或根结点变成死结点为止。
示例：n后问题
问题描述： 在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际 象棋的规则，皇后可以攻击与之处在同一行或同一列或同 一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n 个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。
1
1
2
3 4
2
例: 4-皇后问题
1 结点2的所有儿子表示的都是 x1= 2 x1=1 不可能导致答案的棋盘格局, 因 此结点2也被杀死; 再回溯到结 18 2 点1生成结点18, 路径变为(2) x2= 4 x2= 1 x2= 2 结点18的儿子结点19、 x2= 3 x2= 3 结点24被杀死, 应回溯 24 13 19 8 3 1 x3=2 kill kill kill x3=4 2 x3=2 x3=3 1 9 kill 1 2 11 14 kill x4=3 15 kill 16 kill
用约束函数在扩展结点处剪去不满足约束的
子树即：导致不可行解的结点； 用限界函数剪去得不到最优解的子树。即： 导致非最优解的结点。 几个名词
扩展结点:一个正在产生儿子的结点称为扩展结点 活结点:一个自身已生成但其儿子还没有全部生成的节点
称做活结点 死结点:一个所有儿子已经产生的结点称做死结点 搜索树：搜索过程中动态形成的树
1 2 3 4 5 Q Q Q Q Q Q
6 7 8
Q
Q 1 2 3 4 5 6 7 8
定义问题的解空间 解的形式：(x1, x2, … , xn) xi的取值范围：xi=1,2, … ,n 组织解空间 满n叉树，树的深度为n 搜索解空间 约束条件：不同列且不处于同一正、反对 角线上：|i-j||xi-xj| 限界条件：(×) 搜索过程（以4皇后问题为例）

回溯法 ppt课件

回溯法 ppt课件

回溯法举例：
[旅行商问题] 在这个问题中 ，给出一个n 顶点网络（有向 或无向） ，要求找出一个包含所有n 个顶点的具有最小耗 费的环路 。任何一个包含网络中所有n 个顶点的环路被称 作一个旅行（t o u r ）。在旅行商问题中 ，要设法找到一 条最小耗费的旅行。 [分析]图给出了一个四顶点网络 。在这个网络中 ，一些旅
Bound(t) : 返回的值为true时 ， 在当前扩展节点处 x[1： t]的取值为时 目标函数越界 ， 还需由Backtrack(t+1) 对其相应的子树做进一步搜索 。否则 ， 当前扩展节点处 x[1： t]的取值是目标函数越界 ，可剪去相应的子树
for循环作用： 搜索遍当前扩展的所有未搜索过的 子树。
si+1均不满足约束条件,则去掉xi , 回溯到(x 1 , x 2 , … xi-1), 添加尚 未考虑过的xi , 如此反复进行,直到(x1 , x2 , … xk) k n满足所有的 约束条件或证明无解.
E= { (x1 , x2 , … xn), xi si , si为有限集 }称为问题的解空间.
5. 1 回溯法基本思想
穷举法技术建议我们先生成所有的候选解 ， 然后找出那个 具有需要特性的元素
1 、 回溯法主要思想是每次只构造解的一个分量 ，然后按照 鲜明的方法来评估这个部分构造解 。如果一个部分构造解可以进一 步构造而不会违反问题的约束 ， 我们就接受对下一个分量所作的第 一个合法选择 。如果无法对下一个分量进行合法的选择 ， 就不对剩 下的任何分量再做任何选择了 。在这种情况下 ，该算法进行回溯 ， 把部分构造解的最后一个分量替换为它的下一个选择。
算法模式 Procedure BACKTRACK (n)； {k := l；

课件：第五章回溯法

课件：第五章回溯法

else if (aSaisfeg(oa)o)d{)R{reeccoorrdd((i为,a)a;末); 尾标记。
if ((ai =is=gno)al) {unfinish = false; output( );}
else i{fi+(a+h; aLs.sPounssh)(L1,.P2u, s…h-,Sno,n-s1()a;)}
启发式的搜索 从初始状态开始，每次选择最有可能达到终 止状态的结点进行搜索。
2021/11/25
计算机算法设计与分析
5
三种搜索的优劣之处
• 一般来说，三种搜索方法各有优劣之处：
• 广度优先搜索的优点是一定能找到解；缺点是 空间复杂性和时间复杂性都大。
• 深度优先搜索的优点是空间复杂性和时间复杂 性较小；缺点是不一定能找到解。
• 栈中的结点是分层次的，而现在没有区分它们 的层次。这就增加了回溯判断和操作的困难。
那采么用怎一么个办简？洁有效的方法：设计一个末 尾标记，每次压栈时，先压入末尾标记。
2021/11/25
计算机算法设计与分析
12
用末尾标记的迭代回溯
• Backtrack(Tree T) { • unfinish = true; L.Push(T.root); • while (unfinish || L≠Φ) { • a = L.Pop( ); • if (a is the last mark) backastep( );
• a = L.Pop( );
• if (a == -1) {i– –; a = rec[i]; rec[i]=0;used[a]=0;}
• else if (used[a]==0)
•
{rec[i]=a; used[a]=1;

第5章 回溯法ppt课件

第5章 回溯法ppt课件

2x3=2
x3=4 x3=2 x3=3
3
5
x4=4 x4=3
8 x4=4
10 13 15 x4=2 x4=3 x4=2
4
6
9
11 14 16
迷宫问题
演示
5.1 回溯法的算法框架
问题的解空间〔1）
1. 解向量：问题的解用向量表示
(x1, x2, …, xk) 模。 2. 约束条件
子树； 5. (2)限界函数：某个函数表达式或关系式。 6. 不真时，用于剪去得不到最优解的子树。 7. 回溯法：具有限界函数的深度优先搜索方法
回溯法的基本思想
1. 以深度优先方式搜索解空间。 2. 开始时，根结点为活结点，也是当前的扩展结点。 3. 对扩展结点，寻找儿子结点： 4. 如找到新结点，新结点成为活结点并成为扩展
子集树 void backtrack (int t){
if (t>n) output(x); else
for (int i=0;i<=1;i++) { x[t]=i; if (legal(t)) //若合法 backtrack(t+1);
} }
排列树 void backtrack (int t){
if (t>n) output(x); else
1装载问题2批处理作业调度3n后问题401背包问题5最大团问题6图的m着色问题7旅行售货员问题n皇后问题国际象棋中的皇后在横向直向和斜向都能走步和吃子问在nn格的棋盘上如何摆上n个皇后而使她们都不能相互吃掉
第5章 回溯法
上海大学计算机学院
学习要点与要求
• 掌握与理解回溯法的DFS搜索策略与方法
• （1〕掌握递归回溯

《算法设计与分析》-第五章 回溯法

《算法设计与分析》-第五章 回溯法
回溯法的应用—n后问题 后问题
例1(8-皇问题)
皇问题) 例1(8-皇问题) ( 皇问题
在8×8的棋盘上放置8个皇后,使得这8个皇 后不在同一行,同一列及同一斜角线上.如下 1 2 3 4 5 6 7 8 图6.1: Q
1 2 3 4 5 6 7 8
Q Q Q Q Q Q Q
5.1 回溯法的基本思想
(1)解空间 设问题的解向量为X=(x1,x2,…,xn) ,xi的取值范 围为有穷集Si .把xi的所有可能取值组合,称 为问题的解空间.每一个组合是问题的一个可 能解.
5.1 回溯法的基本思想
(1)解空间 例:0/1背包问题,S={0,1},当n=3时,0/1背 包问题的解空间是: {(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1, 1,0),(1,1,1)} 当输入规模为n时,有2n种可能的解.
A 2 C 3 F 4 L 4 2 G H 3 4 M N 1 B 3 D
4 4 I 2 O E 2 J 3 P 3 K 2 Q
----排列树 解空间大小: n!
5.1 回溯法的基本思想
(3)状态空间树的动态搜索
可行解和最优解: 可行解:满足约束条件的解,解空间中的一个子集 最优解:使目标函数取极值(极大或极小)的可行解,一 个或少数几个 例:货郎担问题,有nn种可能解. n!种可行解,只有一个或 几个解是最优解. 例:背包问题,有2n种可能解,有些是可行解,只有一个或 几个是最优解. 有些问题,只要可行解,不需要最优解,例如八后问题.
5.1 回溯法的基本思想
回溯法(backtracking)是一种系统地搜索问 题解的方法.为实现回溯,首先需要定义一个 解空间(solution space),然后以易于搜索 的方式组织解空间,最后用深度优先的方法搜 索解空间,获得问题的解.
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
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。在其解空间树上搜索最