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

End

Begin

{здесь OstW-вес который следует набрать из оставшихся. Stoim-стоимость текущего решения}

{Nab - набор предметов если наполнили рюкзаки набрали стоимость больше чем имеется, то считаем это новым решением}

if (Nab > N) and (Stoim > Max) then begin

{найдено решение}

BestP:=NowP;

Max:=Stoim;

{иначе если количество взятых <= обьема.

забиваем рюкзак дальше}

else if Nab<=N then

{иначе если набрано меньше чем влазит}

for i:=0 to OstW div W[Nab] do begin

{идем от 0 до ост. места}

NowP[Nab]:=i;

{берем предмет Nab пока есть место в ранце}

Search(Nab+1,OstW-i*W[Nab],Stoim+i*P[Nab]);

{после каждого взятия предмета увеличиваем

стоимость набора и уменьшаем место в рюкзаке

на вес предмета, так же увеличиваем количество

раз взятия предмета}

end;

По существу данный метод - это вариация полного перебора, с исключениями заведомо не оптимальных решений. Для полного перебора можно построить дерево решений. Если у нас есть какое то оптимальное решение P, мы пытаемся улучшить его, но если на рассматриваемой в текущий момент ветви решение заведомо хуже чем P то следует остановить поиск и выбрать другую ветвь для рассмотрения. Например, на рис 1.5. есть ограничение на вес рюкзака W=5. Тогда используя метод ветвей и границ можно сократить дерево перебора до такого, рис 1.6. Видно сразу, что количество вариантов для перебора уменьшилось сразу. А именно осталось 8 вариантов исхода, вместо 24 ранее. Но не всегда получается отсеять достаточно много вариантов чтобы скорость работы была заметно увеличена, всегда можно подобрать такие входные данные, для которых метод ветвей и границ даст оценку по времени идентичную полному перебору.

Рис 1.6

Дата добавления: 2014-10-17