В чем разница между алгоритмами BFS и DFS? - PullRequest
0 голосов
/ 05 апреля 2019

Истекло время ожидания при решении проблемы алгоритма с BFS. Однако есть проблема, которая может быть решена с помощью DFS. Почему возникает эта разница?

Задача состоит в том, чтобы рассчитать количество прибывших от (1,1) до (N, N) путем перемещения по горизонтали, вертикали или диагонали.

Потребовалось 1331,0 мс, если проблема была решена с помощью BFS (наихудший случай), и 62,0 мс, когда она была решена с помощью DFS. (Я создал и протестировал 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));
        }
    }
}

}

Ответы [ 2 ]

5 голосов
/ 05 апреля 2019

Как BFS, так и DFS имеют O(|V| + |E|) сложность времени, и разница во времени, которую вы испытываете, скорее всего коренится в ошибке при реализации BFS, которая нарушает инвариант цикла .

Одной из наиболее распространенных ошибок, допущенных при реализации BFS, является добавление одного и того же элемента в очередь несколько раз. Нужно только один раз добавить вершину v в очередь, чтобы вы могли убедиться, что она удаляется один раз. Если вы этого не сделаете, то асимптотическое время выполнения (т.е. его сложность) больше не будет линейным. Вы можете увидеть соответствующую главу CLRS , чтобы доказать это, основываясь на концепции инварианта цикла , которую они вводят.

Другими словами, BFS - это алгоритм обхода. Он выясняет , какие вершины достижимы, а не количество маршрутов для достижения каждой вершины v. Если вы попытаетесь вычислить количество способов K<sub>v</sub> добраться до каждого v от (1, 1) через BFS, сложность станет больше, чем линейная. Если проблема просит вас найти K<sub>v</sub>, то ваш подход должен заключаться в использовании мемоизации и динамического программирования, а не BFS.

В частности, на основе предоставленного вами кода ваш алгоритм, похоже, не отслеживает, была ли ранее исследована вершина (то есть ячейка в сетке) или нет. Это приводит к многократному исследованию вершин, что лишает смысла использовать алгоритм обхода графа, такой как BFS и DFS. Используя вышеупомянутую терминологию, вы идете против инварианта цикла BFS, который гласит, что каждая вершина выталкивается из очереди только один раз . Это приводит к тому, что сложность вашего кода становится намного выше, чем линейная.

Вы должны изучить термин памятка и найти способ найти решения для (N, N), используя решения, которые вы вычисляете только один раз для (N-1, N-1), (N-1, N) и (N, N-1).

0 голосов
/ 05 апреля 2019

Ваша реализация BFS использует динамическое распределение памяти и ArrayDeque; ваша DFS избегает этого. Это увеличит стоимость одного узла для вашей BFS, хотя странно, что это будет так много.

Вы можете попытаться выделить новое местоположение в каждом вызове DFS (и, возможно, добавить и удалить его из ArrayDeque) и посмотреть, не приводит ли это к той же потере производительности.

Кроме того, ваша BFS не останавливается напрямую, когда x = y = N; но я не вижу, что это значительно увеличивает время выполнения.

...