Метод ветвей и границ. Задача о рюкзаке

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

Предположим, что задача состоит в отыскании минимума функции f на конечном множестве X. Для успешного применения метода ветвей и границ нужно уметь на подмножествах X₁⊆X находить оценку снизу для функции f (при нахождении максимума – оценку сверху). Число f₁, равное нашей оценке функции f на множестве X₁, называется границей для функции f на X₁.

Процесс решения задачи методом ветвей и границ проходит по следующему алгоритму:

1) Разбиваем множество X на два подмножества X₁ и X₂, находим на каждом из них границу f₁ и f₂;

2) Выбираем множество, на котором оценка минимальна (при поиске минимума), разбиваем его на два подмножества X₃ и X₄ (этот процесс называется ветвлением), находим на каждом из них границу f₃ и f₄ (при этом само это множество исключается из списка подмножеств);

3) На каждом шаге мы имеем разбиение исходного множества X на конечное число подмножеств (на первом этапе это два множества X₁ и X₂, на втором – три множества и т.д.), для каждого из которых известна граница целевой функции f. Повторяем пункт 2 до тех пор, пока в каком-то из получающихся подмножеств не найдется настоящий минимум (подмножество будет иметь настолько небольшой размер, что нахождение минимума будет не очень сложной задачей). Такой минимум тоже является оценкой для множества, только в отличие от остальных данная оценка является точной;

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

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

При воплощении этого алгоритма часто используется дерево вариантов. Вершинам данного дерева соответствуют множества X, X₁, X₂, …, X_n и их оценки. Из каждой вершины-множества дуги ведут к его подмножествам, получающимся при ветвлении. Если у вершины (множества) имеется точная оценка, такую вершину помечаем звездочкой (в этой вершине далее ветвление не происходит, а ее оценка используется для прекращения ветвления в тех вершинах, у которых оценки больше).

Таким образом, для того, чтобы решать задачу методом ветвей и границ, необходимо:

1.Предложить метод ветвления, т.е. разбиения множества всех вариантов X на подмножества;

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

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

Оценить достоинства и трудности метода ветвей и границ можно только при рассмотрении конкретных задач.

Поиск по сайту: