практика поиск в ширину

Практика «Поиск в ширину»

Всем привет! Разберём первую практику из «Графов». Перед объяснением самой задачи разберёмся с методом обхода в ширину. Тогда будет гораздо проще сделать задачи, так как этот алгоритм прямо или косвенно фигурирует во всех трёх практиках этой темы.

Обход в ширину

Возьмем код из заметок по лекциям:

Пройдемся по порядку:

1) Именованные константы определяют значения каждой клетки (там пусто, либо стена, либо в этой клетке уже побывали)

2) Далее всё стандартно — каждой клетке лабиринта присваиваются значения из Enum

А вот с 25 строки начинается тот самый алгоритм

3) Создаем очередь, в которую будем класть координаты клетки

4) Добавляем в очередь стартовую точку, откуда начинается обход в ширину (26 строка)

5) И пока очередь не опустеет делаем следующие действия (27-41 строки):

· Достаем из очереди точку и проверяем, не выходит ли она за пределы нашего поля лабиринта

· Далее проверяем, нет ли по указанным координатам стены, либо же не посещали ли мы эту клетку

· Помечаем клетку как посещённую

·Добавляем соседей клетки в очередь

И таким образом, делаем N количество раз эти действия, пока не обойдем весь лабиринт.

Практика

От нас требуется почти то же самое, что и в лекции. Отличия в том, что нужно обойти лабиринт по сундукам и вернуть путь в виде односвязного списка. Посмотрим на него:

Все помнят его по CVS?) Есть текущее значение — это наша клетка в лабиринте и ссылка на предыдущую клетку.

Алгоритм действий:

1) Создаем список для того, чтобы добавлять туда уже посещенные клетки, а потом проверять, посещали ли мы эту клетку (операция проверки должна выполнятся за O(1)). Подумайте, какой список может пригодиться

2) У нас даны координаты сундуков в лабиринте. При ленивом возвращении из метода SinglyLinkedList, необходимо проверять, содержится ли данный сундук в этой клетке. Поэтому сохраним координаты сундуков в каком-нибудь списке (проверка также за O(1)).

4) Указываем, что start точку мы посетили

5) Далее выполняем стандартный алгоритм обхода клеток лабиринта (как в строках 27-41) при этом добавляя в посещенные текущую клетку. Добавляем в очередь соседей текущей точки. (SinglyLinkedList-указываем новую точку и ссылку на предыдущую)

6) В самом цикле while каждый раз достаем SinglyLinkedList

из очереди и проверяем, не содержится ли сундук по заданным координатам, если содержится, то лениво возвращаем данный SinglyLinkedList

. Так как это односвязный список — это и будет путь от start до сундука

Завершение традиционное, делаем всё максимально сами, чтобы антиплагиат не ругался.

Если есть ошибки — орфографические или фактические — пишите в комментарии, лучше указывая блок, в котором вы их обнаружили. Так будет проще редактировать.

Источник

Поиск в ширину (BFS) на С#

Сразу скажу, что статья больше подойдёт людям, желающим познакомиться с поиском в ширину, и новичкам, осваивающим программирование. К тому же, когда мне понадобился этот метод, я нигде не нашёл наглядного рабочего примера на C#.

Устно об алгоритме:

Разберём алгоритм на произвольном графе (для простоты примера рёбра не имеют вес).

Последовательность алгоритма заключается в следующим:

1. Выбирается произвольно вершина графа (отмечается серым).
2.Последовательно рассматриваются вершины (так же отмечаются серым), связанные с нашей первой вершиной (после этого она становится не серой, а чёрной).
3. Выполняется пункт 2 для отмеченных (серых) вершин до тех пор, пока все вершины не будут закрашены чёрным.

Теперь тоже самое, но более техническим языком:
1. Выбирается произвольная вершина в графе и помещается в очередь.
2. В очередь помещаются все вершины графа смежные с уже находящейся в очереди вершиной, после чего эта вершина выталкивается из очереди.
3. Выполняется пункт 2 для всех вершин, находящихся в очереди.

Теперь перейдём непосредственно к коду (C#):
В качестве графа мы будем использовать массив, программировать будем на консоли (для примера достаточно будет и её). К слову, в примере будем использовать ориентированный граф.

Зададим начальные переменные и заполним наш массив.

g — это массив массивов, где первый индекс определяет нашу вершину с которой мы работаем, а второй массив определяет индексы вершин, с которыми наша вершина связана и не связана (если значение равно 0 — не связана, следовательно, если 1 — связана). То есть, например g[1][5] = 0, означает, что от первой к пятой вершины нет связи (но так как граф ориентированный, то матрица смежности будет не симметричной, следовательно если g[1][5] = 0, то это не означает что и g[5][1] = 0).

used — логический массив, в который мы будем заносить посещённые вершины.

Идём далее, собственно, сам алгоритм в действии:

while — будет выполняться до тех пор, пока очередь не опустеет. В начале каждой итерации присваиваем переменной u значение выталкиваемого элемента очереди.

for — цикл, проходящий по всем вершинам. В нём для начала проверяем нашу вершину на наличие у неё смежных вершин, если есть и если такая вершина не добавлена в массив посещённых вершин (массив used), то мы её туда добавляем, а так же добавляем в нашу очередь.

Собственно вот он весь алгоритм. Да, пожалуй далеко без изысков, и можно сделать куда лучше, но пишу статью исключительно для ознакомительных целей, надеясь, что кому-то, кто так же, как когда-то и я, искал наглядные примеры, она поможет.

Вот примерно как должна получиться программа:

Источник

Обход графа: поиск в глубину и поиск в ширину простыми словами на примере JavaScript

Доброго времени суток.

Что такое обход графа?

Простыми словами, обход графа — это переход от одной его вершины к другой в поисках свойств связей этих вершин. Связи (линии, соединяющие вершины) называются направлениями, путями, гранями или ребрами графа. Вершины графа также именуются узлами.

Двумя основными алгоритмами обхода графа являются поиск в глубину (Depth-First Search, DFS) и поиск в ширину (Breadth-First Search, BFS).

Несмотря на то, что оба алгоритма используются для обхода графа, они имеют некоторые отличия. Начнем с DFS.

Поиск в глубину

DFS следует концепции «погружайся глубже, головой вперед» («go deep, head first»). Идея заключается в том, что мы двигаемся от начальной вершины (точки, места) в определенном направлении (по определенному пути) до тех пор, пока не достигнем конца пути или пункта назначения (искомой вершины). Если мы достигли конца пути, но он не является пунктом назначения, то мы возвращаемся назад (к точке разветвления или расхождения путей) и идем по другому маршруту.

Давайте рассмотрим пример. Предположим, что у нас есть ориентированный граф, который выглядит так:

Мы находимся в точке «s» и нам нужно найти вершину «t». Применяя DFS, мы исследуем один из возможных путей, двигаемся по нему до конца и, если не обнаружили t, возвращаемся и исследуем другой путь. Вот как выглядит процесс:

Здесь мы двигаемся по пути (p1) к ближайшей вершине и видим, что это не конец пути. Поэтому мы переходим к следующей вершине.

Мы достигли конца p1, но не нашли t, поэтому возвращаемся в s и двигаемся по второму пути.

Достигнув ближайшей к точке «s» вершины пути «p2» мы видим три возможных направления для дальнейшего движения. Поскольку вершину, венчающую первое направление, мы уже посещали, то двигаемся по второму.

Мы вновь достигли конца пути, но не нашли t, поэтому возвращаемся назад. Следуем по третьему пути и, наконец, достигаем искомой вершины «t».

Так работает DFS. Двигаемся по определенному пути до конца. Если конец пути — это искомая вершина, мы закончили. Если нет, возвращаемся назад и двигаемся по другому пути до тех пор, пока не исследуем все варианты.

Мы следуем этому алгоритму применительно к каждой посещенной вершине.

Необходимость многократного повторения процедуры указывает на необходимость использования рекурсии для реализации алгоритма.

Заметка: этот специальный DFS-алгоритм позволяет проверить, возможно ли добраться из одного места в другое. DFS может использоваться в разных целях. От этих целей зависит то, как будет выглядеть сам алгоритм. Тем не менее, общая концепция выглядит именно так.

Анализ DFS

Давайте проанализируем этот алгоритм. Поскольку мы обходим каждого «соседа» каждого узла, игнорируя тех, которых посещали ранее, мы имеем время выполнения, равное O(V + E).

Краткое объяснение того, что означает V+E:

V — общее количество вершин. E — общее количество граней (ребер).

Может показаться, что правильнее использовать V*E, однако давайте подумаем, что означает V*E.

V*E означает, что применительно к каждой вершине, мы должны исследовать все грани графа безотносительно принадлежности этих граней конкретной вершине.

С другой стороны, V+E означает, что для каждой вершины мы оцениваем лишь примыкающие к ней грани. Возвращаясь к примеру, каждая вершина имеет определенное количество граней и, в худшем случае, мы обойдем все вершины (O(V)) и исследуем все грани (O(E)). Мы имеем V вершин и E граней, поэтому получаем V+E.

Далее, поскольку мы используем рекурсию для обхода каждой вершины, это означает, что используется стек (бесконечная рекурсия приводит к ошибке переполнения стека). Поэтому пространственная сложность составляет O(V).

Теперь рассмотрим BFS.

Поиск в ширину

BFS следует концепции «расширяйся, поднимаясь на высоту птичьего полета» («go wide, bird’s eye-view»). Вместо того, чтобы двигаться по определенному пути до конца, BFS предполагает движение вперед по одному соседу за раз. Это означает следующее:

Вместо следования по пути, BFS подразумевает посещение ближайших к s соседей за одно действие (шаг), затем посещение соседей соседей и так до тех пор, пока не будет обнаружено t.

Чем DFS отличается от BFS? Мне нравится думать, что DFS идет напролом, а BFS не торопится, а изучает все в пределах одного шага.

Далее возникает вопрос: как узнать, каких соседей следует посетить первыми?

Для этого мы можем воспользоваться концепцией «первым вошел, первым вышел» (first-in-first-out, FIFO) из очереди (queue). Мы помещаем в очередь сначала ближайшую к нам вершину, затем ее непосещенных соседей, и продолжаем этот процесс, пока очередь не опустеет или пока мы не найдем искомую вершину.

Анализ BFS

Может показаться, что BFS работает медленнее. Однако если внимательно присмотреться к визуализациям, можно увидеть, что они имеют одинаковое время выполнения.

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

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

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

Аналогии из реальной жизни

Если приводить аналогии из реальной жизни, то вот как я представляю себе работу DFS и BFS.

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

Упрощенная версия выглядит так:

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

Упрощенная версия выглядит так:

Выводы

Источник

Практика поиск в ширину

Практики «Поиск в ширину», «Вынести клад!» и «Поделить территорию!»

Репозиторий содержит решения этой, этой и этой задачи с ulearn.me. Задачи прошли код-ревью у преподавателя (баллы: 50/50, 100/100, 50/50). Все решения курса на максимальный балл также выложены в других репозиториях. Ветка unsolved содержит изначальный проект.

Практика «Поиск в ширину»

Для этого в классе BfsTask нужно реализовать поиск в ширину с указанной сигнатурой. Кстати, он вам понадобится и для следующей задачи!

После корректного выполнения задания, можно будет запустить проект. Кликнув на пустую ячейку вы увидите найденный вашим алгоритмом путь.

Практика «Вынести клад!»

Подготовка закончилась и вы в настоящем лабиринте с сокровищами! Сил хватит только на один сундук и то еле-еле. Найдите кратчайший путь из начальной точки до выхода, проходящий через хотя бы один сундук.

После выполнения этого задания, при запуске проекта можно увидеть визуализацию пути. Наслаждайтесь найденными сокровищами!

Эту задачу можно элегантно решить без циклов, используя LINQ.

Практика «Поделить территорию!»

Оказалось, что в лабиринте есть и другие охотники за сокровищами. Естественно, кто первый доберется до сундука, тот его и заберет себе.

Неплохо бы знать, кто из соперников до каких клеток лабиринта успеет добраться быстрее других.

В классе RivalsTask реализуйте функцию разделяющую карту между игроками.

Нужно определить, до каких из клеток карты каждый игрок сможет дойти быстрее, вне зависимости от тактики остальных. Ходят игроки по очереди, начиная с первого.

Сделайте так, чтобы все тесты в классе Rivals_Should проходили.

После выполнения этого задания, при запуске проекта можно увидеть визуализацию процесса раздела карты.

Источник

Поиск в ширину (Breadth first search, BFS)

Алгоритм BFS

Стандартная реализация ВFS помещает каждую вершину графа в одну из двух категорий:

Алгоритм работает следующим образом:

Граф может иметь две разные несвязанные части, поэтому, чтобы убедиться, что мы покрываем каждую вершину, мы также можем запустить алгоритм BFS на каждом узле.

Пример BFS

Давайте посмотрим, как алгоритм «поиска в ширину» работает на примере. Мы используем неориентированный граф с 5 вершинами.

Мы начнем с вершины 0, алгоритм BFS начинается с помещения его в список посещенных и размещения всех смежных вершин в стеке.

Затем мы посещаем элемент в начале очереди, то есть 1, и переходим к соседним узлам. Так как 0 уже был посещен, мы посещаем 2.

У вершины 2 есть соседняя не посещенная вершина 4, поэтому мы добавляем ее в конец очереди и посещаем 3, которая находится в начале очереди.

В очереди остается только 4, поскольку единственный соседний узел с 3, то есть 0, уже посещен. Мы посещаем вершину 4.

Поскольку очередь пуста, мы завершили обход в ширину графика.

BFS псевдокод

Код BFS

Код для алгоритма «поиска в ширину» с примером показан ниже. Код был упрощен, поэтому мы можем сосредоточиться на алгоритме, а не на других деталях.

BFS в C

BFS в C++

BFS Java код (Java code)

BFS в Python

Рекомендуем хостинг TIMEWEB

Рекомендуемые статьи по этой тематике

Источник