Метод ветвей и границ ( англ. branch and bound ) — общий алгоритмический метод для нахождения оптимальных решений различных задач оптимизации, особенно дискретной и комбинаторной оптимизации . Метод является развитием метода полного перебора , в отличие от последнего — с отсевом подмножеств допустимых решений, заведомо не содержащих оптимальных решений.

Метод ветвей и границ впервые предложен в 1960 году Алисой Лэнд и Элисон Дойг для решения задач целочисленного программирования .

Общая идея метода может быть описана на примере поиска минимума функции ${\displaystyle f(x)}$ на множестве допустимых значений переменной ${\displaystyle x}$ . Функция ${\displaystyle f}$ и переменная ${\displaystyle x}$ могут быть произвольной природы. Для метода ветвей и границ необходимы две процедуры: ветвление и нахождение оценок (границ).

Процедура ветвления состоит в разбиении множества допустимых значений переменной ${\displaystyle x}$ на подобласти (подмножества) меньших размеров. Процедуру можно рекурсивно применять к подобластям. Полученные подобласти образуют дерево , называемое деревом поиска или деревом ветвей и границ . Узлами этого дерева являются построенные подобласти (подмножества множества значений переменной ${\displaystyle x}$ ).

Процедура нахождения оценок заключается в поиске верхних и нижних границ для решения задачи на подобласти допустимых значений переменной ${\displaystyle x}$ .

В основе метода ветвей и границ лежит следующая идея: если нижняя граница значений функции на подобласти ${\displaystyle A}$ дерева поиска больше, чем верхняя граница на какой-либо ранее просмотренной подобласти ${\displaystyle B}$ , то ${\displaystyle A}$ может быть исключена из дальнейшего рассмотрения ( правило отсева ). Обычно минимальную из полученных верхних оценок записывают в глобальную переменную ${\displaystyle m}$ ; любой узел дерева поиска, нижняя граница которого больше значения ${\displaystyle m}$ , может быть исключён из дальнейшего рассмотрения.

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

Метод используется для решения некоторых NP-полных задач, в том числе задачи коммивояжёра и задачи о ранце .

См. также

• Поиск с возвратом
• Альфа-бета-отсечение

Примечания