| 回溯法的研究 |
|
| 作者：未知 文章来源：本站原创 点击数： 更新时间：2006-1-3 |
|
|
回溯法1
回溯（backtrack）
回溯算法的基本思想和适用条件
回溯算法的设计步骤
估计回溯算法的效率
改进回溯算法的途径
分支估界
应用实例
2
基本思想和适用条件
实例
基本思想
搜索问题、搜索空间、搜索策略
判定条件、结点状态、存储结构
必要条件
3
实例
例1 四后问题
解表示成一个4维向量，（放置列号）
搜索空间：4叉树
4
例2 0-1背包问题：
V={12,11,9,8},W={8,6,4,3},B=13
结点：向量（子集的部分特征向量）
搜索空间：子集树，2n片树叶
<0,1,1,1> 对应于可行解： x1=0, x2=1, x3=1, x4=1. 重量：13, 价值：28
<1,0,1,0>对应于可行解： x1=1, x2=0, x3=1, x4=0. 重量：12，价值：21
5
例3 巡回售货员问题：
结点：向量 （部分巡回路线）
搜索空间：排列树
<1,2,4,3> 对应于巡回路线：
1→2 →4 →3 →1
长度：5+2+7+9=23
6
基本思想
适用问题：求解搜索问题
搜索空间：一棵树
每个结点对应了部分解向量，
树叶对应了可行解
搜索过程：
采用系统的方法隐含遍历搜索树
搜索策略：
深度优先，宽度优先，函数优先，宽深结合等
7
结点分支判定条件：
满足约束条件---分支扩张解向量
不满足约束条件，回溯到该结点的父结点
结点状态：
动态生成
结点状态：白结点（尚未访问）；
灰结点（正在访问该结点为根的子树）
黑结点（该结点为根的子树遍历完成）
存储：当前路径
8
必要条件--多米诺性质
设P(x1, x2, …, xi) 为真表示向量中i个皇
后放置在彼此不能攻击的位置
例4 求不等式的整数解
5x1+4x2−x3≤10, 1≤xi≤3, i=1,2,3
P(x1, …, xk) :意味将x1,x2,…,xk代入原不等式的相应
部分使得左边小于等于10
不满足多米诺性质
变换： 令x3=3−x3’,
5x1+4x2+x3’≤13 ，1≤x1, x2≤3, 0≤x3’≤2
P(x1 , x2 ,..., xk+1 ) → P(x1 , x2 ,..., xk ) 0 < k < n
9
回溯算法的设计步骤
设计要素
定义搜索问题的解向量和每个分量的取值范围
解向量为
xi的可能取值的集合为Xi, i=1,2,…,n.
x1,x2,…,xk-1确定以后xk的取值集合为Sk, Sk⊆Xk
确定结点儿子的排列规则
判断是否满足多米诺性质
搜索策略----深度优先
确定每个结点能够分支的约束条件
确定存储搜索路径的数据结构
10
算法ReBack(k)
1. if k>n then 是解;
2. else while Sk ≠∅ do
3. xk←Sk中最小值
4. Sk←Sk–{xk}
5. 计算Sk+1
6. ReBack(k+1)
7. k←k-1
8. if k>0 ReBack(k)
算法ReBacktrack(n)
1. for i←1 to n 计算Xk
2. ReBack(1)
递归回溯
11
迭代算法Backtrack
1. 对于i=1,2,…,n 确定Xi
2. k=1
3. 计算Sk
4. while Sk≠∅ do
5. xk←Sk中最小值; Sk←Sk–{xk}
6. if k7. k←k+1; 计算Sk
8. else 是解；k←k-1
9. if k>0 then goto 4
10. if k>1 then k←k-1； goto 4
迭代回溯
12
估计回溯算法的平均效率
计数搜索树中平均遍历的结点，Monte Carlo方法
Monte Carlo方法
1．从根开始，随机选择一条路经，直到不能分支为止,
即从x1,x2,…, 依次对xi赋值，每个xi的值是从当时的
Si中随机选取，直到向量不能扩张为止
2．假定搜索树的其他|Si|-1个分支与以上随机选出的路
径一样，计数搜索树的点数。
3．重复步骤1和2，将结点数进行概率平均。
13
例5 Monte Carlo方法估计四后问题的效率
case1．<1,4,2>：1+4+4×2+4×2 = 21
case2．<2,4,1,3>:：4×3+1=17
case3．<1,3>：1+4×1+4×2=13
假设4次抽样测试：case1 1次，case2 1次，case3 2次，平均为16
解空间的结点数为17
14
影响算法效率的因素
1. 最坏情况下的时间W(n)=(p(n)f(n))
其中p(n)每个结点时间，f(n)结点个数
2. 影响回朔算法效率的因素
搜索树的结构
分支情况：分支均匀否
树的深度
对称程度：对称适合裁减
解的分布
在不同子树中分布多少是否均匀
分布深度
约束条件的判断：计算简单
15
改进途径
根据树分支设计优先策略：
结点少的分支优先，解多的分支优先
利用搜索树的对称性剪裁子树
分解为子问题:
求解时间f(n)=c2n，组合时间T=O(f(n))
如果分解为k个子问题，每个子问题大小为n/k
则求解时间为kc k T
n
2 +
16
组合优化问题的描述
目标函数（极大化或极小化）
约束条件
搜索空间中满足约束条件的解称为可行解
使得目标函数达到极大(或极小)的解称为最优解
例6 背包问题：
, 1,2,3,4
2 3 4 7 10
max 3 5 9
1 2 3 4
1 2 3 4
∈ =
+ + + ≤
+ + +
x N i
x x x x
x x x x
i
17
分支估界技术
设立代价函数（极大化）
函数值是以该结点为根的搜索树中的所有可行
解的目标函数值的上界
父结点的代价大于等于子结点的代价
设立界
代表当时已经得到的可行解的目标函数的最大值
搜索中停止分支的依据
不满足约束条件或者其代价函数小于当时的界
界的设定与更新（目标函数值为正数）
初值可以设为0
可行解的目标函数值大于当时的界，进行更新
18
背包问题：
, 1,2,3,4
2 3 4 7 10
max 3 5 9
1 2 3 4
1 2 3 4
∈ =
+ + + ≤
+ + +
x N i
x x x x
x x x x
i
对变元重新排序
1
1
+
≥ +
i
i
i
i
w
v
w
v
, 1,2,3,4
7 4 3 2 10
max9 5 3
1 2 3 4
1 2 3 4
∈ =
+ + + ≤
+ + +
x N i
x x x x
x x x x
i
实例
19
的代价函数
否则
若对某个有
Σ
Σ
Σ Σ
=
=
= +
+
=
> − ≥
+ −
k
i
i i
j
k
i
i i
k
i k
k
i i
k
i
i i
v x
j k b w x w
w
v
v x b w x
1
1
1 1
1
1
( )
分支策略----深度优先
代价函数与分支策略的设定
20
, 1,2,3,4
7 4 3 2 10
max9 5 3
1 2 3 4
1 2 3 4
∈ =
+ + + ≤
+ + +
x N i
x x x x
x x x x
i
21
例7 最大团问题
给定无向图G=,求G中的最大团.
算法设计
结点的含义：已检索k个顶点，其中xi=1对应
的顶点在当前的团内，搜索树为子集树
约束条件：该顶点与当前团内每个顶点都有边相连
界：当前图中已检索到的极大团的顶点数
代价函数：目前的团扩张为极大团的顶点数上界
F=cn+n-k
其中cn为目前团的顶点数（初始为0），k为结点层数
时间：O(n2n)
实例（续）
22
例8 图的m着色
给定无向连通图G和m种颜色,给图的顶点着色，每个
顶点一种颜色，且每条边的两个顶点不同色.给出所有
可能的着色方案（如果不存在，则回答“No” ）
搜索空间为m叉完全树. 将颜色编号为1,2,…,m.
结点 表示顶点1着色x1,顶点2着色x2,…,顶点
k着色xk
约束条件：该顶点邻接表中已着色的顶点没有同色的
代价函数：没有（不是优化问题）
时间：O(nmn)
23
<1>
<1,2>
<1,2,1>
<1,2,1,3>
<1,2,1,3,1>
<1,2,1,3,1,2>
<1,2,1,3,1,2,3>
回溯算法的图示
24
提高效率的途径
根据对称性，只需搜索1/3的解空间即可. 当1和2
确定,即<1,2>以后，只有1个解，因此在<1,3>为根的
子树中也只有1个解.由于3个子树的对称性，总共有6
个解.
进一步分析，在取定<1,2>以后，不可以扩张成
<1,2,3>, 因为可以检查是否有和1,2,3都相邻的顶点.如
果存在,例如7, 则没有解. 所以可以从打叉的结点回
溯，而不必搜索它的子树.
25
例9 巡回售货员问题
问题：给定n个城市集合C={c1,c2,…,cn}, 从一个城市到
另一个城市的距离dij为正整数，求一条最短且每个
城市恰好经过一次的巡回路线.
巡回售货员问题的类型：有向图、无向图.
设巡回路线从1开始，解向量为, 其中
i1,i2,…,in-1为{2,3,…,n}的排列. 搜索空间为排列树，结点
表示得到k步巡回路线
26
Σ Σ
= ∉
= +
i B
i
k
j
j
j
j L d l
1
为部分巡回路线扩张成全程巡回路线的长度下界
时间O(n!)：计算O((n-1)!)次，代价函数计算O(n)
约束条件：令B={i1,i2,…,ik}, 则
ik+1∈{2,…,n}-B
界：当前得到的最短巡回路线长度
代价函数：设顶点ci出发的最短边长度为li，dj为选
定巡回路线中第j 段的长度，则
27
例11 圆排列问题
给定n个圆的半径
序列R={r1,r2,…,rn},
将圆放到矩形框中，
各圆与矩形底边相
切，求具有最小长
度ln的圆的排列顺序.
28
解为：其中i1,i2,…,in为1,2,…,n的排列
解空间为排列树.
部分解向量：表示前k个圆已经排好.
令B={i1,i2,…,ik},下一个园选择ik+1.
约束条件：ik+1∈{1,2,…,n}-B
界：当前得到的最小园排列长度
算法设计
29
k：算法完成第k步，已经选择了第1—第k个圆，
rk：第k个圆的半径
dk：第k-1个圆到第k个圆的圆心距离
xk：第k个圆的圆心坐标，规定x1=0,
lk：第1-第k个圆的排列长度
Lk：放好1-k个圆以后，对应结点的代价函数值
Lk≤ ln
代价函数计算的符号说明
30
相关公式
1
1
1
2
1
2
( 1 ) ( ) 2
l x r r
x x d
d r r r r r r
k k k
k k k
k k k k k k k
= + +
= +
= + − − =
−
− − −
31
1 1 2 1 1
1 2 1
2 2 ... 2
...
x r r r r r r r r
L x d d d r r
k k k k k n n n
k k k k n n
= + + + + + +
= + + + + + +
+ + + −
+ +
相关公式(续)
32
r r r i n B
x n k r r
x n k r r r
L x r r r r r r r r
i k j
k
k
k k k k k k n n n
j
= ∈ −
= + − + +
≥ + − + +
= + + + + + + + − + +
min( , ) {1,2,..., }
(2 2 1)
2( )
2 2 ... 2
1
1
1 1 2 1 1
时间：O(n n!)=O((n+1)!)
B={i1,i2,…,ik},
代价函数
33
实例
R={1,1,2,2,3,5}
取排列<1,2,3,4,5,6>,
半径排列为：1,1,2,2,3,5，结果见下表和下图
6 5 7.7 21.4 27.4 27.4
5 3 4.9 13.7 17.7 23.7
4 2 4 8.8 11.8 19.8
3 2 2.8 4.8 7.8 19.8
2 1 2 2 4 12
1 1 0 0 2 12
k rk dk xk lk Lk
34
R={1,1,2,2,3,5}
取排列<1,2,3,4,5,6>, 半径排列为：1,1,2,2,3,5，
最短长度L6=27.4
取排列<1,3,5,6,4,2>, 半径排列为1,2,3,5,2,1，L6=26.5
35
回溯算法小结
适应于求解组合搜索问题（含组合优化问题）
求解条件：满足多米诺性质
解的表示：解向量，求解是不断扩充解向量的过程
回溯条件：
搜索问题---约束条件
优化问题---约束条件+代价函数
算法复杂性：
遍历搜索树的时间，最坏情况为指数
空间代价小
平均时间复杂性的估计：Monte Carlo方法
降低时间复杂性的主要途径：
利用对称性裁减子树
划分成子问题
分支策略（深度优先、宽度优先、宽深结合、优先函数） |
