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

Перебор с возвратом — способ систематически проверить варианты, не повторяя уже пройденные ветви. Алгоритм строит дерево нұсқа, сразу отбрасывает невозможные продолжения и возвращается к последнему выбору, если решение не найдено.

Идея перебора с возвратом

В задаче есть состояние и несколько допустимых действий. Каждое действие создаёт новый узел дерева. Из него снова выполняется выбор, пока не будет достигнуто конечное состояние — готовое решение или доказанная невозможность продолжения.

В отличие от полного перебора, бэктрекинг не обязан строить всё дерево. Если частичное решение уже нарушает ограничение, вся его ветвь отсекается. Поэтому важна проверка не только готового ответа, но и каждого промежуточного состояния.

Модель состояния и дерева

Перед записью алгоритма нужно описать состояние: что уже выбрано, какие элементы использованы и какие ограничения должны выполняться. Узел дерева хранит частичное решение, ребро — добавленный вариант, глубина — число сделанных выборов.

1. Выбрать позицию, которую нужно заполнить.
2. Перебрать кандидатов для этой позиции.
3. Тексеру, не нарушает ли кандидат ограничения.
4. Добавить кандидат к текущему состоянию.
5. Перейти к следующей позиции.
6. После возврата удалить кандидат и попробовать следующий.

Здесь \(b\) — среднее число нұсқа на шаге, а \(d\) — глубина. В задачах на перестановки ветвление уменьшается: сначала доступно \(n\) элементов, затем \(n-1\) и так далее. Поэтому число листьев равно \(n!\).

Шаблон алгоритма

Обычно бэктрекинг удобно оформлять процедурой search, получающей текущее состояние. Базовый случай проверяет, заполнено ли решение. Рекурсивная часть перебирает кандидатов, временно изменяет состояние, вызывает себя и обязательно отменяет изменение.

search(state):
    if state is complete:
        process(state)
        return

    for candidate in candidates(state):
        if satisfies_constraints(state, candidate):
            add(candidate, state)
            search(state)
            remove(candidate, state)

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

Разобранный пример: размещение ладей

Нужно расставить \(n\) ладей на доске \(n \times n\) так, чтобы никакие две не находились в одной строке или столбце. Разберём случай \(n=3\). Будем ставить по одной ладье в каждую строку, поэтому ограничение на строки выполняется автоматически. Проверяем только занятость столбцов.

def search(row, used, placement):
    if row == 3:
        print(placement)
        return
    for col in range(3):
        if col not in used:
            used.add(col)
            placement.append(col + 1)
            search(row + 1, used, placement)
            placement.pop()
            used.remove(col)

search(0, set(), [])

В более сложных задачах ограничение проверяют по нескольким признакам: сумме выбранных чисел, соседним элементам, диагоналям, длине пути или переходам между состояниями. Если состояние удобно представить явно, полезны конечный автомат и таблица допустимых переходов между состояниями.

Отсечение ветвей и оценка эффективности

Чем раньше обнаружено нарушение, тем меньше лишних вызовов. Простое отсечение проверяет уже выбранные элементы. Более сильное отсечение оценивает, можно ли достичь цели даже при самом благоприятном продолжении. Если нельзя, ветвь закрывается сразу.

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

Для отладки полезно печатать глубину, выбранный кандидат и причину отсечения. Разбор таких ошибок связан с отладкой алгоритма, а число вызовов удобно изучать через дерево рекурсивных вызовов. Не забывайте о корректном базовом случае рекурсии.

Как решать экзаменационные тапсырма

• Определите, что является одним шагом выбора и что хранит состояние.
• Запишите ограничения для частичного шешімдер.
• Найдите базовый случай: когда Шешім готово или тапсырма невозможна.
• Проверьте, что после возврата состояние восстановлено.
• Если спрашивается число нұсқа, не прекращайте поиск после первого ответа.
• Сделайте маленькое дерево вручную и сравните с программой.

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