回溯法

概念

回溯算法实际上是一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径。

回溯法是一种选优搜索法,按选优条件向前搜索以达到目标。当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术称为回溯法,而满足回溯条件的某个状态的点称为回溯点。

许多复杂的、规模较大的问题都可以使用回溯法,有“通用解题方法”之称。

基本思想

在包含问题的所有解的解空间树中,按照深度优先搜索的策略,从根节点出发深度优先搜索解空间树。当探索到某一结点时,要先判断节点是否包含问题的解,如果包含,就从该节点出发继续探索下去,如果不包含,则逐层向其祖先节点回溯。

用回溯法求解问题的所有解时,要回溯到根,且根节点的所有可行的子树都要已被搜索遍才结束。

而若用回溯法求任意一个解时,只要搜索到问题的一个可行解就可以结束。

步骤

针对所给问题,确定问题的解空间:首先应明确定义问题的解空间,问题的解空间应至少包含问题的一个(最优)解。

确定结点的扩展搜索规则

以深度优先方式搜索解空间,并在搜索过程中用剪枝函数避免无效搜索

子集树:当所给问题是从 n 个元素的集合 S 中找出 S 满足的某种性质的子集时,相应的解空间树称为子集树。例如,0-1背包问题,要求在n个物品的集合S中,选出几个物品,使物品在背包容积C的限制下,总价值最大(即集合S的满足条件 <容积C下价值最大> 的某个子集)。

子集树是从集合S中选出符合限定条件的子集,故每个集合元素只需判断是否(0,1)入选,因此解空间应是一颗满二叉树。

1
2
3
4
5
6
7
8
9
10
void backtrack(int t) { //t是当前层数
if(t > n) output(x);
else {
for(int i = 0; i <= 1; i++) { //子集树是从集合S中,选出符合限定条件的子集,故每个元素判断是(1)否(0)选入即可(二叉树),因此i定义域为{0,1}
x[t] = i; //x[]表示是否加入点集,1表示是,0表示否
if(constraint(t) && bound(t)) //constraint(t)和bound(t)分别是约束条件和限定函数
backtrack(t + 1);
}
}
}

排列树:当问题是确定n个元素满足某种性质的排列时,相应的解空间称为排列树。排列树与子集树最大的区别在于,排列树的解包括整个集合S的元素,而子集树的解则只包括符合条件的集合S的子集。

1
2
3
4
5
6
7
8
9
10
11
void backtrack(int t) { //t是当前层数
if(t > n) output(x);
else {
for(int i = t; i <= n; i++) {
swap(x[t], x[i]);
if(constraint(t) && bound(t))
backtrack(t + 1);
swap(x[i], x[t]);
}
}
}

非子集树,非排列数:

1
2
3
4
5
6
7
8
9
10
void backtrack(int t) {
if(t > n) output(x);
else {
for(int i = f(n, t); i <= g(n, t); i++) {
x[t] = h[i];
if(constraint(t) && bound(t))
backtrack(t + 1);
}
}
}

货箱装船问题

有两艘船,载重量为c1、c2,有n个货箱,重量分别为w1, w2, …, wn。

基本思路: 容易证明,如果一个给定装载问题有解,则采用下面的策略可得到最优装载方案。
(1)首先将第一艘轮船尽可能装满;
(2)将剩余的集装箱装上第二艘轮船。

将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集,使该子集中集装箱重量之和最接近c1。由此可知,装载问题等价于特殊的0-1背包问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int n;       //货箱数目
int w[maxn]; //货箱重量数组
int c; //第1艘船的载重量
int cw; //当前装载的重量
int bestw; //目前最优装载的重量

void maxLoading(int i) { //从第i层节点搜索
if(i > n) {
if(cw > bestw) bestw = cw;
return;
}
if(cw + w[i] <= c) { //尝试x[i] = 1
cw += w[i];
maxLoading(i + 1);
cw -= w[i]; //回溯
}
maxLoading(i + 1); //尝试x[i] = 0
}

You need to set client_id and slot_id to show this AD unit. Please set it in _config.yml.