Основная идея B & B:
- При решении задачи оптимизации («Найти X, удовлетворяющий критериям Y, чтобы минимизировать стоимость f (X)»), вы строите решение по частям - в любой момент времени у вас есть частичное решение , которое имеет стоимость .
- Если природа проблемы такова, что стоимость частичного решения может оставаться неизменной или увеличиваться по мере того, как вы продолжаете добавлять к ней кусочки, то вы знаете, что нет смысла продолжать добавлять кусочки к частичное решение, если уже есть полное решение с более низкой стоимостью . В этом случае вы можете отказаться от (или «обрезать», или «понять») дальнейшей обработки этого частичного решения.
Многие проблемы обладают последним свойством, что делает B & B широко применяемым алгоритмом.
Процесс поиска решений может быть представлен деревом поиска , где корневой узел представляет отправную точку, где не было принято никаких решений, а каждое ребро, ведущее от узла, представляет решение о чем-то быть включенным в частичное решение. Каждый узел - это частичное решение, включающее решения (ребра) от корня до этого узла.
Пример: если мы хотим решить головоломку судоку, корневой узел будет представлять доску с заполненными только первоначально поставленными числами; от этого корня может быть 9 ребер, каждое из которых представляет решение присвоить число 1-9 верхней левой ячейке. Каждый из этих 9 узлов частичного решения может иметь 8 ветвей, представляющих действительные назначения для ячейки в позиции (1, 2) и так далее. Обычно каждое ребро представляет шаг рекурсии в программе.
В B & B в лучшем случае хорошее решение находится на ранней стадии, а это означает, что неперспективные области дерева поиска можно обрезать рядом с корнем; но в худшем случае будет создано все дерево действительных решений. По этой причине B & B обычно используется только для решения задач, для которых не известен более быстрый алгоритм (например, NP-сложные задачи).