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

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

При некоторых конкретных значениях исходных даннных задачи удается полный перебор заменить перебором с отсечением. Наиболее типичным вычислительным методом сокращения перебора является метод ветвей и границ.

Пусть имеется конечное множество М ситуаций или вариантов и функция F, принимающая различные значения в зависимости от выбранного варианта. Требуется среди вариантов найти оптимальный, то есть такой, на котором функция F принимает минимальное значение (или максимальное в зависимости от условия задачи).

Метод ветвей и границ отыскания оптимального варианта состоит из ветвей и отсечений. Рассмотрим сначала ветвление.

Принимаем какой либо принцип разбиения множества М на подмножества M_i такие, что , .

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

На каждом шаге вариант, оптимальный для всего множества М, принадлежит одному из M_i и является для него оптимальным. Поэтому его достаточно искать среди оптимальных вариакнтов для подмножества M_i, составляющих множество М. Этим самым решение задачи для всего множества М сводится к решению задачи для составляющих его множеств M_i и последующему отысканию оптимальных среди найденных для них решений. Процесс разбиения множества М на подмножества можно изобразить в виде дерева.

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

Исключение множеств вариантов из рассмотрения производится с помощью оценочных функций. Оценочная функция - это функция m(M_i)=m_i заданная на вершнах дерева полного перебора, возможно, исключая корень, и равная в его конечных вершинах соответствующим значениям функции F, а в остальных вершинах M_i дающая нижнюю или верхнюю границу значений функции F для вариантов, входящих в множество M_i.

Оценочная функция, дающая нижнюю границу, в процессе разбиения множества на части не убывает, а дающая верхнюю границу - не возрастает.

Основные принципы отсечения ветвей.

1) Отсечение по сравнению с уже найденным значением функции F. Пусть ищется минимальныое значение F и получены оценки снизу от M_i, для части вершин дерева и значение F=F₀ для некоторого варианта. Тогда в вершинах, где M_i , ветвление прекращаеются.

2) Отсечение по сравнению двух оценок. Его можно производить когда для M_i строится оценка снизу и оценка сверху. Если при этом для некоторых M_i и M_j оказывается, что нижняя больше - либо равна верхней, то при отыскани минимума F ветвлений из вершины M_i прекращается.