Алгоритмы

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

Цели урока

Понять парадигму Backtracking
Освоить шаблон решения
Решать классические задачи
Применять pruning для оптимизации

Предварительные знания

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

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

Головоломки (Судоку, кроссворды)
Компиляторы (парсинг с откатом)
AI игры (minimax)
Составление расписаний

Лемер дал имя, Голомб и Баумерт сделали метод систематическим

Приём «попробуй частичное решение и откати последний шаг при неудаче» очень старый. Задачу о восьми ферзях поставили в 1848 году и решали перебором задолго до компьютеров. Слово backtracking ввёл математик Д. Х. Лемер в 1950-х. Первое аккуратное общее изложение появилось в 1965 году, когда Соломон Голомб и Леонард Баумерт опубликовали работу Backtrack Programming. Они описали метод как единый способ обходить дерево частичных кандидатов и отсекать ветви, которые не могут привести к решению. Главная идея, которую они формализовали, это отсечение: как только частичное присваивание нарушает ограничение, всё поддерево под ним отбрасывается, и это может сократить экспоненциальное пространство поиска до практически приемлемого.

Идея: попробуй -> откатись

**Backtracking** - это систематический перебор всех вариантов с «откатом» при тупике.

**Когда использовать Backtracking:**

Нужно найти ВСЕ решения (или хотя бы одно)
Решение строится последовательно (выбор за выбором)
Можно рано отсечь «плохие» ветки (pruning)

**Backtracking = DFS по дереву решений.** Каждый узел - частичное решение, листья - полные решения или тупики.

Backtracking отличается от brute force тем, что:

Шаблон Backtracking

**Пример: все перестановки [1, 2, 3]**

**Не забывайте UNDO!** Без отката `state` будет содержать все выборы, не только текущую ветку.

Зачем нужен `state.pop()` в конце?

Классические задачи

**1. N-Queens (N ферзей):**

**2. Sudoku solver:**

**3. Subsets (все подмножества):**

N-Queens для n=8 имеет 92 решения. Без pruning пришлось бы проверить:

Оптимизации: Pruning

**Pruning (отсечение)** - ключ к эффективности backtracking.

Задача	Без pruning	С pruning
N-Queens (n=8)	16 777 216	~15 000
Sudoku (средняя)	9^81	~1000
TSP (n=10)	10! = 3 628 800	~10 000

**Хороший pruning** может превратить экспоненциальный алгоритм в практически полиномиальный!

Branch and Bound = Backtracking + ?

Backtracking

DFS по дереву решений
Шаблон: choice → recurse → undo
Pruning критичен для производительности
Branch & Bound = Backtracking + оптимальность
Сложность: экспоненциальная, но pruning помогает

Связанные темы

Backtracking - основа многих алгоритмов.

DFS — Backtracking = DFS по дереву решений
Dynamic Programming — Когда подзадачи перекрываются

Связанные уроки

alg-13-dfs — Backtracking - это DFS по дереву состояний
alg-32-branch-bound — Добавив границы, превращаем backtracking в branch and bound
alg-21-dp — Оба исследуют подзадачи; DP кэширует, backtracking откатывает
crypto-11-classical-cryptanalysis — Взлом шифров перебирает ключи и откатывается при неудаче
comp-01-intro

Идея: попробуй -> откатись

**Backtracking** - это систематический перебор всех вариантов с «откатом» при тупике.

**Когда использовать Backtracking:**

Нужно найти ВСЕ решения (или хотя бы одно)

Решение строится последовательно (выбор за выбором)

Можно рано отсечь «плохие» ветки (pruning)

**Backtracking = DFS по дереву решений.** Каждый узел - частичное решение, листья - полные решения или тупики.

Backtracking отличается от brute force тем, что:

Оптимизации: Pruning

**Pruning (отсечение)** - ключ к эффективности backtracking.

Задача

Без pruning

С pruning

N-Queens (n=8)

16 777 216

~15 000

Sudoku (средняя)

9^81

~1000

TSP (n=10)

10! = 3 628 800

~10 000

**Хороший pruning** может превратить экспоненциальный алгоритм в практически полиномиальный!

Branch and Bound = Backtracking + ?

Связанные уроки

alg-13-dfs — Backtracking - это DFS по дереву состояний

alg-32-branch-bound — Добавив границы, превращаем backtracking в branch and bound

alg-21-dp — Оба исследуют подзадачи; DP кэширует, backtracking откатывает

crypto-11-classical-cryptanalysis — Взлом шифров перебирает ключи и откатывается при неудаче

comp-01-intro