Алгоритмы поиска и сортировки деревьями: метод ветвей и границ

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

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

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

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

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

void Knapsack3(int j) {

if (j == N) {

if (bestWeight < curWeight && curWeight <= W) {

for (int i = 0; i < N; ++i) y[i] = x[i];

bestWeight = curWeight;

}

return;

}

lostWeight += weight[j];

if (bestWeight <= maxWeight - lostWeight) //205

Knapsack3(j + 1);

lostWeight -= weight[j];

curWeight += weight[j];

if (curWeight <= W) { //106

x[j] = 1;

Knapsack3(j + 1);

x[j] = 0;

}

curWeight -= weight[j];

}

Дата добавления: 2015-07-26; просмотров: 136; Нарушение авторских прав

Мы поможем в написании ваших работ!