Depth-first search - тупик как стратегия поиска пути.

Не так давно рассказывал про BFS алгоритм, который слоями, как лук, накладывается, а сейчас пойдем по другому пути его старшего и более топорного брата - DFS — depth-first search, поиск в глубину.

История начинается раньше BFS. В 1882 французский математик Шарль Тремо описал способ выйти из лабиринта, помечая пройденные проходы — по сути, уже DFS с бэктрекингом, просто без графов и без имени. Формализовали алгоритм на графах только в 1972-м Джон Хопкрофт и Роберт Тарьян, за эту и смежные работы позже получившие премию Тьюринга. Тот же Тарьян попутно придумал на основе DFS алгоритм поиска компонент сильной связности - он до сих пор в учебниках идёт отдельной главой, только я про него не сильно много знаю.

Идея проще, чем звучит и работает строго прямолинейно: цикл вместо очереди, когда заходишь в узел, помечаешь посещённым и сразу лезешь в первого непосещённого соседа, а не откладываешь его на потом, как в BFS. Уткнулся в тупик? Не беда, возвращаешься на уровень выше и пробуешь следующего. В пустом поле он тебе нарисует сначала полоску, а потом пойдет вдоль стены, например.

Насколько он простой, настолько же много у этого алгоритма применений. Топологическая сортировка — тот же порядок, в котором Terraform и Ansible резолвят зависимости ресурсов. Обход ФС, гарбедж коллекторы, решение судоку перебором с откатом — везде один и тот же спуск до упора. Правильно подогнанные решения по выбору следующей ячейки были весами и были основной системой поиска путей в Гарвардских соревнованиях автономных роботов, что, по сути, безумно увлекательное событие само по себе: программируют роботов на колесиках, не зная о том, каким будет лабиринт, роботы на колесиках катаются, применяют свои веса в выборе направлений, а побеждает тот, кто доехал быстрее. Простой кампусный прикол, в котором видно наикрутейшие системы алгоритмических вычислений, которые, зачастую, потом уходят в открытый мир как сильнейшие решения. Даже Veritassium про это целое видео записывал.

А у меня одним из последних решений в реализации были вообще тараканьи бега для заказного проекта в миниапку телеграма еще в 2024 что ли. Там одновременно и генерация лабиринта была через алгоритм, что я описывал ранее(пост про плейграунды посмотри выше) и сами человечки бегали таким алгоритмом, задавая веса через свайпы перед началом движения.

Забавнее всего, что я с ним столкнулся одновременно и раньше и позже в своей истории геймдева: сначала скачивал какие-то примеры на Game Maker с ботами, пытаясь понять, как они думают и ничего не понимал, а потом прыгнул в алгоритмы читать всякое и увидел, что это целый кладезь для создания лабиринтов, данжей или прохода по ним, потому что логика тупорылая, но рабочая как никто. Иногда очень эффектно выглядит, если условия подходящие.