ВоITи и выITи

Перевод моей статьи с HackerNoon .  В нашем предыдущем посте мы рассмотрели алгоритмы поиска путей в графах, которые по своей сути похожи на решение поиска выхода из лабиринта. Когда я делал карту для проекта Wall-E из прошлой статьи, я наткнулся на варианты построения лабиринтов. И чем больше я читал, тем дальше погружался в большой и увлекательный мир лабиринтов. Ранее я не осознавал всю широту и глубину этой темы, и обнаружил, например, что лабиринты можно классифицировать семью различными способами, каждый из которых можно сгенерировать различными алгоритмами. Кстати, я не нашел ни одной книги, которая бы всесторонне охватывала эту тему, и даже на странице Википедии нет систематического обзора. К счастью, я наткнулся на потрясающий ресурс, который охватывает различные типы и алгоритмы лабиринтов . Я начал изучать различные классификации лабиринтов, включая размерные и гиперразмерные вариации, идеальные лабиринты и уникурсальные (unicursal) лабиринты, плоские и разреженные лабири

  Перевод моей статьи с HackerNoon .   В моем последнем посте я показал способ унификации самых известных алгоритмов обхода графов. Теперь давайте сделаем это более наглядно и рассмотрим различия в производительности. Предистория Несколько лет назад Яндекс организовал конкурс Роботы Курьеры с заманчивым призом: билетом на закрытую конференцию по беспилотным технологиям для профессионалов. Конкурс напоминал игру, в которой участникам нужно было находить оптимальные маршруты на карте и оптимизировать доставку с помощью роботизированных курьеров. Углубляясь в эту тему, я обнаружил, что, несмотря на то, что задача поиска маршрутов уже решена, она продолжает вызывать интерес у профессионального сообщества разработчиков, например, игр. Между 2010 и 2020 годами инженеры сделали значительные оптимизации алгоритма A* , что было особенно полезно для AAA игр с огромными картами. Могу порекомендовать почитать статьи и научные работы из этой сферы. Однако, требования конкурса Яндекс были разра

 Перевод моей статьи с HackerNoon .   Оказывается, что известные алгоритмы BFS, DFS, Дейкстры и А* являются, по сути, вариациями одного и того же алгоритма. Я продемонстрирую это на реальной реализации. Другими словами, можно реализовать универсальную структуру данных, которая может переключаться между этими алгоритмами, не требуя изменений в своих основных компонентах. Хотя существуют некоторые ограничения, исследование этого подхода представляет интерес. Весь рабочий код этих алгоритмов можно найти в моем репозитории GitHub здесь . Я рекомендую экспериментировать с кодом во время чтения этой статьи, так как практический опыт лучше, чем просто теоретическое понимание. Представление графа Рассмотрим граф с 25 узлами, расположенными в виде сетки 5x5, где мы стремимся найти путь от узла 0 в верхнем левом углу до узла 24 в нижнем правом углу:  ``` ( 0  ) - ( 1  ) - ( 2  ) - ( 3  ) - ( 4  )   |        |        |        |        | ( 5  ) - ( 6  ) - ( 7  ) - ( 8  ) - ( 9  )   |        |