Когда задача не имеет умного решения — перебираем все варианты, отсекая лишнее.
Перебор вариантов — универсальный метод: попробуй все возможные комбинации и выбери лучшую. На ЕГЭ это задача №12 (комбинаторный перебор).
| Объект | Формула | Пример |
|---|---|---|
| Размещения без повторений | A(n,k) = n! / (n-k)! | Рассадить 3 из 5 человек |
| Перестановки | P(n) = n! | Рассадить всех 5 |
| Сочетания без повторений | C(n,k) = n! / (k!(n-k)!) | Выбрать команду 3 из 5 |
| Размещения с повторениями | nk | Пароль из 4 цифр |
| Сочетания с повторениями | C(n+k-1, k) | Разложить шары по коробкам |
Backtracking — алгоритм перебора, который:
Сложность в худшем случае: O(число листьев дерева поиска), часто экспоненциальная.
На каждом уровне выбираем столбец. Откат = возврат на предыдущий уровень.
Дерево растёт вширь: каждый уровень — следующий ферзь. Ветка обрывается (откат), если позиция бьёт предыдущих ферзей.
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]) # первое решение
Полный перебор: 64⁸ ≈ 2.8×10¹⁴ комбинаций. С отсечениями: ~15 000 nodes (из 4.4 млрд). Это примерно в 19 млн раз меньше благодаря backtracking!
Start → 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)]
Уровень 0: пустой. Уровень 1: ферзь в столбце 0. Уровень 2: ферзь в столбце 1... Каждая ветка обрывается, если ферзь бьёт предыдущего.
Ветка [0,1]→...→[0,1,3,?] дала решение. Ветка [0,1]→[0,1,2] оборвана (конфликт по диагонали). Branch-and-bound отсекает ~99.9999% ветвей.
Проверь себя! 5 вопросов, 20 XP за каждый правильный ответ.