Идея метода ветвей и границ. Основные способы отсечения ветвей

Решение ищется посредством направленного перебора вариантов.

Сокращение количества просмотренных вариантов достигается как за счет организации ветвления, так и за счет отсечения подмножества вариантов, не содержащих оптимального решения.

Ветвление может осуществляться, как по методу в ширину, так и по методу в глубину с возвращением.

Реализация метода: принцип разбиения вариантов на подм-ва и вычисление условий отсечения существенно зависят от вида задачи, т.е. св-в исследуемого графа. Степень сокращения перебора зависит от кач-ва оценочной функции, стратегии декомпозиции и исходных данных, учитываемых характеристик объекта. # соотношение весов ребер.

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

Способы отсечения ветвей:

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

- По результатам сравнения 2-х оценок. Такое отсечение выполняется, если в задаче на min целевой ф-ции для мн-ва вариантов можно найти оценку сверху и снизу. Если для некоторого подм-ва вариантов: Mi Fн(Mi), Fв(Mi) а для подмножества M_j - F_н(M_j) и F_в(M_j), и Fн(Mj)>= Fв(Mi), то очевидно, что ветвление в вершине соответствующей подм-ву Mj надо прекращать

- Если по каким-либо др. оценкам известно, что данное подм-во не содержит оптимального решения или прекращение ветвления в особых вершинах (алгоритм Дейкстера).

Особенности метода ветвей и границ.

- Чем точнее получена оценка перспективности, т.е. чем ближе ее значение к целевой функции для оптимального варианта, тем < кол-во вершин дерева решений будет исследовано. То же самое относительно дерева опорного решения.

- Чем > будут отличаться значения оценочных ф-ций для текущих вершин дерева решений, тем < количество вариантов будет рассмотрено.

- Если сущ. несколько принципов разбиения мн-ва решений, необходимо выбирать тот, при котором оценки наиболее точны.