Подборка визуализаций по алгоритмам поиска

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

Список рассматриваемых алгоритмов:

• алгоритм поиска A*;
• алгоритм поиска Jump Point Search;
• алгоритм обнаружения циклических схем в направленном графе;
• алгоритм поиска в глубину (Depth First Search);
• алгоритм поиска в ширину (Breadth First Search);
• алгоритм Дейкстры.

Алгоритм поиска A*

Алгоритм поиска по первому наилучшему совпадению на графе, который находит маршрут с наименьшей стоимостью от одной вершины (начальной) к другой (целевой, конечной).

A* пошагово просматривает все пути, ведущие от начальной вершины в конечную, пока не найдёт минимальный. Как и все информированные алгоритмы поиска, он просматривает сначала те маршруты, которые «кажутся» ведущими к цели. С исходным кодом алгоритма вы сможете ознакомиться на дополнительном ресурсе.

Алгоритм поиска Jump Point Search (JPS)

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

Более подробно ознакомиться с работой этого алгоритма вы сможете в развёрнутой статье, посвящённой ему. С кодом этого алгоритма предлагаем ознакомиться на дополнительном ресурсе.

Алгоритм обнаружения циклических схем в направленном графе

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

С исходным кодом алгоритма и его интерактивной презентацией вы сможете ознакомиться в источнике.

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

Стратегия алгоритма состоит в том, чтобы идти «вглубь» графа, насколько это возможно. Алгоритм поиска в глубину описывается рекурсивно: перебираются все исходящие из рассматриваемой вершины рёбра. Если ребро ведёт в вершину, которая не была рассмотрена ранее, то алгоритм нужно запустить от неё, а после вернуться и продолжить перебирать рёбра. Возврат происходит в том случае, если в рассматриваемой вершине не осталось рёбер, которые ведут в нерассмотренную вершину. Если после завершения алгоритма не все вершины были рассмотрены, то необходимо запустить алгоритм от одной из нерассмотренных вершин.

Давайте рассмотрим работу алгоритма на анимации ниже. Как видите, путь «вглубь» графа начинается с вершины A, затем проверяется вершина B, дальше вершины D и E. Таким образом алгоритм проверяет все вершины данной ветви и «возвращается» для исследования другой ветви. Алгоритм заканчивает работу на вершине A, потому что вершина D уже была проверена раннее. С кодом алгоритма вы сможете ознакомиться в статье, посвящённой ему.

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

Поиск в ширину (BFS) работает путём просмотра отдельных уровней графа, начиная с узла-источника. Стоит отметить, что этот алгоритм использует метод полного перебора, в котором не используется дополнительная информация о состояниях, кроме той, которая представлена в определении задачи.

Примечание Вы можете экспериментировать с этим алгоритмом в специальном визуализаторе.

Примечание граф — это, говоря простыми словами, множество точек, называемых вершинами, соединенных какими-то линиями, называемыми рёбрами (необязательно все вершины соединены). Можно представлять себе как города, соединённые дорогами.

Вы сможете ознакомиться с исходным кодом и интерактивной презентацией алгоритма в источнике.

Алгоритм Дейкстры

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

Примечание Вы можете экспериментировать с этим алгоритмом в специальном визуализаторе.

Вы сможете ознакомиться с кодом и интерактивной презентацией алгоритма на специальном ресурсе.

Дополнительные материалы для практики

Также предлагаем вам обратить внимание на интерактивные реализации разных алгоритмов вместе с игровыми механизмами. Все образцы представлены с исходным кодом под лицензией MIT. Этот ресурс будет полезен для программистов, которые также заинтересованы в разработке игр, но не знают, как реализовать или построить правильно тот или иной алгоритм.