Как можно определить, какие из узлов называются наиболее обещающими? Это можно сделать, сравнивая нижние границы живых листьев. Разумно рассматривать как наиболее обещающий узел с наилучшей границей, хотя это не препятствует тому, что оптимальное решение будет в конечном итоге принадлежать иной ветви дерева пространства состояний. Такая стратегия называется методом ветвей и границ с выбором наилучшего варианта.
Метод ветвей и границ
Начнем с корня, который соответствует отсутствию какого-либо выбора элементов матрицы стоимости. Значение нижней границы (которое мы обозначим lb, low bound) для корня равно 10. Узлы на первом уровне дерева соответствуют четырем элементам (заданиям) в первой строке матрицы, поскольку все они могут быть потенциальными первыми компонентами решения. Итак, мы имеем четыре живых листа, которые могут содержать оптимальное решение. Наиболее обещающим среди них является узел 2, поскольку он имеет наименьшее значение нижней границы.
Метод ветвей и границ
a -> 1 задание lb = 9+3+1+4 = 17 a -> 2 задание lb = 2+3+1+4 = 10 a -> 3 задание lb = 7+4+5+4 = 20 a -> 4 задание lb = 8+3+1+6 = 18 Таким образом, для работника a мы выделяем задание 2. Следуя стратегии выбора наилучшего варианта, исследуем сперва эту ветвь, перед тем как перейти к остальным. Теперь для работника b и оставшихся заданий мы должны произвести подсчет оценок стоимостей (естественно, с учетом работника a и задания 2).
Метод ветвей и границ
Из рассматриваемого листа выходят три ветви, соответствующие набору элемента из второй строки, не находящегося во втором столбце, и представляющие три различные задания, предназначенные работнику b. a -> зад. 2 b -> зад. 1 lb = 13 b -> зад. 3 lb = 14 b -> зад. 4 lb = 17 Рассмотрим выбор третьего элемента из строки с – при этом у нас не остается иного выбора, кроме назначения 4 работнику d, что дает нам лист, который соответствует допустимому решению с общей стоимостью 13.
Метод ветвей и границ
Другой «сестринский» узел соответствует допустимому решению {a->2, b->1, c->4, d->3} с общей стоимостью 25. Поскольку эта стоимость больше стоимости решения, соответствующего предыдущему узлу, работа с этим узлом просто прекращается (если бы его стоимость была меньше 13, пришлось бы заменить информацию о найденном наилучшем решении данными, соответствующими этому листу).
Метод ветвей и границ
Теперь, если мы обратимся к каждому из пяти листьев построенного дерева пространства состояний, то обнаружим, что их значения нижних границ не меньше значения целевой функции наилучшего решения, обнаруженного к настоящему времени. Следовательно, работа с ними прекращается, и решение, представленное этим листом является оптимальным решением поставленной задачи. Интересно отметить, что это задача имеет полиномиальный алгоритм решения известный под названием Венгерский метод (в честь открывших его венгерских математиков Кёнига и Эгервари.
Метод ветвей и границ
Пример 2. Задача о рюкзаке Дано n предметов с весами w1,…,wn и ценами v1,…,vn, а также рюкзак, выдерживающий вес W. Требуется найти подмножество предметов, которое можно разместить в рюкзаке и которое имеет при этом максимальную цену. Поскольку общее количество подмножеств n-элементного множества равно 2ⁿ, исчерпывающий перебор приводит к алгоритму со временем работы Ω(2ⁿ). Оказывается удобным упорядочить предметы в неубывающем порядке по их удельной цене (отношение цены к весу), с разрешением неоднозначностей произвольным образом.
Метод ветвей и границ
Естественной структурой дерева пространства состояний для данной задачи является бинарное дерево, построенное следующим образом. Каждый узел на уровне 0 <= i <= n представляет все подмножества из n элементов, которые включают определенный набор из первых i упорядоченных элементов. Этот частичный выбор однозначно определяется путем от корня к узлу: ветвь, идущая влево, указывает на включение очередного элемента в подмножестве.
Метод ветвей и границ
Мы записываем общий вес w и общую стоимость v выбора, соответствующего узлу, вместе с верхней границей ub значения для любого подмножества, которое может быть получено путем добавления некоторых элементом (возможно, никаких) к этому выбору. Простым способом вычисления верхней границы ub является добавление к общей стоимости уже выбранных элементов v произведения оставшейся емкости рюкзака W-w и наибольшего значения удельной стоимости среди оставшихся элементов, которое равно vi+1/wi+1: ub = v + (W-w)(vi+1/wi+1)
Метод ветвей и границ
Предмет Вес Стоимость Удельная стоимость 1 4 40 10 2 7 42 6 3 5 25 5 4 3 12 4
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.