Поиск с углублением

Поиск с углублением (англ. depth-limited search, итеративное углубление, iterative deepening depth-first search, IDDFS) — это стратегия обхода графа или дерева решений в информатике и теории алгоритмов, которая сочетает в себе преимущества поиска в глубину (DFS) и поиска в ширину (BFS). Основная идея заключается в последовательном выполнении поиска в глубину с возрастающим ограничением на максимальную глубину (лимитом), пока не будет найдена целевая вершина (узел) или не будет исчерпано всё пространство состояний. Алгоритм гарантирует нахождение кратчайшего пути (оптимального по числу рёбер) в невзвешенных графах, при этом используя значительно меньше памяти, чем поиск в ширину.

История и развитие

Концепция поиска с углублением возникла как ответ на ограничения классических методов поиска. Поиск в глубину (DFS) прост в реализации и требует памяти порядка O(d), где d — максимальная глубина, но не гарантирует нахождения кратчайшего пути и может зацикливаться в бесконечных графах. Поиск в ширину (BFS) гарантирует оптимальность, но требует памяти O(b^d), где b — коэффициент ветвления, что делает его неприменимым для задач с большим пространством состояний (например, в шахматах или планировании).

В 1970-х годах, с развитием искусственного интеллекта и теории игр, исследователи начали искать компромиссные решения. Одним из первых формальных описаний алгоритма итеративного углубления считается работа Ричарда Корфа (Richard Korf) 1985 года «Depth-First Iterative-Deepening: An Optimal Admissible Tree Search», где он доказал его оптимальность и эффективность для деревьев. Впоследствии алгоритм стал стандартным инструментом в задачах поиска путей, решения головоломок (например, «15-пятнашек» или «Кубика Рубика») и в игровых программах.

Алгоритм работы

Основная процедура

Поиск с углублением реализуется как последовательность вызовов поиска в глубину с ограничением (DLS). На каждом шаге алгоритм задаёт лимит глубины L (начиная с 0 или 1) и запускает DFS, который не углубляется дальше L. Если цель найдена, алгоритм завершается. Если нет — лимит увеличивается на 1, и процесс повторяется.

Псевдокод (упрощённый): ``` function IDDFS(root, goal): for depth = 0 to ∞: result = DLS(root, goal, depth) if result != failure: return result

function DLS(node, goal, depth): if depth == 0 and node == goal: return node if depth > 0: for each child in expand(node): result = DLS(child, goal, depth - 1) if result != failure: return result return failure ```

Особенности реализации

• Отсутствие запоминания посещённых узлов: в классической версии IDDFS не хранит информацию о посещённых узлах между итерациями, что экономит память, но может приводить к повторным вычислениям.
• Ограничение глубины: лимит L предотвращает бесконечное углубление в графах с циклами. Для графов с циклами требуется дополнительная проверка на повторное посещение узла в рамках одной итерации (например, с помощью хранения пути).
• Условие завершения: алгоритм завершается, когда либо найдена цель, либо при очередном увеличении лимита не было найдено ни одного нового узла (что свидетельствует о полном обходе).

Характеристики и сложность

Временная сложность

Временная сложность IDDFS в худшем случае составляет O(b^d), где b — коэффициент ветвления (среднее число потомков узла), d — глубина оптимального решения. Это кажется неэффективным из-за повторных обходов, однако на практике повторные вычисления незначительны: для дерева с b > 1 суммарное число узлов, обработанных за все итерации, составляет примерно b^d * (b/(b-1)). Например, при b=2 и d=10 IDDFS обработает примерно вдвое больше узлов, чем BFS, но при b=10 — всего на 11% больше. Таким образом, асимптотическая сложность совпадает с BFS.

Пространственная сложность

Пространственная сложность IDDFS составляет O(d) — линейная по глубине. Это главное преимущество перед BFS (O(b^d)). Алгоритм хранит только текущий путь от корня до обрабатываемого узла, что позволяет решать задачи с огромным пространством состояний (например, в планировании маршрутов или в играх).

Оптимальность

IDDFS является оптимальным для невзвешенных графов (деревьев), если стоимость пути измеряется числом рёбер. Он гарантированно находит кратчайший путь, так как последовательно увеличивает лимит глубины, и первое найденное решение будет иметь минимальную глубину.

Полнота

Алгоритм полон для конечных графов и для бесконечных деревьев с конечным коэффициентом ветвления. В графах с циклами полнота достигается за счёт ограничения глубины и проверки повторений в рамках одной итерации.

Применение

Искусственный интеллект и игры

• Головоломки: IDDFS широко используется для решения задач, где пространство состояний велико, но глубина решения невелика. Примеры: «Ханойская башня», «15-пятнашки», «Кубик Рубика». В 1990-х годах с помощью IDDFS были найдены оптимальные решения для многих состояний кубика Рубика (до 20 ходов).
• Игровые программы: в шахматах и шашках IDDFS применяется в алгоритмах минимакса с альфа-бета-отсечением для поиска на фиксированную глубину. Итеративное углубление позволяет программе использовать оставшееся время: если время истекло, возвращается результат последнего завершённого поиска.

Поиск путей в графах

• Навигация: в задачах поиска пути в лабиринтах или на картах IDDFS может быть эффективной альтернативой A*, если требуется минимальное использование памяти.
• Планирование: в робототехнике и планировании действий IDDFS применяется для поиска последовательностей операций, особенно когда пространство состояний неограниченно.

Компиляторы и анализ программ

• Символическое выполнение: IDDFS используется для обхода деревьев выполнения программ при поиске ошибок или уязвимостей, где глубина стека вызовов может быть большой, но ограничена.

Сравнение с другими алгоритмами

Поиск в ширину (BFS)

• Память: BFS требует O(b^d) памяти, IDDFS — O(d). Для задач с b=10 и d=10 BFS потребует хранения ~10^10 узлов, что невозможно на обычных компьютерах, тогда как IDDFS обходится сотнями узлов.
• Скорость: IDDFS обычно медленнее BFS на 10-30% из-за повторных обходов, но в задачах с ограниченной памятью он является единственным практичным выбором.

Поиск в глубину (DFS)

• Оптимальность: DFS не гарантирует нахождения кратчайшего пути, IDDFS — гарантирует.
• Полнота: DFS может зацикливаться в бесконечных графах, IDDFS — нет (при правильной реализации с ограничением глубины).

A* и эвристические алгоритмы

• Эвристики: IDDFS не использует эвристические функции, поэтому в задачах с известной эвристикой A или IDA (итеративное углубление A) могут быть быстрее. IDA является гибридом IDDFS и A*, где лимит задаётся не глубиной, а стоимостью пути (f-стоимостью).

Ограничения и критика

• Повторные вычисления: основной недостаток IDDFS — многократный пересчёт одних и тех же узлов на разных итерациях. Для деревьев с большим коэффициентом ветвления это приводит к незначительному замедлению, но для графов с малым b (например, b=2) накладные расходы могут составлять до 100%.
• Неприменимость к взвешенным графам: классический IDDFS не учитывает стоимость рёбер, поэтому для взвешенных графов (например, карт с расстояниями) он не гарантирует оптимальности. В таких случаях используются алгоритмы вроде IDA* или поиска с углублением по стоимости (DLS с весами).
• Зависимость от глубины: алгоритм плохо подходит для задач, где глубина решения неизвестна или очень велика (например, тысячи шагов). В таких случаях предпочтительнее эвристические методы.

Примеры использования

Решение головоломки «15-пятнашек»

Для классической головоломки «15-пятнашек» (4x4) пространство состояний содержит около 10^13 узлов. IDDFS позволяет найти оптимальное решение (минимальное число ходов) для большинства конфигураций за разумное время (от секунд до минут), используя память порядка нескольких килобайт. Например, для случайной конфигурации с глубиной решения 50 ходов IDDFS обработает около 10^7 узлов, что выполнимо на современном компьютере.

Поиск в шахматах

В шахматных программах (например, Stockfish, Deep Blue) итеративное углубление является стандартом. Программа начинает поиск на глубину 1, затем 2, 3 и т.д., пока не истечёт отведённое время. Это позволяет:

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

Интересные факты

• Алгоритм IDDFS иногда называют «поиском с итеративным углублением» (iterative deepening search, IDS). В русскоязычной литературе встречаются термины «итеративное углубление» и «поиск с ограничением глубины».
• В 1990-х годах IDDFS использовался в проекте Deep Blue (компания IBM) для поиска в шахматах, хотя основным алгоритмом был альфа-бета-поиск с итеративным углублением.
• Для задач с непрерывным пространством состояний (например, в робототехнике) существуют модификации IDDFS, работающие с вещественными числами.

Источники

• Корф, Р. (1985). «Depth-First Iterative-Deepening: An Optimal Admissible Tree Search». Artificial Intelligence, 27(1), 97-109.
• Рассел, С., Норвиг, П. (2010). «Искусственный интеллект: современный подход» (3-е изд.). — М.: Вильямс. — Глава 3.
• Кнут, Д. (1997). «Искусство программирования» (Том 1). — М.: Вильямс. — Раздел 2.3.4.
• Седжвик, Р. (2002). «Фундаментальные алгоритмы на C++». — М.: ДиаСофт. — Глава 5.