Алгоритмы с нуля
Backtracking
Представь, что ты упаковываешь рюкзак. У тебя есть пять предметов, каждый с весом и стоимостью. Ты хочешь уместить ценные, но не превысить лимит веса. Ты пробуешь положить предмет 1 — потом 2, потом 3. Внезапно вес превышен. Вместо того чтобы пробовать каждый оставшийся предмет (что бесполезно), ты достаёшь предмет 3 и пробуешь другой подход. Ты отступаешь. Это суть backtracking: систематично перебирай выборы и в момент, когда частичное решение не может привести к ответу, брось всю эту ветвь.
После этого урока ты понимаешь backtracking как шаблон: систематический обход в глубину всех кандидатов решений. Ты можешь кодить pattern выбора-исследования-отмены в рекурсивной функции. Ты понимаешь отсечение: как обнаружить, что частичное решение обречено, и пропустить целое поддерево. Ты видишь, что backtracking решает те же проблемы, что и brute force, но быстрее — иногда резко быстрее — потому что отсечение скрывает неплодородные ветви.
Что такое backtracking?
Backtracking — это рекурсивная техника, что перебирает все кандидаты решений, строя их пошагово. На каждом шаге ты:
- Выбираешь — делаешь выбор (возьми предмет, поставь королеву, выбери цифру).
- Исследуешь — вызываешь рекурсию с этим выбором, строя полное решение.
- Отменяешь — убираешь выбор и пробуешь следующий.
Ключевая фраза — выбери, исследуй, отмени. Ты идёшь глубоко (рекурсия), обнаруживаешь, что ветвь неплодородна (нет валидного решения), потом отступаешь (отменяешь) и пробуешь другую ветвь. Backtracking — это поход в глубину по дереву всех возможных частичных решений.
Частичные решения и ограничения
Частичное решение — неполный ответ. Ты решил часть (скажем, первые три предмета в рюкзаке), но не всё. Ограничение — правило, что должно выполняться в финальном решении (общий вес ≤ лимит, две королевы не атакуют друг друга и т.д.).
Отсечение: мощь backtracking
Без отсечения backtracking перебирает все — это brute force. Но backtracking добавляет критический элемент: отсечение. Перед рекурсией проверь, нарушает ли текущее частичное решение ограничение. Если да — ты знаешь, что ни один потомок этого частичного решения не может быть валидным. Итак, пропусти целое поддерево. Вот выигрыш: ты избегаешь исследования ветвей, что не могут привести к решению.
Пример: Генерируй все бинарные строки длины n
Бинарная строка длины 3 — это последовательность трёх 0s и 1s: 000, 001, 010, 011, 100, 101, 110, 111. Всего 2^n возможностей.
Подход backtracking:
- На каждой позиции (0 до n-1) выбери 0 или 1.
- После выбора, вызови рекурсию для следующей позиции.
- Когда строка полная (длина n), записыва её.
- Отмени выбор и пробуй другую цифру.
Это перебирает полное дерево (все 2^n возможности), но код чистый: одна рекурсивная функция, что пробует обе цифры на каждой позиции.
Пример: Расставь королей с отсечением
На доске n×n расставь n королей так, чтобы никакие две не атаковали друг друга. Brute force: пробуй все C(n², n) расстановок. Для n=8 это C(64, 8) ≈ 4 миллиарда — неосуществимо.
Backtracking с отсечением: расставляй королей ряд за рядом. Для каждого ряда пробуй каждый столбец. Перед рекурсией на следующий ряд проверь: атакует ли новая королева уже расставленных? Если да — отсеки (не вызывай рекурсию). Если нет — вызови рекурсию.
На ряду 1 расставляешь королеву в столбец 1. На ряду 2 пробуешь столбец 1 (конфликт с рядом 1, столбец 1 — отсеки). Пробуешь столбец 2 (нет конфликта — рекурсируй). На ряду 3 пробуешь столбцы, отсекая по пути. Множество ветвей отсекаются рано, избегая огромного пространства поиска.
Универсальный шаблон
function backtrack(partial_solution):
if solution_complete(partial_solution):
record_solution(partial_solution)
return
for each_choice in available_choices:
if is_valid(partial_solution + choice):
make_choice(partial_solution, choice)
backtrack(partial_solution)
undo_choice(partial_solution, choice)Мощь в is_valid(). Отсечение здесь решает, вызывать ли рекурсию.
Давай кодить два примера backtracking: генерирование бинарных строк и крошечную задачу на ограничения.
Пример 1: Генерируй все бинарные строки длины n
function generateBinaryStrings(n, current = "") {
// Базовый случай: если строка полная, записыва её
if (current.length === n) {
console.log(current);
return;
}
// Выбери 0, исследуй, отмени
generateBinaryStrings(n, current + "0");
// Выбери 1, исследуй, отмени
generateBinaryStrings(n, current + "1");
}
generateBinaryStrings(3);
// Вывод: 000, 001, 010, 011, 100, 101, 110, 111Это перебирает все 2^3 = 8 возможностей. Заметь: здесь нет отсечения. Ты выбираешь и исследуешь обе ветви на каждой позиции.
Пример 2: Положи предметы в рюкзак с лимитом веса (с отсечением)
Предположим, у тебя предметы [{weight: 2, value: 3}, {weight: 3, value: 4}, {weight: 1, value: 2}] и лимит веса 4. Какие предметы ты упакуешь?
function knapsack(items, limit, index = 0, current = [], totalWeight = 0) {
// Базовый случай: перебрали все предметы
if (index === items.length) {
console.log("Рюкзак:", current, "Общий вес:", totalWeight);
return;
}
const item = items[index];
// Выбор 1: Включи текущий предмет (если влезает)
if (totalWeight + item.weight <= limit) {
current.push(item);
knapsack(items, limit, index + 1, current, totalWeight + item.weight);
current.pop(); // Отмени
}
// Выбор 2: Пропусти текущий предмет
knapsack(items, limit, index + 1, current, totalWeight);
}
const items = [
{weight: 2, value: 3},
{weight: 3, value: 4},
{weight: 1, value: 2}
];
knapsack(items, 4);
// Выводит: все валидные рюкзаки с весом <= 4Заметь проверку if (totalWeight + item.weight <= limit). Это отсечение: если добавление предмета превышает лимит, мы пропускаем эту ветвь целиком.
Пробуй оба примера:
Давай проследим выполнение generateBinaryStrings(2), чтобы увидеть pattern выбора-исследования-отмены.
1
function generateBinaryStrings(n, current = "") {
2
if (current.length === n) {
3
console.log(current); return;
4
}
5
generateBinaryStrings(n, current + "0");
6
generateBinaryStrings(n, current + "1");
7
}
Pattern: выбери (0 или 1), иди глубоко, исследуй полностью, вернись, выбери другой вариант, иди глубоко снова. Это backtracking.
Временная сложность зависит от отсечения.
Без отсечения: Ты перебираешь всё дерево выборов. Если есть c выборов на каждом уровне и глубина d, число узлов c^d. Каждый узел делает O(1) работы, итак время O(c^d).
Пример: генерирование всех бинарных строк длины n. Выборов на каждом уровне = 2 (0 или 1). Глубина = n. Время = O(2^n). Ты генерируешь 2^n строк, это оптимально (ты должен коснуться каждой).
С отсечением: Ты пропускаешь целые поддеревья. Время сложнее анализировать, но в лучшем случае отсечение режет пространство поиска резко. В худшем случае (мало отсечения) оно ещё O(c^d).
Пример: Расстановка королей. Brute force (расставь n королей на n² клеток) O(C(n², n)) ≈ O((n²)!/(n! × (n² - n)!)), это огромно. С отсечением пространство поиска сужается, потому что ты пропускаешь ветви, где королевы атакуют друг друга. Для n=8, отсечение режет с миллиардов расстановок до 92 решений (крошечная доля).
Пространственная сложность: Глубина стека вызовов равна глубине рекурсии, это d. Итак пространство O(d). Текущее частичное решение занимает O(d) или O(d × c) пространства в зависимости от того, как ты его храниш.
Почему backtracking мощный: Без отсечения это brute force (медленно, может быть неосуществимо). С отсечением это часто практично, потому что ты избегаешь исследования ветвей, что не могут работать.
Сколько раз достигается базовый случай, когда ты вызываешь generateBinaryStrings(3)?
В функции backtracking для рюкзака, что делает проверка `if (totalWeight + item.weight <= limit)`?
Backtracking — это по сути ___ обход дерева всех частичных решений.
Почему отсечение важно в backtracking?
Частая ошибка
Ошибка: Забыть отменить выбор. Ты выбираешь включить предмет в рюкзак. Ты рекурсируешь. Но ты забываешь удалить (pop) предмет, когда возвращаешься. Теперь предмет всё ещё в рюкзаке для следующей ветви (когда ты его пропускаешь). Это портит последующие частичные решения.
// НЕПРАВИЛЬНО
for item in items:
current.push(item);
backtrack(items, current, ...);
// ОШИБКА: забыл pop!
// ПРАВИЛЬНО
for item in items:
current.push(item);
backtrack(items, current, ...);
current.pop(); // ОтмениШаг отмены — не опциональный, он критичен. Частичное решение должно быть чистым перед тем, как ты пробуешь следующий выбор.
Ты пишешь функцию backtracking, чтобы расставить 4 предмета на полку. На каждом шаге ты выбираешь, положить ли предмет или пропустить. Сколько листовых узлов (полные решения) в дереве рекурсии?
Backtracking — это рекурсивная техника, что перебирает все кандидаты решений, строя их пошагово.
Выбери, исследуй, отмени: На каждом шаге ты делаешь выбор, вызываешь рекурсию (исследуешь глубже), потом отменяешь выбор и пробуешь следующий. Это поход в глубину по дереву всех частичных решений.
Частичное решение: Неполный ответ. Ограничение — правило, что оно должно выполнять.
Отсечение: Перед рекурсией проверь, нарушает ли текущее частичное решение ограничение. Если да — пропусти целое поддерево (не вызывай рекурсию). Вот выигрыш: ты избегаешь исследования обреченных ветвей.
Временная сложность: Без отсечения ты перебираешь c^d узлов (c выборов за уровень, d уровней). С отсечением ты пропускаешь множество поддеревьев. В лучшем случае отсечение режет пространство поиска резко. В худшем случае (мало отсечения) оно ещё экспоненциально.
Шаблон:
function backtrack(partial):
if complete(partial):
record(partial); return
for each choice:
if valid(partial + choice):
add(partial, choice)
backtrack(partial)
remove(partial, choice)Backtracking решает те же проблемы, что и brute force — но быстрее, потому что отсечение пропускает неплодородные ветви.