BFS 和 DFS 算法有什么区别?
What is the difference between BFS and DFS algorithms?
使用 BFS 解决算法问题时发生超时。但是,有一个问题可以用 DFS 解决。为什么会出现这种差异?
题目是计算从(1,1)到(N,N)通过水平、垂直或对角线移动到达的次数。
如果用BFS解决问题(最坏情况)用了1331.0ms,用DFS解决用了62.0ms。 (我创建并测试了 16 * 16 个数组。)
附上问题 URL。 (但请理解它是韩语。)
URL> https://www.acmicpc.net/problem/17070
我想听到的答案是...
- 我以为 BFS 算法会更快,但为什么 DFS 更快?
- 是不是因为队列中的元素多,所以BFS变慢了?我想知道具体原因。
实现代码>
class 位置 {
int x;
int y;
int dir;
public Location(int x, int y, int dir) {
super();
this.x = x;
this.y = y;
this.dir = dir;
}
}
public class 主要{
static int[][] map;
static int Answer;
static int N;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
map = new int[N + 1][N + 1];
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 1; j <= N; j++)
map[i][j] = Integer.parseInt(st.nextToken());
}
DFS(1, 2, 0);
System.out.println(Answer);
Answer = 0;
BFS(1, 2, 0);
System.out.println(Answer);
br.close();
}
static void DFS(int x, int y, int pre) {
if (x == N && y == N) {
Answer++;
return;
}
if (pre == 0) {
if (y + 1 <= N && map[x][y + 1] == 0)
DFS(x, y + 1, 0);
if (y + 1 <= N && map[x][y + 1] == 0 && x + 1 <= N && map[x + 1][y] == 0 && map[x + 1][y + 1] == 0)
DFS(x + 1, y + 1, 1);
} else if (pre == 1) {
if (y + 1 <= N && map[x][y + 1] == 0)
DFS(x, y + 1, 0);
if (x + 1 <= N && map[x + 1][y] == 0)
DFS(x + 1, y, 2);
if (y + 1 <= N && map[x][y + 1] == 0 && x + 1 <= N && map[x + 1][y] == 0 && map[x + 1][y + 1] == 0)
DFS(x + 1, y + 1, 1);
} else {
if (x + 1 <= N && map[x + 1][y] == 0)
DFS(x + 1, y, 2);
if (y + 1 <= N && map[x][y + 1] == 0 && x + 1 <= N && map[x + 1][y] == 0 && map[x + 1][y + 1] == 0)
DFS(x + 1, y + 1, 1);
}
}
static void BFS(int startX, int startY, int dir) {
ArrayDeque<Location> arrayDeque = new ArrayDeque<>();
arrayDeque.add(new Location(startX, startY, dir));
Location location;
int x, y, pre;
while(!arrayDeque.isEmpty()) {
location = arrayDeque.remove();
x = location.x;
y = location.y;
pre = location.dir;
if(x == N-1 && y == N-1) {
Answer++; continue;
}
if (pre == 0) {
if (y + 1 <= N && map[x][y + 1] == 0)
arrayDeque.add(new Location(x, y + 1, 0));
if (y + 1 <= N && map[x][y + 1] == 0 && x + 1 <= N && map[x + 1][y] == 0 && map[x + 1][y + 1] == 0)
arrayDeque.add(new Location(x + 1, y + 1, 1));
} else if (pre == 1) {
if (y + 1 <= N && map[x][y + 1] == 0)
arrayDeque.add(new Location(x, y + 1, 0));
if (x + 1 <= N && map[x + 1][y] == 0)
arrayDeque.add(new Location(x + 1, y, 2));
if (y + 1 <= N && map[x][y + 1] == 0 && x + 1 <= N && map[x + 1][y] == 0 && map[x + 1][y + 1] == 0)
arrayDeque.add(new Location(x + 1, y + 1, 1));
} else {
if (x + 1 <= N && map[x + 1][y] == 0)
arrayDeque.add(new Location(x + 1, y, 2));
if (y + 1 <= N && map[x][y + 1] == 0 && x + 1 <= N && map[x + 1][y] == 0 && map[x + 1][y + 1] == 0)
arrayDeque.add(new Location(x + 1, y + 1, 1));
}
}
}
}
BFS 和 DFS 都具有 O(|V| + |E|)
时间复杂度,您遇到的时间差异很可能是由于 BFS 的实现错误导致 循环不变量.
实现 BFS 时最常见的错误之一是多次将相同的元素添加到队列中。一个人应该只向队列添加一个顶点 v
一次,这样你就可以确保它被删除一次。除非你这样做,否则渐近运行时(即它的复杂性)将不再是线性的。您可以查看相关的 CLRS 章节来证明这一点,基于他们引入的 循环不变性 概念。
换句话说,BFS是一种遍历算法。它找出 哪些 个顶点是可达的,而不是到达每个顶点 v
的路由数。如果您尝试计算 K<sub>v</sub>
通过 BFS 从 (1, 1)
到达每个 v
的方法数,则复杂性变得大于线性。 如果问题要求你找到K<sub>v</sub>
,那么你的方法应该是使用memoization和dynamic编程,而不是 BFS。
具体来说,根据您提供的代码,您的算法似乎没有跟踪先前是否探索过顶点(即网格中的单元格)。这导致顶点被多次探索,这超过了使用 BFS 和 DFS 等图遍历算法的意义。使用我上面提到的术语,您将违反 BFS 的循环不变量,它指出 每个顶点仅从队列中弹出一次 。这会导致代码的复杂性远高于线性。
您应该查看术语 memoization 并找出一种方法来找到 (N, N)
的解决方案,使用您计算的解决方案 仅一次 对于 (N-1, N-1)
、(N-1, N)
和 (N, N-1)
。
您的 BFS 实现使用动态内存分配和 ArrayDeque;你的 DFS 避免了这种情况。这将增加 BFS 每个节点的成本,尽管它会那么多很奇怪。
您可以尝试在每次调用 DFS 时分配一个新位置(并可能在 ArrayDeque 中添加和删除它),看看这是否会导致相同的性能损失。
另外当x=y=N时你的BFS不会直接停止;但我没有看到它显着增加了 运行 时间。
使用 BFS 解决算法问题时发生超时。但是,有一个问题可以用 DFS 解决。为什么会出现这种差异?
题目是计算从(1,1)到(N,N)通过水平、垂直或对角线移动到达的次数。
如果用BFS解决问题(最坏情况)用了1331.0ms,用DFS解决用了62.0ms。 (我创建并测试了 16 * 16 个数组。)
附上问题 URL。 (但请理解它是韩语。) URL> https://www.acmicpc.net/problem/17070
我想听到的答案是...
- 我以为 BFS 算法会更快,但为什么 DFS 更快?
- 是不是因为队列中的元素多,所以BFS变慢了?我想知道具体原因。
实现代码>
class 位置 {
int x;
int y;
int dir;
public Location(int x, int y, int dir) {
super();
this.x = x;
this.y = y;
this.dir = dir;
}
}
public class 主要{
static int[][] map;
static int Answer;
static int N;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
map = new int[N + 1][N + 1];
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 1; j <= N; j++)
map[i][j] = Integer.parseInt(st.nextToken());
}
DFS(1, 2, 0);
System.out.println(Answer);
Answer = 0;
BFS(1, 2, 0);
System.out.println(Answer);
br.close();
}
static void DFS(int x, int y, int pre) {
if (x == N && y == N) {
Answer++;
return;
}
if (pre == 0) {
if (y + 1 <= N && map[x][y + 1] == 0)
DFS(x, y + 1, 0);
if (y + 1 <= N && map[x][y + 1] == 0 && x + 1 <= N && map[x + 1][y] == 0 && map[x + 1][y + 1] == 0)
DFS(x + 1, y + 1, 1);
} else if (pre == 1) {
if (y + 1 <= N && map[x][y + 1] == 0)
DFS(x, y + 1, 0);
if (x + 1 <= N && map[x + 1][y] == 0)
DFS(x + 1, y, 2);
if (y + 1 <= N && map[x][y + 1] == 0 && x + 1 <= N && map[x + 1][y] == 0 && map[x + 1][y + 1] == 0)
DFS(x + 1, y + 1, 1);
} else {
if (x + 1 <= N && map[x + 1][y] == 0)
DFS(x + 1, y, 2);
if (y + 1 <= N && map[x][y + 1] == 0 && x + 1 <= N && map[x + 1][y] == 0 && map[x + 1][y + 1] == 0)
DFS(x + 1, y + 1, 1);
}
}
static void BFS(int startX, int startY, int dir) {
ArrayDeque<Location> arrayDeque = new ArrayDeque<>();
arrayDeque.add(new Location(startX, startY, dir));
Location location;
int x, y, pre;
while(!arrayDeque.isEmpty()) {
location = arrayDeque.remove();
x = location.x;
y = location.y;
pre = location.dir;
if(x == N-1 && y == N-1) {
Answer++; continue;
}
if (pre == 0) {
if (y + 1 <= N && map[x][y + 1] == 0)
arrayDeque.add(new Location(x, y + 1, 0));
if (y + 1 <= N && map[x][y + 1] == 0 && x + 1 <= N && map[x + 1][y] == 0 && map[x + 1][y + 1] == 0)
arrayDeque.add(new Location(x + 1, y + 1, 1));
} else if (pre == 1) {
if (y + 1 <= N && map[x][y + 1] == 0)
arrayDeque.add(new Location(x, y + 1, 0));
if (x + 1 <= N && map[x + 1][y] == 0)
arrayDeque.add(new Location(x + 1, y, 2));
if (y + 1 <= N && map[x][y + 1] == 0 && x + 1 <= N && map[x + 1][y] == 0 && map[x + 1][y + 1] == 0)
arrayDeque.add(new Location(x + 1, y + 1, 1));
} else {
if (x + 1 <= N && map[x + 1][y] == 0)
arrayDeque.add(new Location(x + 1, y, 2));
if (y + 1 <= N && map[x][y + 1] == 0 && x + 1 <= N && map[x + 1][y] == 0 && map[x + 1][y + 1] == 0)
arrayDeque.add(new Location(x + 1, y + 1, 1));
}
}
}
}
BFS 和 DFS 都具有 O(|V| + |E|)
时间复杂度,您遇到的时间差异很可能是由于 BFS 的实现错误导致 循环不变量.
实现 BFS 时最常见的错误之一是多次将相同的元素添加到队列中。一个人应该只向队列添加一个顶点 v
一次,这样你就可以确保它被删除一次。除非你这样做,否则渐近运行时(即它的复杂性)将不再是线性的。您可以查看相关的 CLRS 章节来证明这一点,基于他们引入的 循环不变性 概念。
换句话说,BFS是一种遍历算法。它找出 哪些 个顶点是可达的,而不是到达每个顶点 v
的路由数。如果您尝试计算 K<sub>v</sub>
通过 BFS 从 (1, 1)
到达每个 v
的方法数,则复杂性变得大于线性。 如果问题要求你找到K<sub>v</sub>
,那么你的方法应该是使用memoization和dynamic编程,而不是 BFS。
具体来说,根据您提供的代码,您的算法似乎没有跟踪先前是否探索过顶点(即网格中的单元格)。这导致顶点被多次探索,这超过了使用 BFS 和 DFS 等图遍历算法的意义。使用我上面提到的术语,您将违反 BFS 的循环不变量,它指出 每个顶点仅从队列中弹出一次 。这会导致代码的复杂性远高于线性。
您应该查看术语 memoization 并找出一种方法来找到 (N, N)
的解决方案,使用您计算的解决方案 仅一次 对于 (N-1, N-1)
、(N-1, N)
和 (N, N-1)
。
您的 BFS 实现使用动态内存分配和 ArrayDeque;你的 DFS 避免了这种情况。这将增加 BFS 每个节点的成本,尽管它会那么多很奇怪。
您可以尝试在每次调用 DFS 时分配一个新位置(并可能在 ArrayDeque 中添加和删除它),看看这是否会导致相同的性能损失。
另外当x=y=N时你的BFS不会直接停止;但我没有看到它显着增加了 运行 时间。