В чем разница между алгоритмами BFS и DFS?

ProgramBox

В чем разница между алгоритмами BFS и DFS?

Post author:admin
Запись опубликована:1 апреля, 2023
Post category:Вопросы по программированию

#algorithm #depth-first-search #breadth-first-search

#алгоритм #поиск в глубину #поиск в ширину

Вопрос:

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

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

Потребовалось 1331,0 мс, если проблема была решена с помощью BFS (наихудший случай), и 62,0 мс, когда она была решена с помощью DFS. (Я создал и протестировал массивы 16 * 16.)

Прикрепите URL-адрес проблемы. (Но, пожалуйста, поймите, что это корейский.) URL>https://www.acmicpc.net/problem/17070

Ответ, который я хочу услышать, таков…

Я думал, что алгоритм BFS будет быстрее, но почему DFS быстрее?
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 amp;amp; y == N) {

        Answer  ;
        return;
    }

    if (pre == 0) {

        if (y   1 <= N amp;amp; map[x][y   1] == 0)
            DFS(x, y   1, 0);

        if (y   1 <= N amp;amp; map[x][y   1] == 0 amp;amp; x   1 <= N amp;amp; map[x   1][y] == 0 amp;amp; map[x   1][y   1] == 0)
            DFS(x   1, y   1, 1);
    } else if (pre == 1) {

        if (y   1 <= N amp;amp; map[x][y   1] == 0)
            DFS(x, y   1, 0);

        if (x   1 <= N amp;amp; map[x   1][y] == 0)
            DFS(x   1, y, 2);

        if (y   1 <= N amp;amp; map[x][y   1] == 0 amp;amp; x   1 <= N amp;amp; map[x   1][y] == 0 amp;amp; map[x   1][y   1] == 0)
            DFS(x   1, y   1, 1);
    } else {

        if (x   1 <= N amp;amp; map[x   1][y] == 0)
            DFS(x   1, y, 2);

        if (y   1 <= N amp;amp; map[x][y   1] == 0 amp;amp; x   1 <= N amp;amp; map[x   1][y] == 0 amp;amp; 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 amp;amp; y == N-1) {
               Answer  ; continue;
            }

        if (pre == 0) {

            if (y   1 <= N amp;amp; map[x][y   1] == 0)
                arrayDeque.add(new Location(x, y   1, 0));

            if (y   1 <= N amp;amp; map[x][y   1] == 0 amp;amp; x   1 <= N amp;amp; map[x   1][y] == 0 amp;amp; map[x   1][y   1] == 0)
                arrayDeque.add(new Location(x   1, y   1, 1));
        } else if (pre == 1) {

            if (y   1 <= N amp;amp; map[x][y   1] == 0)
                arrayDeque.add(new Location(x, y   1, 0));

            if (x   1 <= N amp;amp; map[x   1][y] == 0)
                arrayDeque.add(new Location(x   1, y, 2));

            if (y   1 <= N amp;amp; map[x][y   1] == 0 amp;amp; x   1 <= N amp;amp; map[x   1][y] == 0 amp;amp; map[x   1][y   1] == 0)
                arrayDeque.add(new Location(x   1, y   1, 1));
        } else {

            if (x   1 <= N amp;amp; map[x   1][y] == 0)
                arrayDeque.add(new Location(x   1, y, 2));

            if (y   1 <= N amp;amp; map[x][y   1] == 0 amp;amp; x   1 <= N amp;amp; map[x   1][y] == 0 amp;amp; map[x   1][y   1] == 0)
                arrayDeque.add(new Location(x   1, y   1, 1));
        }
    }
}

}

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

Ответ №1:

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

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

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

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

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

1. @Taylous Я обновил свой ответ на основе предоставленного вами примера кода.

2. Обратите внимание, что для того, чтобы найти решение для (N, N) на основе решений для (N-1, N-1), (N-1, N) и (N, N-1) — или вообще обновить массив с количеством решений для каждой ячейки — вам нужно разделить общее количество возможных решений на три решения в зависимости от того, был ли последний ход горизонтальным, вертикальным или диагональным. (Поскольку в противном случае диагональные перемещения считались бы три раза: по диагонали, по горизонтали-> по вертикали, по вертикали-> по горизонтали.)

3. Да, есть третий параметр направления. Но я просто хотел намекнуть на то, как работает memoization и DP-подход, в отличие от предложения всех деталей одного.

Ответ №2:

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

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

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