Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.90/10: Рейтинг темы: голосов - 10, средняя оценка - 4.90
iRomul
159 / 100 / 14
Регистрация: 17.10.2012
Сообщений: 483
Завершенные тесты: 1
1

Поиск в глубину (DFS)

02.10.2013, 22:03. Просмотров 1810. Ответов 15
Метки нет (Все метки)

Добрый день! Интересует алгоритм поиска в ширину. Алгоритм вроде простой, но мне никак не понять, как он работает в данном случае. Допустим, есть ситуация:

1 1 1 3 1
1 1 1 0 1
1 1 0 0 1
1 0 0 1 1
1 2 1 1 1

Здесь 1 - "стена", а 0 - "пол". Задача определить, можно ли пройти из 2 в 3, если известны их координаты. Из средств у меня есть только массив значений. И по-этому вопрос - как для этого составить алгоритм? Я так понимаю, что исходный массив нужно преобразовать в матрицу смежности. Но как?
Спасибо!
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.10.2013, 22:03
Ответы с готовыми решениями:

Поиск в глубину dfs
Доброго времени суток. Использую алгоритм поиска в глубину в графе для поиска...

Поиск в глубину в конкретной задаче
Добрый день! Я знаю что задача...

Можно ли распараллелить алгоритм DFS?
Можно ли распараллелить алгоритм DFS? Если да, то можно ссылку на статью? А...

Разница между DFS и Backtracking
Не могу никак понять в чём принципиальная разница между Поиском в глубину (DFS)...

Обход в глубину?
Вот...

15
Mysterious Light
Эксперт по математике/физике
3996 / 1961 / 398
Регистрация: 19.07.2009
Сообщений: 2,985
Записей в блоге: 21
03.10.2013, 03:28 2
Поиск в ширину:

берёте булеву матрицу тех же размеров a (заведомо всё false) и список пар чисел (или два списка чисел) p (заведомо пустой).
сначала ставите a[x2][y2] = true, p[0] = { x: x2, y: y2}, т.е. говорите, что точка 2 достижима из точки 2 и всякий путь из точки 2 начинается с точки 2. Капитан Очевидность плачет.
затем делаете цикл, пока p непусто и первый элемент не точка 3, оно содержит множество точек, которыми кончается хотя бы один путь из точки 2 и хотя бы гипотетически возможно продолжение этого пути.
на каждой итерации мы извлекаем первый элемент (shift в javascript) из p, рассматриваем 4 его соседа. Из них мы отсекаем нефизичные (за бортом) и недоступные (для которых в матрице стоит 0), а также те, где a истинно, такие уже были посещены. Оставшиеся вершины мы добавляем в конец списка p, помечаем в a их как true.

Пример: ваша матрица.
подготовка: a[5][2] = true, p[0] = { x: 5, y: 2 }
1iter: cur = { x: 5, y: 2 }, p = []; added = [{ x: 4, y: 2}], p = [{x:4,y:2}], a[4][2] = true
2iter: cur = {x:4,y:2}, p = []; added = [{x:3,y:3}], p = [{x:3,y:3}], a[3][3] = true
и так далее.
всего 6 итераций.
этот пример простой, потому что в p на каждом шаге только один элемент.
Вот если у Вас развилки будут, в p будет количество элементов, равное числу ветвлений (грубо).

ЗЫ матрицу смежности явно можно не выписывать.
ЗЗЫ описанное можно оптимизировать.
0
iRomul
159 / 100 / 14
Регистрация: 17.10.2012
Сообщений: 483
Завершенные тесты: 1
03.10.2013, 10:16  [ТС] 3
Получается, что если у нас есть развилки, то для всех p мы должны будем вызвать рекурсивно поиск для всех вариантов?
0
Igor3D
1227 / 594 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
03.10.2013, 11:16 4
Представьте себе "пятно" которое растекается от точки 2 заполняя клетки "пол". В конце-концов или пятно достигнет точки 3 или мы не можем добавить никакую клетку пола.

- отмечаем клетку 2 как посещаемую и помещаем ее в стек/очередь. До тех пор пока стек не пуст
- извлекаем эл-т из стека и просматриваем всех его соседей
если сосед клетка 3 - ответ найден, иначе
- если сосед отмечен как посещаемый - ничего не делаем, иначе
- отмечаем соседа как посещаемого и помещаем в стек
1
Qwertiy
821 / 629 / 100
Регистрация: 20.08.2013
Сообщений: 2,524
03.10.2013, 11:41 5
Цитата Сообщение от iRomul Посмотреть сообщение
И по-этому вопрос - как для этого составить алгоритм?
Для каждой клетки проверяем соседнии и рекурсивно запускаемся из них. Начальная клетка - с 2. Если пришли в клетку 3, то ответ да, прекращаем поиск. Если ничего не нашли, ответ нет. Попадая в клетку, стираем её на поле, чтобы она больше не считалась пустой и обратно мы в неё не пошли.

Цитата Сообщение от iRomul Посмотреть сообщение
Я так понимаю, что исходный массив нужно преобразовать в матрицу смежности.
Не нужно.

Добавлено через 3 минуты
Кстати, я бы при реализации ещё обрамил массив фиктивной границей, чтобы не приходилось проверять индексы на принадлежность массиву.

Цитата Сообщение от iRomul Посмотреть сообщение
вызвать рекурсивно поиск для всех вариантов?
Dfs как раз в этом и заключается.

Цитата Сообщение от Igor3D Посмотреть сообщение
До тех пор пока стек не пуст
Ой.. Конечно так можно, но 90%, что так мудрить не надо...
1
Igor3D
1227 / 594 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
03.10.2013, 16:03 6
Цитата Сообщение от Qwertiy Посмотреть сообщение
Ой.. Конечно так можно, но 90%, что так мудрить не надо...
Почему мудрить - зачем нужна рекурсия если легко можно обойтись без нее? Кроме того, стек/очередь дает интересные возможности. Напр мапа сортированная по расстоянию до целевой точки, при большом размере данных это важно
0
Qwertiy
821 / 629 / 100
Регистрация: 20.08.2013
Сообщений: 2,524
03.10.2013, 17:28 7
Цитата Сообщение от Igor3D Посмотреть сообщение
Напр мапа сортированная по расстоянию до целевой точки
Эээ.. Для этого нужен bfs c очередью. Dfs со стеком кратчайшее расстояние не даёт.
Вопрос был, во-первых, о существовании пути, а во-вторых, там явно сказано про dfs.

Цитата Сообщение от Igor3D Посмотреть сообщение
зачем нужна рекурсия если легко можно обойтись без нее?
Зачем нужно обходиться без рекурсии, когда гораздо легче её использовать?
Единственный случай, когда это может понадобиться - это чтобы избежать переполнения стека при очень большом размере поля. Уверен на 90%, что в этой задаче это не требуется.
Если подумать про скорость выполнения. Весьма возможно, что у рекурсии она даже больше, поскольку нет выделения памяти, которое будет происходить, если использовать сишный стек.
Итог: получается более сложный код, который ещё и медленнее работает (правда можно ускорить, использовав не стек, а вектор). Вопрос - зачем оно надо?
0
Igor3D
1227 / 594 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
03.10.2013, 19:10 8
Цитата Сообщение от Qwertiy Посмотреть сообщение
Вопрос - зачем оно надо?
Необязательно жестко следовать постановке ТС. Для нахождения пути этот метод не очень хорош. Гораздо чаще он используется для др целей, напр

- есть 3D модель, пользователь брашем выкрасил неск точек. Нужно "размазать" этот эффект распространяя цвет по поверхности модели от точки к точке. И ото мне надо ломать голову вылетит по стеку или нет?

Ну и вообше, чего спорить о простом, очевидном? Вот напр есть тема "Осреднение" где Ваша критика гораздо более желательна
0
iRomul
159 / 100 / 14
Регистрация: 17.10.2012
Сообщений: 483
Завершенные тесты: 1
03.10.2013, 20:25  [ТС] 9
Спасибо всем за ответы! Но раз уж встал такой вопрос, то
Цитата Сообщение от Igor3D Посмотреть сообщение
Для нахождения пути этот метод не очень хорош.
что в таком случае лучше?
0
Qwertiy
821 / 629 / 100
Регистрация: 20.08.2013
Сообщений: 2,524
03.10.2013, 23:20 10
Цитата Сообщение от iRomul Посмотреть сообщение
что в таком случае лучше?
Всё с методом нормально. Если n<1000 и пишешь на си++. Если .NET, то там размер стека 1М, соответственно ограничения будут поменьше.
Это наиболее частоиспользуемый метод для проверки существования пути - именно из-за простоты его реализации.

Bfs - c очередью - позволяет найти кратчайший путь. Он тоже достаточно легко пишется.
0
iRomul
159 / 100 / 14
Регистрация: 17.10.2012
Сообщений: 483
Завершенные тесты: 1
03.10.2013, 23:27  [ТС] 11
Цитата Сообщение от Qwertiy Посмотреть сообщение
Всё с методом нормально. Если n<1000 и пишешь на си++. Если .NET, то там размер стека 1М, соответственно ограничения будут поменьше.
Это наиболее частоиспользуемый метод для проверки существования пути - именно из-за простоты его реализации.

Bfs - c очередью - позволяет найти кратчайший путь. Он тоже достаточно легко пишется.
Я не знаю, каков размер стека у JS (можно проверить), но в любом случае мне этого будет достаточно. И в завершении

Не по теме:


Какая оценка у BFS с очередью для поиска кратчайших путей? И какова его эффективность по отношению в Алг. Дейкстры?

0
Qwertiy
821 / 629 / 100
Регистрация: 20.08.2013
Сообщений: 2,524
03.10.2013, 23:45 12
Цитата Сообщение от iRomul Посмотреть сообщение
Я не знаю, каков размер стека у JS (можно проверить)
var i=0; (function x() { ++i, x() })(); : 16384 - Опера 12, 17838 - Нихром.

Цитата Сообщение от iRomul Посмотреть сообщение
Какая оценка у BFS с очередью для поиска кратчайших путей?
Bfs и dfs O(n+m) в случае списка смежности, O(n^2) в случае матрицы смежности.

Цитата Сообщение от iRomul Посмотреть сообщение
И какова его эффективность по отношению в Алг. Дейкстры?
У Дейкстры O(n^2).
Но так сравнивать некорректно, поскольку дейкстра применяется для взвешенных графов (при выполнении трёх условий), а bfs для невзвешенных, а также 0-1 графов.

* n - число вершин, m - число рёбер.
2
iRomul
159 / 100 / 14
Регистрация: 17.10.2012
Сообщений: 483
Завершенные тесты: 1
05.10.2013, 13:37  [ТС] 13
Что-то я намудрил, но намудрил, видимо, неправильно. Моя функция либо никогда не находит выход, либо (я так понял, что в этот момент находит) Stack Overflow.
Код:
Javascript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
function isAttainableBFS(matrix, qx, qy) {
 
    var up = matrix[qx][qy+1];
    var left = matrix[qx-1][qy];
    var right = matrix[qx+1][qy];
    
    if((up == CELL.exit) && (left == CELL.exit) && (right == CELL.exit)) return true;
    
    if(up != CELL.wall && up != CELL._visited) {
        matrix[qx][qy] = CELL._visited;
        return(isAttainableBFS(matrix, qx, qy+1));
    }
        
    if(right != CELL.wall && right != CELL._visited) {
        matrix[qx][qy] = CELL._visited;
        return isAttainableBFS(matrix, qx+1, qy);
    }
    
    if(left != CELL.wall && left != CELL._visited)  {
        matrix[qx][qy] = CELL._visited;
        return isAttainableBFS(matrix, qx-1, qy);
    }
    
    return false;
    
}
0
Qwertiy
821 / 629 / 100
Регистрация: 20.08.2013
Сообщений: 2,524
05.10.2013, 20:57 14
Return надо делать не так. Не видно стирания клеток, тоэтому и вечная рекурсия возможна. И вообще, код надо проще писать - слишком много if'ов.

Добавлено через 54 секунды
Хотя нет, пометки вижу. Но return'ы всё равно кривые.
0
Igor3D
1227 / 594 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
05.10.2013, 21:29 15
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool Lookup( int matr[N][N], int visited[N][N], int x, int y )
{
  if (x == targetX && y == targetY) return true;
  visited[x][y] = true;
  for (int i = x - 1; i <= x + 1; ++i) {
   if (i < 0 || i >= N) continue;
   for (int j = y - 1; j <= y + 1; ++j) {
    if (j < 0 || j >= N) continue;
    if (matr[i][j] || visited[i][j]) continue;
    if (Lookup(matr, visited, i, j)) return true;
   }
  }
  return false;
}
0
Qwertiy
821 / 629 / 100
Регистрация: 20.08.2013
Сообщений: 2,524
06.10.2013, 01:05 16
Javascript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
function check(f) {
  var dx=[-1,0,0,1], dy=[0,-1,1,0], q, w;
  
  for(q=0; q<f.length; ++q)
    for(w=0; w<f[q].length; ++w)
      if(f[q][w]===2)
        return dfs(q,w);
  
  function dfs(x, y) {
    var q, x1, y1;
 
    for(q=0; q<4; ++q)
      if(f[x1=x+dx[q]])
        switch(f[x1][y1=y+dy[q]]) {
          case 3:
            return true;
          case 0:
            f[x1][y1]=4;
            if(dfs(x1,y1))
              return true;
        }
    
    return false;
  }
}
 
check([[1,1,1,3,1],
       [1,1,1,0,1],
       [1,1,0,0,1],
       [1,0,0,1,1],
       [1,2,1,1,1]]);
1
06.10.2013, 01:05
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.10.2013, 01:05

Не работает поиск в глубину (DFS)
Вот код (заполнен для ориентированного графа 0 2 | + +/ 1--+3--+4 | +...

Реализация обхода графа в глубину (DFS)
Всем здравствуйте! Задача такова реализация обхода не взвешенного дерева,...

Решение задачи "Пятнашки"/"Восьмёрки" методом поиска в глубину (DFS)
Может кто-то сталкивался с решение данной задачи? Не могу осмыслить алгоритм...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
16
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru