BFS和DFS算法有什么区别?

问题描述 投票:0回答:2

解决BFS的算法问题时发生超时。但是,有一个问题可以通过DFS解决。为什么会出现这种差异?

问题是通过水平,垂直或对角线移动来计算从(1,1)到(N,N)的到达次数。

如果问题由BFS(最坏情况)解决,则花费1331.0ms,当DFS解决问题时花费62.0ms。 (我已经创建并测试了16 * 16阵列。)

附上问题URL。 (但请理解它是韩文。)URL> https://www.acmicpc.net/problem/17070

我想听到的答案是......

  1. 我认为BFS算法会更快,但为什么DFS会更快?
  2. BFS是否较慢,因为队列中有许多元素?我想知道确切的原因。

实施代码>

班级地点{

int x;
int y;
int dir;

public Location(int x, int y, int dir) {
    super();
    this.x = x;
    this.y = y;
    this.dir = dir;
}

}

公共类Main {

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));
        }
    }
}

}

algorithm breadth-first-search dfs
2个回答
5
投票

BFS和DFS都具有O(|V| + |E|)时间复杂度,而您遇到的时间差异很可能源于BFS实现中的错误,即打破循环不变量。

实现BFS时出现的一个常见错误是多次向队列添加相同的元素。应该只将一个顶点v添加到队列中一次,这样就可以确保它被删除一次。除非你这样做,否则渐近运行时(即它的复杂性)将不再是线性的。您可以根据他们介绍的循环不变概念,查看相关的CLRS章节以证明这一点。

换句话说,BFS是遍历算法。它找出哪些顶点是可到达的,而不是到达每个顶点v的路径数。如果你试图计算Kvv到BFS到达每个(1, 1)的方式的数量,复杂性变得大于线性。如果问题要求您找到Kv,那么您的方法应该是使用memoization和动态编程,而不是BFS。

具体来说,根据您提供的代码,您的算法似乎无法跟踪先前是否探索过顶点(即网格中的单元格)。这会导致顶点被多次探索,这比使用像BFS和DFS这样的图遍历算法更为重要。使用上面提到的术语,你将反对BFS的循环不变量,它指出每个顶点只从队列中弹出一次。这会导致代码的复杂性远高于线性。

您应该查看术语memoization并找出一种方法来找到(N, N)的解决方案,使用您只为(N-1, N-1)(N-1, N)(N, N-1)计算一次的解决方案。


0
投票

您的BFS实现使用动态内存分配和ArrayDeque;你的DFS避免了这一点。这将增加你的BFS的每个节点的成本,尽管奇怪的是它会那么多。

您可以尝试在每次DFS调用中分配一个新位置(并可能在ArrayDeque中添加和删除它),看看是否会导致相同的性能损失。

此外,当x = y = N时,您的BFS不会直接停止;但我没有看到它显着增加了运行时间。

© www.soinside.com 2019 - 2024. All rights reserved.