Шаблон алгоритма с возвратом

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

Идея и состояние перебора

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

Обычно рекурсивная процедура состоит из четырёх действий: выбрать очередной вариант; проверить ограничения; добавить выбор в состояние; вызвать процедуру для следующего шага. После возврата из рекурсии выбор нужно удалить. Последнее действие обязательно: именно оно освобождает состояние для следующей ветви.

Универсальный шаблон

Пусть \(state\) — текущее состояние, а \(pos\) — номер шага. Множество кандидатов зависит от состояния и номера шага. Условие допустимости отбрасывает ветви как можно раньше: не нужно строить продолжение, которое уже нарушает ограничения.

1procedure Search(state, pos):
2    if complete(state, pos):
3        process(state)
4        return
5
6    for choice in candidates(state, pos):
7        if allowed(state, choice, pos):
8            apply(state, choice, pos)
9            Search(state, pos + 1)
10            undo(state, choice, pos)

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

База рекурсии и отмена выбора

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

Операция отмены должна быть обратной операции выбора. Если при выборе сделали used[x] = true, после рекурсивного вызова нужно сделать used[x] = false. Если увеличили счётчик ресурса, его нужно уменьшить; если добавили элемент в список, его нужно удалить.

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

Разобранный пример: перестановки

Построим все перестановки чисел \(1,2,3\). На позиции pos выбираем ещё не использованное число. Состояние состоит из массива a и отметок used. Когда заполнены три позиции, выводим массив.

1a = [0, 0, 0]
2used = [False, False, False, False]
3
4
5def search(pos):
6    if pos == 3:
7        print(*a)
8        return
9
10    for x in range(1, 4):
11        if not used[x]:
12            a[pos] = x
13            used[x] = True
14            search(pos + 1)
15            used[x] = False
16
17
18search(0)

Первые ветви дают \(123\), \(132\), затем после отмены выбора первого элемента — \(213\), \(231\), \(312\), \(321\). Всего решений \(3! = 6\). Важен не только вывод, но и восстановление массива отметок: после завершения ветви used[x] снова должен иметь значение false.

Если ограничения зависят от предыдущих элементов, их проверяют в allowed. Например, при построении последовательности без одинаковых соседей новый элемент \(x\) допустим, если \(pos=0\) или \(x\ne a[pos-1]\). Для задачи о маршруте проверяют границы поля, запрет посещённой клетки и возможность перехода.

Порядок вариантов и отсечения

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

Отсечение — это досрочное прекращение ветви, которая уже не может привести к цели. Условие отсечения должно быть безопасным: если оно истинно, ни одно продолжение этой ветви не является решением. Например, если сумма уже превысила допустимый предел, добавлять новые положительные числа бессмысленно.

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

Как распознать шаблон в задаче

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

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

Быстрый тест