Перебор вариантов. Backtracking

Содержание и основные понятия

← Вернуться к оглавлению
Alterna · глава 22 · страница 22.2
Перебор вариантов. Backtracking
Backtracking, N-Queens, перестановки, размещения, сочетания.
Когда задача не имеет умного решения — перебираем все варианты, отсекая лишнее.
Backtracking
(поиск с возвратом) — главный приём. Используется в N-Queens, судоку, расстановке фигур, комбинаторных задачах.
ФГОС
ФОП
ЕГЭ №12,23
01
Виды комбинаторных объектов
Объект
Формула
Пример
Размещения без повторений A(n,k)
n! / (n−k)!
Рассадить 3 из 5
Перестановки P(n)
n!
Рассадить всех 5
Сочетания без повторений C(n,k)
n! / (k!(n−k)!)
Выбрать команду 3 из 5
Размещения с повторениями
n
k
Пароль из 4 цифр
Сочетания с повторениями
C(n+k−1, k)
Разложить шары по коробкам
02
Backtracking
Строим решение пошагово, выбирая один вариант на каждом уровне.
Если текущий частичный выбор не ведёт к полному решению — откатываемся назад и пробуем другой вариант.
Использует дерево поиска: корень — пустой выбор, листья — полные решения.
Сложность в худшем случае: O(число листьев дерева поиска), часто экспоненциальная.
03
N-Queens визуализатор
♛
Задача N ферзей: пошаговая анимация
N