搜索策略学习笔记（5）：DFS最优问题求解的缺陷

发表于   |   分类于   |  

承接上一篇学习笔记（BFS最优问题求解实例）我再给大家看看如果用DFS求解这个问题的代码，比BFS复杂很多
在使用DFS时，我遇到的困难有：

Difficult

1.为了防止死循环，所以 当Ignatius走到一个Bomb-Reset-Equipment上时，这个结点的子辈结点都不能再使用这个Bomb-Reset-Equipment，而这个结点的兄弟结点和父辈结点的兄弟结点仍可以使用，所以在递归和回溯时要把控制Bomb-Reset-Equipment是否可用的变量修改（reset[i][j]–/reset[i][j]++，当reset[i][j]=1时maze[i][j]的Bomb-Reset-Equipment才可用）；而BFS中只要有一个结点访问过Bomb-Reset-Equipment就可把这个Bomb-Reset-Equipment视为EMPTY

2.如果要进行剪枝，DFS比较困难，需要再定义一个vis地图保存访问记录，当Ignatius走到Bomb-Reset-Equipment上时还要允许Ignatius可以回退两步（BACK），不仅情况复杂，而且占用内存空间比较大；而BFS如果要剪枝的话只需要保存其父结点（之后我会给出带剪枝的BFS和DFS的code），当Ignatius走到Bomb-Reset-Equipment上时只要把此结点的父结点指向自己即可

3.查找次数过多

case1：
2 1 1
1 1 0
1 1 3

case2：
2 1 1 0 1 1 1 0
1 0 4 1 1 0 4 1
1 0 0 0 0 0 0 1
1 1 1 4 1 1 1 3

case3：
1 2 1 1 1 1 1 4
1 0 0 0 1 0 0 1
1 4 1 0 1 1 0 1
1 0 0 0 0 3 0 1
1 1 4 1 1 1 1 1

—- | Case1 | Case2 | Case3 |
BFS |—– 34 |—-119 |— 164 |
DFS |—– 36 |—-989 |— 564 |

My AC Code

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
//Title：use DFS to search the shortest path
//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 MAX_LIFE 6
int maze[SIZE][SIZE];
int reset[SIZE][SIZE];
int n,m;
int min;
//int cnt;
void Visit(int i,int j,int life,int time) {
	//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) {
		if (reset[i][j] == 1) {
			life = MAX_LIFE;
		}
		
		reset[i][j]--;
	}
	if (1 <= i-1) {
		Visit(i-1,j,life-1,time+1);
	}
	if (i+1 <= n) {
                Visit(i+1,j,life-1,time+1);
	}
	if (1 <= j-1) {
		Visit(i,j-1,life-1,time+1);
	}
	if (j+1 <= m) {
		Visit(i,j+1,life-1,time+1);
	}
	if (maze[i][j] == RESET) {
		reset[i][j]++; 	
	}
	
	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++) {
				scanf("%d",&maze[i][j]);
		
				if (maze[i][j] == START) {
					pos_i = i;
					pos_j = j;
				}
				if (maze[i][j] == RESET) {
					reset[i][j] = 1;
				}
				else {
					reset[i][j] = 0;
				}
			}
		} 
	
		//cnt = 0;
		min = -1;
	
		Visit(pos_i,pos_j,MAX_LIFE,0);
		printf("%d\n",min);
		//printf("%d\n",cnt);
	}
	return 0;
}