【算法】回溯法_回溯法界值在何处更新

回溯法

回溯法：在约束条件下对解空间树进行深度优先搜索的过程，并在搜索过程中剪去那些不满足条件的分支。
问题的解： 为 n 元组 (X 1 ,…,X i ,…X n ) ，其中 X i 选自有限集 S · ，
基本策略：当选出一组值 X=(x 1 ,…,x i ,…x n ) 能够使评价函数 P(x 1 ,…,x i ,…x n )满足问题的某种约束条件或到达极值。每次只考虑一个分量，逐次扩大建立 n 元组，并随时用评价函数 P i (X 1 ,…,X i ,…X n ) 去判断正在形成的 n 元组是否有成功的希望，一旦确定部分元组 (X 1 , … ,X i ) 不能求出解时，则立即停止这种搜索，“剪掉”以当前结点为根的分枝，并逐次向上一个分量回溯，然后向其它分支继续探索 。
算法框架：
(1) 开始结点是一个活结点，也是一个 扩展结点；
(2) 如果能从当前的扩展结点移动到一个新的结点，那么这个新结点将变成一个活结点和可扩展结点，旧的扩展结点仍是一个活结点。
(3) 如果不能移动到一个新结点 ( 已经找到一个解或违反约束的情况 ) ，当前的扩展结点就变成了一个 死结点，便只能返回到最近被考察的活结点 ( 回溯 ), 这个活结点就变成了新的扩展结点。
(4) 当找到了最优解或者没有活结点的时候（回溯尽了所有的活结点），搜索过程结束。
适用条件：满足多米诺性质
设评价函数为$P(X)$，$X_i$为第i重解有
$$P(X_{i+1})\to P(X_i)$$

分支限界法

分支限界法：增加约束条件，剪掉解空间中更多分支，加快算法的执行速度。
约束条件
（ 1 ）上界函数：用来求得以当前结点为根的可行性解可能达到的极值。
（ 2 ）限界值：搜索到某一结点时，已经得到可行解或可能包含可行性解的最优值。
（ 3 ）评价函数：判定当前所获得路径或值是否为解的函数
剪枝
（ 1 ）该结点的上界小于界限值，即再往下搜索也不可能有更优的值。
（ 2 ）该结点无法代表任何可行解，因为它已经违反了问题的约束，不能满足评价函数。
（ 3 ）该节点代表的可行解的子集只包含一个单独的点。
设计步骤
（ 1 ）建立上界函数，函数值是以该结点为根的搜索树中的所有可行解在目标函数上求得值的上 / 下界。
（ 2 ）求得限界值，即当前巳经得到的可行解的目标函数的最大值。
（ 3 ）依据剪枝条件，停止分支的搜索，向上回溯到父结点。
（ 4 ）限界值的更新：当得到的可行解的目标函数值大于 / 小于当前限界值时，更新之。

例题1

0-1 背包问题：已知有 n 件物品，物品 i 的重量为 wi 、价值为 pi 。现从
中选取一部分物品装入一个背包内，背包最多可容纳的总重量是 m ，如何选择，才能使得物品的总价值最大？

#include <stdio.h>
#define N 100
/*
input
3 50
10 60
20 100
30 12 0

output
0  1  1  
220
*/
int m;//背包最多容纳的总重量
int n;//n件物品
int w[N];//物品重量数组
int v[N];//物品价值数组
int bagv;//当前背包价值
int bagw;//当前背包重量
int x[N];//当前解
int maxv;//最优价值
int maxx[N];//存放最优解
int r;//剩余背包重量
void input(){
	bagw = 0;
	bagv = 0;
	maxv = 0;
	scanf("%d%d",&n,&m);
	r = 0;
	for(int i = 0;i<n;++i){
		scanf("%d%d",&w[i],&v[i]);
		r = r + v[i];
		x[i] = 0;
	}
}
void bag(int i){
	if(i>=n){
		if(bagv>maxv){
			maxv = bagv;
			for(int j = 0;j<n;++j){
				maxx[j] = x[j];
			}
			return;
		}
	}
	r = r - v[i];
	if (bagw + w[i]<=m){
		bagw = bagw + w[i];
		bagv = bagv + v[i];
		x[i] = 1;
		bag(i+1);
		bagw = bagw - w[i];
		bagv = bagv - v[i];
		x[i] = 0;
	}
	if(bagv + r>= maxv){
		bag(i+1);
	}
	r = r + v[i];
}
int main(int argc, char const *argv[])
{
	input();
	bag(0);
	for (int i= 0;i<n;++i){
		printf("%d  ",maxx[i]);
	}
	printf("\n%d", maxv);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

例题2

旅行商问题(Traveling Salesman Problem，简称TSP)。

#include <stdio.h>
#define N 100
#define inf 1000000
/*
input
4
0 2 6 7
2 0 4 4
6 4 0 2
7 4 2 0

output
0  1  2  3  
15
*/
int n;
int d[N][N];
int nowd;
int nowx[N];
int mind;
int minx[N];
//全局变量自动初始化为0
void input(){
	nowd = 0;
	mind = inf;
	scanf("%d",&n);
	for (int i=0;i<n;++i){
		for(int j=0;j<n;++j){
			scanf("%d",&d[i][j]);
		}
	}
}
bool ok(int j){
	for (int k = 0;k<n;++k){
		if (nowx[k] == j){
			return false;
		}
	}
	return true;
}
void search(int i){
	if(i>=n){
		nowd = nowd + d[nowx[i-1]][0];
		if(mind > nowd){
			mind = nowd;
			for (int j = 0;j<n;++j){
				minx[j] = nowx[j];
			}
		}
		return;
	}
	for (int j = 1;j<n;++j){
		if(ok(j)){
			nowd = nowd + d[nowx[i-1]][j];
			nowx[i] = j;
			search(i+1);
			nowd = nowd - d[nowx[i-1]][j];
			nowx[i] = 0;
		}
	}
}
int main(int argc, char const *argv[])
{
	input();
	search(1);
	for (int i = 0; i < n; ++i)
	{
		printf("%d  ",minx[i]);
	}
	printf("\n%d",mind);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

参考资料：张小东老师ppt