Правило отсечения ветвей
Правило отсечения ветвей позволяет остановить перебор на некотором шаге, если продолжение выбранной ветви уже не может привести к допустимому или лучшему решению. Благодаря этому алгоритм просматривает не все варианты, а только перспективные.
Чтобы применить правило, рассматривают текущее состояние перебора: какие элементы уже выбраны, какие ограничения выполнены и что ещё можно добавить. Если частичное решение нарушает условие задачи, ветвь отсекают сразу. Если решается задача оптимизации, можно также оценить наилучший результат, который вообще достижим из этой ветви.
Формулировка для задачи оптимизации
Здесь \(R\) — уже найденный результат, а \(B\) — граница: максимально возможный результат для продолжений данной ветви при поиске максимума или минимально возможный при поиске минимума. Если граница не лучше \(R\), продолжать ветвь не имеет смысла.
Нужно выбрать предметы с максимальной стоимостью при ограничении веса. В одной ветви уже набрана стоимость \(R=100\). Даже если добавить все оставшиеся предметы, можно получить не больше \(B=95\). Ветвь отсекают: её продолжения не превзойдут найденное решение.
Отсечение ветви — это не пропуск случайного варианта и не остановка всего алгоритма. Удаляется только одна бесперспективная ветвь, а остальные варианты продолжают проверяться. В дереве вариантов такая ветвь просто не разворачивается до листа.
Для задачи на минимум уже найден результат \(R=12\). Нижняя граница продолжений ветви равна \(B=15\). Что сделать?
В задачах на допустимость достаточно найти противоречие с условием: например, сумма уже выбранных чисел превысила разрешённую. В задачах на подсчёт вариантов отсечение применяют только тогда, когда можно доказать, что ветвь не содержит ни одного подходящего варианта. Метод перебора с возвратом обычно возвращается к предыдущему состоянию и выбирает следующую ветвь.
Главное
- Ветвь отсекают, если она нарушает условие или доказанно не может улучшить результат.
- Для максимума сравнивают верхнюю границу с уже найденным результатом, для минимума — нижнюю.
- Отсечение одной ветви не прекращает весь перебор.