Перебор с возвратом¶

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

¶История

Метод перебора с возвратом в неявном виде использовался ещё в древности при решении головоломок, таких как задача о ходе коня или задача о восьми ферзях. Однако формализация алгоритма началась в середине XX века с развитием вычислительной техники. В 1950-х годах американский математик Деррик Генри Лемер (Derrick Henry Lehmer) ввёл термин «backtracking» для описания процесса поиска решений комбинаторных задач. В 1960-х годах метод был систематизирован в работах по искусственному интеллекту, в частности, в алгоритмах для доказательства теорем и игр, таких как шахматы. В 1970-х годах Роберт Флойд и другие исследователи предложили формальные схемы реализации перебора с возвратом, включая использование рекурсии и стека. С тех пор метод стал одним из основных в дискретной математике, комбинаторике и программировании.

¶Основные принципы

¶Дерево решений

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

¶Рекурсивная процедура

Алгоритм реализуется, как правило, рекурсивной функцией, которая на каждом шаге:

1. Проверяет, является ли текущее состояние полным решением. Если да — фиксирует его (например, выводит или сохраняет).
2. Если решение не полное, но может быть продолжено, перебирает все возможные варианты следующего шага (кандидатов).
3. Для каждого кандидата проверяет, удовлетворяет ли он ограничениям задачи (функция проверки допустимости). Если кандидат допустим, рекурсивно вызывает себя для нового состояния.
4. После возврата из рекурсии (или если ни один кандидат не подошёл) происходит откат к предыдущему состоянию — отмена изменений, сделанных на текущем шаге.

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

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

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

¶По типу решаемой задачи

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

¶По способу реализации

• Рекурсивный перебор — наиболее распространённый вариант, использующий стек вызовов.
• Итеративный перебор — реализуется с помощью явного стека (например, списка состояний) для избежания переполнения стека при большой глубине рекурсии.

¶Применение

¶Комбинаторные задачи

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

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

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

В игровых программах (шахматы, шашки, го) перебор с возвратом лежит в основе алгоритмов минимакс и альфа-бета-отсечение. Дерево игры строится на несколько ходов вперёд, а отсечение позволяет отбрасывать заведомо проигрышные ветви.

¶Поиск в пространстве состояний

В задачах планирования и робототехники перебор с возвратом используется для поиска последовательности действий, приводящих к целевой ситуации. Примеры: поиск пути в лабиринте, сборка кубика Рубика, планирование задач.

¶Компиляторы и обработка текста

В синтаксическом анализе (парсинге) метод перебора с возвратом применяется в некоторых алгоритмах разбора, например, в рекурсивном спуске с возвратом (backtracking parser). Однако на практике чаще используются более эффективные методы (LL, LR).

¶Пример: задача о восьми ферзях

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

Алгоритм:

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

Метод находит все 92 решения (с учётом симметрий — 12 уникальных). Без отсечения (наивный перебор) пришлось бы проверить 4,4 миллиарда комбинаций, с отсечением — всего несколько тысяч.

¶Ограничения и недостатки

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

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

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

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

• Алгоритм перебора с возвратом часто используется в учебных курсах по программированию как пример рекурсии и комбинаторного поиска.
• В 1970-х годах метод был применён для решения задачи о «проблеме коммивояжёра» (TSP) для небольших графов, но для больших графов оказался непрактичным.
• В современных системах искусственного интеллекта, таких как AlphaGo, перебор с возвратом в чистом виде не используется из-за огромного пространства состояний; вместо этого применяются методы машинного обучения и эвристики.

¶Источники

• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. — 3-е изд. — М.: Вильямс, 2013. — Глава 5.4.
• Седжвик Р., Уэйн К. Алгоритмы на Java. — 4-е изд. — М.: Вильямс, 2016. — Глава 4.2.
• Кнут Д. Искусство программирования. Том 4А. Комбинаторные алгоритмы. — М.: Вильямс, 2016. — Раздел 7.2.1.
• Russell S., Norvig P. Artificial Intelligence: A Modern Approach. — 4th ed. — Pearson, 2020. — Chapter 3.6.