搜索策略学习笔记（6）：Strategy of Branch & Bound

发表于   |   分类于   |  

承接我的搜索学习笔记（4）BFS最优问题求解实例、（5）DFS最优问题求解的缺陷，我在问题搜索求解的过程中添加剪枝条件，并且对BFS和DFS分别进行了剪枝前后的性能测试，结果和总结我写在了这篇文章的最后

BFS with Bounds & Constraints

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
//Title：BFS with bounds & constraints
//Author：Call偶围城
#include <stdio.h>
#include <stdlib.h>
#define MAP_SIZE 10
#define QUEUE_LEN 100000
#define WALL  0
#define EMPTY 1
#define START 2
#define EXIT  3
#define RESET 4
#define MAX_LIFE 6
struct node{
	int i;
	int j;
	int life;
	int step;
	int id;
	int father;
};
const int di[4] = {-1,1,0,0};
const int dj[4] = {0,0,-1,1};
const char arrow[4][10] = {"up","down","left","right"};
struct node queue[QUEUE_LEN];
struct node x,y;
int head,tail;
int n,m;
int map[MAP_SIZE][MAP_SIZE];
int min;
//int cnt;
void append(struct node q,int first) {
	int i;
	if (first != 1) {
		for (i = head;i <= tail;i++) {
			if (queue[i].i == q.i && queue[i].j == q.j) {
				if (queue[i].step == q.step && queue[i].life >= q.life) {
					return;
				}
			}
		}
	}
	else {
		q.father = tail;
	}
	q.id = tail;
	queue[tail] = q;
	tail = (tail + 1) % QUEUE_LEN;
	return;
}
struct node serve() {
	struct node q = queue[head];
	head = (head + 1) % QUEUE_LEN;
	
	return q;	
}
int IsEmpty() {
	if (head == tail) {
		return 1;
	}
	else {
		return 0;
	}
}
void bfs() {
	int s_i,s_j;
	int i;
	while (!IsEmpty()) {
		//cnt++;
		x = serve();
		if (map[x.i][x.j] == EXIT) {
			min = x.step;
			return;
		}
		if (x.life <= 1) {
			continue;
		}
		for (i = 0;i < 4;i++) {
			s_i = x.i + di[i];
			s_j = x.j + dj[i];
			if ((1 <= s_i && s_i <= n)
			 && (1 <= s_j && s_j <= m)
			 && map[s_i][s_j] != WALL
			 && !(s_i == queue[x.father].i
			   && s_j == queue[x.father].j)
			) {
				y.i = s_i;
				y.j = s_j;
				
				if (map[s_i][s_j] == RESET) {
					y.life = MAX_LIFE;
					map[s_i][s_j] = EMPTY;
					y.step = x.step + 1;
					append(y,1);
				} 
				else {
					y.life = x.life - 1;
					y.step = x.step + 1;
					y.father = x.id;
					append(y,0);
				}
			}
		}				
	}	
}
int main() {
	int N;
	int s_i,s_j;
	int i,j;
	scanf("%d",&N);
	while (N--) {
		head = tail = 0;
		scanf("%d%d",&n,&m);
		
		for (i = 1;i <= n;i++) {
			for (j = 1;j <= m;j++) {
				scanf("%d",&map[i][j]);
				if (map[i][j] == START) {
					x.i = i;
					x.j = j;
					x.life = MAX_LIFE;
					x.step = 0;
					append(x,1);
				}
			}
		}
		//cnt = 0;
		min = -1;
		bfs();
		
		printf("%d\n",min);
		//printf("cnt=%d\n",cnt);
	}
	return 0;
}

DFS with Bounds & Constraints

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
//Title：DFS with bounds & constraints
//Author：Call偶围城
#include <stdio.h>
#include <stdlib.h>
#define SIZE 10 
#define WALL  0
#define EMPTY 1
#define START 2
#define EXIT  3
#define RESET 4
#define RESET_EMPTY 5
#define MAX_LIFE 6
#define BACK 2 
#define VISITED 1
#define UNVISITED 0
int maze[SIZE][SIZE];
int vis[SIZE][SIZE];
int n,m;
int min;
//int cnt;
void Visit(int i,int j,int life,int time,int back) {
	//cnt++;
	
	if (life <= 0 || (min != -1 && time >= min)) {
		return;
	}
	if (maze[i][j] == WALL) {
		return;
	}
	if (maze[i][j] == EXIT) {
		min = time;
		
		return;
	}
	if (maze[i][j] == RESET) {
		life = MAX_LIFE;
		back = BACK;
		maze[i][j] = RESET_EMPTY;
	}
	vis[i][j] = VISITED;
	if (i+1 <= n && (vis[i+1][j] == UNVISITED || back > 0) && maze[i+1][j] != RESET_EMPTY) {
		Visit(i+1,j,life-1,time+1,back-1);
	}
	if (j+1 <= m && (vis[i][j+1] == UNVISITED || back > 0) && maze[i][j+1] != RESET_EMPTY) {
                Visit(i,j+1,life-1,time+1,back-1);
	}
	if (1 <= i-1 && (vis[i-1][j] == UNVISITED || back > 0) && maze[i-1][j] != RESET_EMPTY) {
		Visit(i-1,j,life-1,time+1,back-1);
	}
	if (1 <= j-1 && (vis[i][j-1] == UNVISITED || back > 0) && maze[i][j-1] != RESET_EMPTY) {
		Visit(i,j-1,life-1,time+1,back-1);
	}
	if (maze[i][j] == RESET_EMPTY)
		maze[i][j] = RESET;
	
	if (back < 0)
		vis[i][j] = UNVISITED;
	return;
} 
int main() {
	int N;
	int pos_i,pos_j;
	int i,j;
	scanf("%d",&N);
	while (N--) {
		scanf("%d%d",&n,&m);
		
		for (i = 1;i <= n;i++) {
			for (j = 1;j <= m;j++) {
				vis[i][j] = UNVISITED;
				scanf("%d",&maze[i][j]);
		
				if (maze[i][j] == START) {
					pos_i = i;
					pos_j = j;
				}
			}
		} 
		
		//cnt = 0;
		min = -1;
	
		Visit(pos_i,pos_j,MAX_LIFE,0,0);
		printf("%d\n",min);
		//printf("cnt=%d\n",cnt);
	}
	return 0;
}


Property Comparison

以下是各类搜索在案例测试中的搜索次数的比较：
—- | Case1 | Case1 | Case1 |
without bounds or constrains
BFS |—– 34 |—-119 |— 164 |
DFS |—– 36 |—-989 |— 564 |
with bounds and constrains
BFS |—– 10 |—— 14|—- 32 |
DFS |—– 23 |—— 35|—- 57 |



关于我最近对搜索问题的学习，我最后还想说几句：

1.剪枝很重要
2.当求最短路径时，用BFS绝对比DFS好，尤其是程序出bug后，打印调试时，dfs几百行的数据一条条验证我的内心是崩溃的。。。
3.未剪枝的DFS应该可以AC，如果不考虑时间限制

注：读者可以进一步了解其他常用的搜索算法，如双向宽度优先搜索，启发式搜索（A*算法）。我在整理时看到一篇比较好的博客，在这里推荐给大家
http://blog.csdn.net/huangxy10/article/details/8034285
博主用C++对象的形式，以八数码问题为案例展示了各类搜索算法