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

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

← Вернуться к оглавлению
Alterna · глава 25 · страница 25.2
Перебор вариантов. Backtracking
Когда задача не имеет умного решения — перебираем все варианты, отсекая лишнее.
Перебор вариантов
— универсальный метод: попробуй все возможные комбинации и выбери лучшую. На ЕГЭ это задача №12 (комбинаторный перебор).
ФГОС
ФОП
ЕГЭ №12
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 — поиск с возвратом
Backtracking
— алгоритм перебора, который:
Строит решение пошагово, выбирая один вариант на каждом уровне.
Если текущий частичный выбор не ведёт к полному решению — откатывается назад и пробует другой вариант.
Использует дерево поиска: корень — пустой выбор, листья — полные решения.
Сложность в худшем случае: O(число листьев дерева поиска), часто экспоненциальная.
Backtracking-дерево: 3 ферзя (упрощённо)
На каждом уровне выбираем столбец. Откат = возврат на предыдущий уровень.
Q1
Q2
Q2
Q3
Q3
Q3
Q3
X
OK
X
Красные линии = откат (конфликт), зелёные = допустимо
Дерево растёт вширь: каждый уровень — следующий ферзь. Ветка обрывается (откат), если позиция бьёт предыдущих ферзей.
def n_queens(n, row=0, cols=[], diag1=[], diag2=[]):
if row == n:
print(cols) # одна расстановка: cols[i] = столбец ферзя на строке i
return 1
count = 0
for col in range(n):
if col in cols or (row-col) in diag1 or (row+col) in diag2:
continue # откат — бит, пропускаем
count += n_queens(n, row+1, cols+[col], diag1+[row-col], diag2+[row+col])
return count
print(f"Решений для 8 ферзей: {n_queens(8)}") # 92
# Визуализация:
def print_board(cols):
n = len(cols)
for r in range(n):
row = ['.' if c != cols[r] else 'Q' for c in range(n)]
print(' '.join(row))
print_board([0, 4, 7, 5, 2, 6, 1, 3]) # первое решение
8 ферзей — масштаб
Полный перебор: 64⁸ ≈ 2.8×10¹⁴ комбинаций. С отсечениями: ~15 000 nodes (из 4.4 млрд). Это
примерно в 19 млн раз меньше
благодаря backtracking!
Лабиринт: поиск пути с возвратом
Start → End. На каждой клетке пробуем соседей слева направо. Тупик = возврат (backtrack).
S
A
B
✗
D
E
F
G
H
End
①
②
③
④
⑤
↩
↩
⑥
✓
Сплошные = исследованные, пунктир = возврат (backtrack)
Путь: S→A→B→E→H→I→End (найден за 6 шагов). B→C отброшен (тупик), E→H отброшен (затем G→H дало лучший путь).
def solve_maze(maze, start, end):
path = []
visited = set()
def backtrack(pos):
if pos == end:
return True
for row in range(len(maze)):
for col in range(len(maze[row])):
if maze[row][col] == 1 and (row, col) not in visited:
visited.add((row, col))
path.append((row, col))
if backtrack((row, col)):
return True
path.pop() # backtrack
return False
visited.add(start)
path.append(start)
return path if backtrack(start) else []
maze = [[0,1,0,0,0],
[0,1,1,1,0],
[0,0,0,1,0],
[0,0,0,1,0]]
print(solve_maze(maze, (0,1), (3,4)))
# → [(0,1),(0,2),(0,3),(1,3),(2,3),(3,3)]
🧭
Лабиринт: анимация backtracking
N-Queens: пошаговое дерево (4 ферзя, упрощённо)
Уровень 0: пустой. Уровень 1: ферзь в столбце 0. Уровень 2: ферзь в столбце 1... Каждая ветка обрывается, если ферзь бьёт предыдущего.
∅
[0]
[1]
[0,1]
✗
✗
[1,3]
✗
✓
✗
✗
✗
✓
✗
∅ = пусто | [0,1] = ферзь 0 в столбце 0, ферзь 1 в столбце 1 | ✓ = решение | ✗ = откат
Ветка [0,1]→...→[0,1,3,?] дала решение. Ветка [0,1]→[0,1,2] оборвана (конфликт по диагонали). Branch-and-bound отсекает ~99.9999% ветвей.
♕
N-Queens: анимация backtracking
🎯
Мини-тест: 5 вопросов
XP: 0
🧩
Быстрый тест по теме
Проверь себя! 5 вопросов, 20 XP за каждый правильный ответ.