Задания № 23, 24, 26 · ЕГЭ

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

Как сокращать перебор, отбрасывая бесперспективные варианты

2 мин чтенияСложность: Обновлено 29 сентября 2026

Отсечение ветвей перебора — это исключение вариантов, которые уже не могут привести к допустимому решению. Благодаря этому алгоритм не тратит время на продолжение заведомо неудачных вариантов.

Отсечение ветвей перебора«Ветвь» — один из путей в дереве возможных вариантов; отсечь ветвь — значит удалить весь этот путь вместе с продолжениями.

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

Как работает отсечение

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

\[\text{если } P(s)=\text{ложь},\quad \text{то все продолжения } s \text{ отбрасываются}\]

Здесь \(s\) — уже построенная часть решения, а \(P(s)\) — проверка того, что она остаётся допустимой. Правило отсечения должно быть безопасным: нельзя отбрасывать ветвь, в которой ещё может находиться правильное решение.

№

Пример

Нужно расставить числа от 1 до 4 так, чтобы сумма соседних чисел не превышала 5. Если начало последовательности уже содержит соседнюю пару \(3\) и \(4\), её сумма равна \(7\). Условие нарушено, поэтому всю ветвь, начинающуюся с этой пары, можно отсечь: переставлять оставшиеся числа бессмысленно.

Не путайте

Отсечение ветвей — это не просто перебор в другом порядке и не остановка всей программы при первой ошибке. Отбрасывается только текущая бесперспективная ветвь, после чего алгоритм продолжает проверять другие варианты. Сложность перебора с возвратом уменьшается, но в худшем случае перебор всё ещё может быть большим.

Проверьте себя

Когда можно отсечь ветвь перебора?

Что важно для задач

Сначала определить ограничение, которое можно проверить на частичном решении.
Отсекать ветвь сразу после обнаружения нарушения.
Проверять, что правило не удаляет допустимые решения.
Отличать количество проверенных вариантов от количества всех возможных вариантов.

Главное за минуту

Главное

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