Первой попыткой описания поиска в глубину считают стратегию прохождения лабиринтов французского математика XIX века Шарля Пьера Тремо. Через сто лет Джон Хопкрофт и Роберт Тарьян свели обход графа к линейному времени: 14 вершин метод проходит за 13 шагов и 3 отката. Основатель «Школы траблшутеров» Олег Брагинский и ученик Владислав Иванов изучают старинный метод исследования графов.
Шарль Тремо предложил простой способ выхода из лабиринта: движемся по коридорам, оставляя отметки о пути. При достижении тупика «закрываем» дорогу как изученную и возвращаемся назад до предшествующей развилки. Входить в коридор с двумя отметками запрещено – каждый проход оставляет одну. Принцип бэктрекинга за век до его формального описания.
В 1950-х Клод Шеннон, отец информационного века, формализовал задачу лабиринтов для компьютеров: его электромеханическая мышь Тесей сама находила выход и запоминала маршрут. Через 20 лет Джон Хопкрофт и Роберт Тарьян объединились для развития идей Тремо. В 1972 году Тарьян опубликовал статью «Depth-first search and linear graph algorithms», которая стала основополагающей.
Алгоритм исследует ветку графа, пока не упрётся в финальную вершину. Затем возвращается на предыдущий шаг и выполняет проверку: есть ли пути до неизученных вех? Если ответ «да», проходит дальше. В отрицательном случае откатывается до тех пор, пока не обнаружит неизвестный ранее путь к новым точкам.
В отличие от собрата, работающего с шириной, поиск в глубину не создаёт очередей, а взаимодействует со стеком и «пожирает» меньший объём памяти. Но поиск в ширину зачастую обнаруживает кратчайшие пути, чем не может похвастаться глубинный поиск.
Поиск в глубину просто реализовать на любом языке программирования. Он играючи справляется с глубокими графами, которые часто встречаются в машинном обучении. Однако при реализации через рекурсию на длинных дистанциях может происходить переполнение стека.
Разберём метод на примере. Дан граф из 14 вершин: некоторые точки связаны рёбрами, ориентира движения нет, веса неважны (рисунок 1). Работу начинаем с вершины 1.
Рис. 1. Начальный граф, точка старта – вершина 1
Двигаемся случайно. Пройдём вершины 2, 11 и 9, направимся в точку 3 (рисунок 2).
Рис. 2. Прохождение графа до вершины 3
В вехе 3 оценим диспозицию: точка 1 уже пройдена – с неё начинали, значит, по правилу алгоритма выбираем направление на 4 (рисунок 3). Ребро 3–1 запоминаем как обратное: новых вершин оно не открывает.
Рис. 3. Прохождение графа до вершины 4
Из четвёрки заглядываем в шестёрку. Оказываемся в тупике, следовательно, делаем шаг назад (рисунок 4). Это первый откат маршрута: вершина 6 больше не понадобится. Теперь дорога лежит в вершину 5. В ней находим невостребованный путь до 1 и уходим в 12, отметив ребро 5–1 как обратное.
Рис. 4. Бэктрекинг из вершины 6 до 4
После 12 перемещаемся в 10 и 13. В последней вершине вновь есть путь до известной точки 12, поэтому переходим в 14. Вершина 14 соседствует с изученной девяткой, значит, отступаем назад до 13.
Веха 13 тоже не даёт новых путей – возвращаемся в 10. И уже из десятки идём в восьмёрку. Здесь повторяется ситуация: одна узнаваемая девятка и анонимная семёрка. Выбор очевиден, итоговый граф перед вами (рисунок 5).
Рис. 5. Изученный в глубину граф
Для графа из 14 вершин выявили 5 рёбер, соединяющих знакомые точки, и совершили 3 отката. Обход занял 13 шагов – по одному на каждое ребро дерева поиска.
Временная сложность метода:
T = O(V + E),
где T – время работы, V – число вершин, E – количество рёбер.
Алгоритм поиска в глубину подойдёт, если требуется проверить граф на связность, выявить циклы, провести топологическую сортировку. Также метод используется при поиске файлов на диске, построении пути до точки, программировании роботов, для анализа сетей и взаимодействий людей, оптимизации компиляторов и выявления критических узлов.
Какой алгоритм выбрать?
Ширина предпочтительнее для поиска кратчайшего пути в невзвешенном графе и при знании, что решение близко к корню. Глубина подскажет все маршруты и сработает при комбинациях и перестановках, окажется полезной на множественных уровнях и при запросе на циклы или топологическую сортировку.
В чём преимущество поиска в глубину?
Алгоритм эффективнее работает с памятью, требуя меньше ресурсов для хранения промежуточных результатов. Он легко реализуется, проявляет гибкость и универсальность. Его стихия – небоскрёбы из точек.
Сколько проходов делает алгоритм?
Каждую вершину алгоритм посещает один раз, а каждое ребро проверяет дважды – с обоих концов. Поэтому количество заходов зависит исключительно от числа точек и связей между ними.
Где поиск в глубину проигрывает?
Для нахождения кратчайших путей выбирайте поиск в ширину. При отсутствии отметок посещённых вершин алгоритм зациклится. Любовь к глубине окажется пагубной, если дерево бесконечно раскрывается листьями, – такое встречается в машинном обучении. В базовой версии порядок обхода случайный.
Рекурсия или явный стек?
Рекурсивная запись короче: вызов функции сам хранит пройденный путь и точку возврата, а код умещается в десяток строк. Но глубина вызовов ограничена размером системного стека, и на длинных ветках программа падает с ошибкой переполнения. Явный стек в коде занимает больше места, зато его размер вы задаёте сами и наращиваете по необходимости. На графах глубиной в тысячи вершин выбирайте вторую форму, на компактных задачах – первую.
Что запомнить?
Поиск в глубину погружается в ветку, пока не достигнет тупика. Ширина двигается слоями. Глубина «жрёт» мало памяти и работает быстро. Может возвращаться на предыдущие шаги для выявления неизученных путей.
Поиск в глубину – базовый кирпич десятков алгоритмов: на нём стоят топологическая сортировка, поиск компонент связности и мостов, проверка графа на двудольность. Освоив обход одной картинки из 14 вершин, вы получаете инструмент для сетей любого размера.
Рис. 6. Пять шагов поиска в глубину и цифры разобранного графа