Визуализация алгоритма обхода графа и поиска пути в Python
Введение
Проблемы кодирования на основе графиков обычно возникают в ходе технических интервью среди технологических компаний, таких как Amazon, Google и Facebook.
В этой статье представлены предложения проекта Python для изучения алгоритмов обхода графа. Я завершил этот проект несколько лет назад, и идея возникла у TheBartR и Clément Mihailescu.
Описание Проекта
Ориентированные и неориентированные графы
Методы поиска пути — это алгоритмы поиска по графу, которые изучают маршруты между узлами. то есть цель алгоритма поиска пути состоит в том, чтобы перейти от начального узла к конечному узлу и отследить путь принятые для достижения цели.
В этом проекте я реализовал четыре ключевых алгоритма; Поиск в ширину, Поиск в глубину, Дейкстры и A*(звездочка). В Интернете доступно множество отличных ресурсов, которые четко описывают эти фундаментальные концепции.
Думайте о графе как о сети из узлов. Например, на рисунке 1 показаны неориентированный и ориентированный графы.
- Неориентированныеграфы имеют связи с нет направления. Между каждым ребром существует двусторонняя связь.
- Направленные графы имеют связи между вершинами с помощью стрелок, указывающих, каким образом информация может перемещаться по ребрам.
Сетка фактически служит сетью узлов. По мере исследования необходимо определить прошлое, настоящее и будущее State узлов. Gist 1 показывает enum, который инкапсулирует все возможные значения состояния.
Gist 2 дает код Python, содержащий класс Node. Основные свойства включают его положение в сетке, список окружающих элементов и текущий State.
Алгоритмы
Поиск в ширину (BFS) и Поиск в глубину (DFS) — это фундаментальные алгоритмы обхода графа.
BFS обходит все узлы на текущем уровне, прежде чем перейти к следующему уровню. В Gist 3 представлена реализация на Python итеративного алгоритма BFS, используемого для поиска пути между двумя узлами в сетке.
Проблемы на собеседовании по кодированию часто могут включать любой из этих методов в качестве анализа первого шага. На рис. 2 показан алгоритм BFS в действии.
DFS проходит через узлы насколько это возможно, пока не достигнет узла, в котором нет непосещенных ближайших узлов. Решатель DFS Python предоставляется в Gist 4.
О сравнении этих алгоритмов читайте в разделе Разница между BFS и DFS. DFS визуализирована на рисунке 3.
Кратчайший путь
Дейкстры и A* находят кратчайший путь, то есть вычисляют самый краткий маршрут между парой узлов. . Таким образом, они определяют оптимальные пути между начальным и конечным узлами.
Практические варианты использования методов поиска кратчайших маршрутов, таких как A*, включают планирование логистики и IP-маршрутизацию.¹
Рисунок 4 иллюстрирует метод Дейкстры. На холсте существуют взвешенные узлы, что добавляет еще один уровень сложности в технику. Предыдущие методы, BFS и DFS, не учитывали веса.
Алгоритм A* улучшает процесс Дейкстры, добавляя дополнительную информацию с помощью эвристической функции, которая определяет, какие пути исследовать дальше. Примером такой эвристики является евклидово расстояние между начальной и конечной точками.
Эта оптимизация приводит к более быстрому поиску кратчайших путей. Алгоритм A* может найти кратчайшие пути между отдельными парами местоположений, для которых известны GPS-координаты. На рис. 5 показана эффективность этого метода в гораздо более обширной сети, чем в других примерах.
Алгоритмы A* и Дейкстры более или менее одинаковы, за исключением того, что A* использует эвристику. Следовательно, оба этих алгоритма реализованы в одном и том же class с flag, чтобы указать, какой из них желательно использовать. См. код в Gist 5 для обоих методов.
Заключение
В этой статье представлен код Python и визуализации четырех алгоритмов обхода графа. Понимание этих механизмов полезно для инженеров и студентов компьютерных наук, поскольку они часто появляются на собеседованиях по программированию.
Если вас заинтересовала идея этого проекта, ознакомьтесь с визуализацией алгоритма сортировки. Эти проекты будут полезны всем, кто интересуется программированием и информатикой.
Я постоянно ссылаюсь на Python, потому что это мой предпочтительный язык программирования. Однако, если у вас есть навыки владения другим языком, эти проекты можно выполнять на любом языке, который вы предпочитаете.
Анимации — отличное дополнение к презентациям портфолио. Он демонстрирует результаты проекта и иллюстрирует понимание того, как реализовать алгоритмы. код для этого проекта хранится на GitHub.
Если вы интересуетесь Python, инженерией и наукой о данных, не стесняйтесь подписаться и ознакомиться с другими моими статьями.
Надеюсь, вы нашли для себя что-то полезное. Спасибо, что прочитали.
Рекомендации
[1] Глава 4. Алгоритмы поиска путей и графического поиска — Графовые алгоритмы Марка Нидхэма, Эми Э. Ходлер
