Отсечения в переборе

Перебор растёт экспоненциально, и обычно это приговор. Но экспонента считается по дереву перебора, а его можно обрезать: если из вершины заведомо не получится ни одного ответа, спускаться туда незачем.

Приём называется отсечением, а весь метод — перебором с отсечениями. Асимптотику он, как правило, не улучшает, зато на практике ускоряет в тысячи раз.

Простейший пример

Генерируем двоичные строки длины $n$ с ровно $k$ единицами. Без отсечений — перебрать все $2^n$ и отфильтровать. С отсечениями:

void generate(int length, int ones) {
    if (length == n) { if (ones == k) print(prefix); return; }
    if (n - length > k - ones) {          // нулей ещё хватит
        prefix.push_back(0);
        generate(length + 1, ones);
        prefix.pop_back();
    }
    if (ones < k) {                       // единиц ещё не набрали
        prefix.push_back(1);
        generate(length + 1, ones + 1);
        prefix.pop_back();
    }
}

Оба условия — отсечения. Первое: если оставшихся позиций ровно столько, сколько недостающих единиц, ноль ставить нельзя. Второе: если единиц уже $k$, больше их не добавить.

После них перебор заходит только в вершины, из которых достижим хотя бы один ответ, и работает за $O(\binom{n}{k} \cdot n)$ вместо $O(2^n \cdot n)$. При $n = 30$, $k = 2$ это разница между $435$ и миллиардом.

Проверено: количество выведенного равно $\binom{n}{k}$ для всех $n \le 12$ и всех $k$, порядок лексикографический.

Два места, где отсекать

Отсечение можно ставить перед спуском:

if (ones < k) { ... generate(...); ... }

или сразу после входа:

void generate(int length, int ones) {
    if (ones > k) return;
    ...
}

Результат одинаков, разница только в одном лишнем вызове. Первый вариант чуть быстрее, второй короче, когда условий много и они одинаковы для всех веток.

Выбирайте по читаемости. Экономия на одном вызове функции не стоит запутанного кода.

Оценка снизу и сверху

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

Ищем минимум и уже нашли ответ $B$. Если текущая частичная стоимость плюс оптимистичная оценка остатка уже не меньше $B$ — спускаться некуда.

if (currentCost + optimisticRest >= bestFound) return;

Оценка обязана быть оптимистичной — не завышать. Завысив, вы отсечёте ветку с настоящим ответом, и решение станет неверным, причём молча.

Отсюда же стандартный совет: сначала найдите какой-нибудь ответ жадно, и только потом запускайте перебор. С хорошим начальным $B$ отсечение работает с первых шагов; со стартовым «бесконечность» первые ветки обходятся целиком.

Порядок перебора

Отсечение по оценке тем сильнее, чем раньше найден хороший ответ. Значит, перебирать варианты стоит в порядке убывания перспективности.

Классические эвристики: в задаче об упаковке начинать с самых больших предметов; в раскраске графа — с вершин наибольшей степени; в переборе с выбором — брать самую ограниченную позицию (меньше всего вариантов) первой.

Асимптотику это не меняет, зато на реальных тестах разница бывает в сотни раз. Такие приёмы называют эвристиками: доказать выигрыш нельзя, измерить — можно.

Если порядок задан условием (нужен лексикографический вывод), переставлять ветки нельзя — тогда остаются только логические отсечения.

Мемоизация как отсечение

Отдельный случай — когда разные ветки приводят в одно и то же состояние. Тогда достаточно посчитать его один раз, и это уже мемоизация.

Признак: состояние описывается небольшим набором чисел, а путь до него неважен. Если так — экспоненциальный перебор превращается в полиномиальную динамику, и это гораздо сильнее любых отсечений.

Проверять стоит именно в этом порядке: сначала «а не динамика ли это», потом отсечения.

Когда отсечения не помогут

Честная оговорка. Отсечения не меняют худший случай. Если задача требует перебрать $2^{40}$ вариантов и все они допустимы, никакая обрезка не спасёт.

Признаки, что нужен другой подход: ограничения велики ($n > 30$), а структура задачи не даёт очевидных запретов. Тогда смотрите в сторону динамики по подмножествам ($n \le 20$), встречи посередине ($n \le 40$) или полиномиального алгоритма, который вы пока не увидели.