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

Next:4.9 Динамическое программирование
Up:4 Разработка алгоритмов
Previous:4.7 Усовершенствование поиска с возвращением

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

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

ЦЕНА $(a_1, a_2,\ldots, a_k)$ = ЦЕНА $(a_1,a_2, \ldots, a_{k-1})+ C(a_k)$ ,
где $C(a_k) \geq 0$ -- функция, определенная для всех ).

Это свойство позволяет отбрасывать любое частичное решение в процессе поиска, если его цена больше цены ранее вычисленного решения. Такие ограничения использованы в приведенном ниже варианте алгоритма поиска:

минимум := бесконечность; (* максимальное представимое число *)

цена := 0; := 1; Вычислить ;
while 0 do
while (Не пусто ) and (цена минимум) do
(* Продвижение:*)

                В качестве взять наименьший элемент из , удалив его из ;
                цена := ЦЕНА ();
                if (() -- решение) & (цена минимум) then
                    минимум := цена;

                    Хранить далее () как решение с наименьшей ценой
                end;
                ifthen (* Смысл r см. в п. 4.4 *)
                        k:=k - 1; Вычислить
                end
        end;

(* Возврат *)

; цена := ЦЕНА ()
end.

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