Метод ветвей и границ

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

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

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

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

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

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

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

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

См. такжеПравить

ПримечанияПравить

↑ A. H. Land and A. G. Doig. An automatic method of solving discrete programming problems, С. 497-520.

[land_doig-1] A. H. Land and A. G. Doig. An automatic method of solving discrete programming problems, С. 497-520.

[1]