BFS和DFS算法之间有什么区别？

Question

解决BFS的算法问题时发生超时。但是，存在DFS可以解决的问题。为什么会出现这种差异？

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

如果用BFS解决问题（最坏的情况）需要1331.0毫秒，而用DFS解决则花费了62.0毫秒。（我已经创建并测试了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;
}

}

公共班级主要{

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

}

Answer 1

BFS和DFS都具有O(|V| + |E|)时间复杂性，并且您遇到的时间差很可能是由于BFS的实现中的错误而导致循环不变。

实施BFS时犯的最常见错误之一是多次将同一元素添加到队列中。一个顶点只应添加一次v到队列中，这样就可以确保将其删除一次。除非您这样做，否则渐近运行时（即其复杂性）将不再是线性的。您可以在相关的CLRS章节中找到证明，这是基于它们引入的循环不变性概念。

换句话说，BFS是遍历算法。它发现它的顶点是可达的，不是路线到达每个顶点数量v。如果你试图计算的方式的数量，以达到每个从通过BFS，复杂性变得比线性更大。如果问题要求您找到，那么您的方法应该是使用记忆和动态编程，而不是BFS。Kvv(1, 1)Kv

具体而言，根据您提供的代码，您的算法似乎无法跟踪先前是否探索过顶点（即网格中的单元）。这将导致顶点被多次浏览，这超越了使用诸如BFS和DFS之类的图遍历算法的要点。使用上面提到的术语，您将遇到BFS的循环不变式，该循环不变式指出每个顶点仅从队列中弹出一次。这会导致代码的复杂度远高于线性。

你应该看看术语记忆化，并想出一个办法找到一个解决方案(N, N)，使用你计算的解决方案只有一次的(N-1, N-1)，(N-1, N)和(N, N-1)。