Поиск с возвратом

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

История

Идея поиска с возвратом восходит к работам математиков XVIII—XIX веков, в частности, к задаче о ходе коня (задача об обходе шахматной доски конём), которую исследовал Леонард Эйлер в 1759 году. Однако термин «backtracking» был введён американским математиком Дерриком Генри Лемером в 1950-х годах в контексте задач комбинаторного анализа. В 1960-х годах метод получил широкое распространение в программировании благодаря работам Роберта Флойда и Джона Маккарти. В СССР алгоритмы поиска с возвратом изучались в рамках курсов дискретной математики и программирования, в частности, в трудах А. А. Маркова и Ю. И. Журавлёва.

Принцип работы

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

Формально алгоритм можно описать следующим образом:

1. Определить пространство поиска — множество всех возможных частичных решений.
2. Выбрать начальное частичное решение (обычно пустое).
3. Проверить, является ли текущее частичное решение полным и допустимым. Если да — сохранить его как решение.
4. Если частичное решение не может быть расширено до полного (например, из-за нарушения ограничений), выполнить возврат (backtrack) — отменить последний добавленный элемент.
5. Если есть нерассмотренные варианты на текущем уровне, выбрать следующий кандидат и перейти к шагу 3.
6. Повторять до тех пор, пока все варианты не будут исчерпаны.

Отсечение (pruning)

Для повышения эффективности поиска с возвратом часто используется отсечение — отказ от рассмотрения ветвей, которые заведомо не могут привести к решению. Например, в задаче о ферзях (расстановка 8 ферзей на шахматной доске так, чтобы они не атаковали друг друга) отсечение происходит, если очередной ферзь оказывается под боем уже поставленных. Отсечение может быть реализовано с помощью эвристик, таких как эвристика наименьшего оставшегося домена (MRV) в задачах удовлетворения ограничений.

Классификация

Поиск с возвратом можно классифицировать по нескольким признакам:

По способу обхода

• Рекурсивный поиск с возвратом — использует рекурсивные вызовы функций для каждого уровня дерева. Наиболее распространённый вариант.
• Итеративный поиск с возвратом — использует явный стек для хранения текущего состояния. Применяется в языках без поддержки рекурсии или для избежания переполнения стека.

По типу задачи

• Задачи комбинаторной оптимизации — поиск наилучшего решения среди всех допустимых (например, задача коммивояжёра).
• Задачи удовлетворения ограничений — поиск любого допустимого решения (например, судоку, раскраска графа).
• Задачи перечисления — нахождение всех возможных решений (например, все перестановки или подмножества).

По наличию эвристик

• Чистый поиск с возвратом — без дополнительных эвристик, полный перебор.
• Поиск с отсечением — с использованием эвристик для сокращения пространства поиска.

Применение

Поиск с возвратом широко используется в различных областях:

Комбинаторика

• Генерация всех перестановок, сочетаний и подмножеств.
• Решение задачи о рюкзаке (0-1 knapsack problem) — поиск подмножества предметов с максимальной ценностью при ограничении на вес.

Головоломки и игры

• Решение судоку — заполнение сетки 9×9 цифрами от 1 до 9 с учётом ограничений по строкам, столбцам и блокам.
• Задача о ходе коня — обход шахматной доски конём, посещающим каждую клетку ровно один раз.
• Задача о восьми ферзях — расстановка 8 ферзей на доске 8×8.
• Кроссворды и лабиринты — поиск пути от начальной до конечной точки.

Теория графов

• Поиск всех гамильтоновых циклов — циклов, проходящих через каждую вершину графа ровно один раз.
• Раскраска графа — назначение цветов вершинам так, чтобы смежные вершины имели разные цвета.
• Поиск клик — полных подграфов заданного размера.

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

• Планирование действий в системах искусственного интеллекта (например, в классическом планировщике STRIPS).
• Решение задач логического вывода, таких как задача о волке, козе и капусте.

Криптография

• Взлом простых шифров, например, подбор ключа методом перебора с отсечением.

Примеры

Задача о восьми ферзях

Классический пример поиска с возвратом. На шахматную доску размером 8×8 необходимо расставить 8 ферзей так, чтобы ни один ферзь не атаковал другого. Алгоритм начинает с первой строки и поочерёдно ставит ферзя в каждую колонку. Если после установки ферзя в текущую позицию он оказывается под боем уже поставленных, алгоритм отменяет установку и пробует следующую колонку. Если все колонки в строке перебраны, алгоритм возвращается на предыдущую строку. Решение достигается, когда все 8 ферзей успешно расставлены. Существует 92 различных решения, не считая симметричных.

Решение судоку

Для судоку размером 9×9 поиск с возвратом работает следующим образом: начиная с первой пустой клетки, алгоритм пробует вставить цифру от 1 до 9. Если цифра не нарушает правила судоку (не повторяется в строке, столбце и блоке 3×3), алгоритм переходит к следующей пустой клетке. Если ни одна цифра не подходит, алгоритм возвращается к предыдущей клетке и пробует следующую цифру. В среднем, для стандартного судоку требуется около 1000—5000 шагов, что делает метод эффективным для задач небольшой размерности.

Сложность

Временная сложность поиска с возвратом в худшем случае экспоненциальна, так как алгоритм перебирает все возможные комбинации. Для задачи о восьми ферзях сложность составляет O(n!), где n — размер доски. Для судоку сложность может достигать O(9^m), где m — количество пустых клеток. Однако на практике отсечение значительно сокращает количество рассматриваемых вариантов, и для многих задач поиск с возвратом работает за приемлемое время.

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

Критика

Основным недостатком поиска с возвратом является его экспоненциальная сложность для задач большой размерности. Для задач с большим пространством поиска (например, задача коммивояжёра для 50 городов) метод становится непрактичным без дополнительных эвристик. Кроме того, рекурсивная реализация может привести к переполнению стека при большой глубине рекурсии. В таких случаях предпочтительнее итеративный вариант или использование методов динамического программирования.

Альтернативами поиску с возвратом являются:

• Метод ветвей и границ — использует нижние и верхние оценки для отсечения ветвей.
• Динамическое программирование — для задач с оптимальной подструктурой.
• Жадные алгоритмы — для задач, где локально оптимальное решение ведёт к глобальному оптимуму.
• Методы Монте-Карло — для задач, где точное решение не требуется.

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

• В 1970-х годах советский математик В. М. Глушков использовал поиск с возвратом для решения задач оптимизации в системах управления.
• Алгоритм поиска с возвратом лежит в основе многих современных решателей задач удовлетворения ограничений (CSP-решателей), таких как Minion и Choco.
• В русскоязычной литературе метод также называют «алгоритмом перебора с отступлением» или «алгоритмом возврата».

Источники

• Лемер, Д. Г. (1950). «A machine method for solving combinatorial problems». Proceedings of the ACM.
• Кнут, Д. Э. (1997). Искусство программирования. Том 4. Комбинаторные алгоритмы. Addison-Wesley.
• Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. (2005). Алгоритмы: построение и анализ. М.: Вильямс.
• Марков, А. А. (1954). «Теория алгоритмов». Труды Математического института АН СССР.
• Журавлёв, Ю. И. (1968). «Алгоритмы перебора с возвратом в задачах дискретной математики». Журнал вычислительной математики и математической физики.