Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 90
Текст из файла (страница 90)
Кроме того, стоимость минимального 1-дерева легко вычислить (гм, задачу 2). Если в алгоритме ветвей и границ длн ЗК ветвление производится путем включения и исключения множеств ребер, то подзадачами также являются ЗК, и соответствующие задачи об 1-дереве дают нижние границы. Хелд и Карп ие останавливаются на этом, а получают более точные нижние границы на основе этой идеи.
Предположим, что мы преобразуем ЗК, заменяя ее матрицу расстояний матрицей Ы„+пг+пт! для некоторых чисел пь Тогда стоимость каждого обхода возРастает на 2~ч ",,пг, так как мы входим в каждую вершину и выходим из каждой вершины ровно один раз. Поэтому ~акое преобразование не влияет на относительный порядок стоимостей обходов, в частности оптимальный обход остается опти- И.З. Отношения доминирования мальным. С другой стороны, оптимальное 1-дерево может измениться. Если степень вершины 1 в 1-дереве равна б„то стоимость 1-дерева после преобразования матрицы расстояний с помощью л будет равна с+ ~",,6;ло где с — стоимость 1-дерева относительно исходной матрицы стоимостей [дм!.
Следовательно, если с* — стоимость оптимального обхода, то л л с'+2 ~ли) п»[п ~с+ ~6«л, . См! пв всем С=! Ьдеревьвм Это неравенство можно переписать в виде с') гс (л), .де л гс (л) = ппп ~с+,.,'~~ (6« — 2) лг . по нем Ьдеревьвм »то дает нижнюю границу ю(л) для произвольного л; Хелд и Карп рассматривают далее задачу максимизации «с(л) относительно л, юлучая, таким образом, наилучшую нижнюю границу, возможную ~ри таком подходе. (Следует отметить, что в общем случаес* ) >шах,гс(л), поэтому имеется «разрыв» между ЗК и указанной .оответствующей ей задачей получения нижних границ.) Граница, полученная в !НК2[, настолько гочна, что деревья виска для некоторых довольно больших задач (до а=64) удается ~редставить полностью. Этот пример показывает важность эффекивных нижних границ в методе ветвей и границ, поскольку преды,ущий вариант применения этого метода приводил к существенно 'слышим деревьям поиска. Д 18.3 )тношанмя доминирования До сих пор единственным вариантом, когда вершина могла сключаться из претендентов на то, чтобы быть предком оптималього решения — т.
е. убивалась,— был вариант, в котором нижняя раница оказывалась выше текущей верхней границы. Однако имется другой способ убить вершину. Рассмотрим, например, задачу о ратчайшем пути из примера !8.2. Предположим, что в результате етвления мы получили две вершины, определяемые ребрами а, е, а : нижней границей 5) и с, й (с нижней границей 6). Эти два пути риводят в одну и ту же вершину в исходном графе, и можно скаать, что два пути в дереве ветвлений слились. Нет смысла продол;ать путь с, И, поскольку мы достигли той же точки по пути а, е, а меньшей стоимостью.
Следовательно, вершину, соответствующую ути с, й, можно убить даже раньше, чем будут получены какие- 456 Гг. 18. Метод ветвей и границ нибудь полные решения. Это пример отношения доминирования; будем говорить, что вершина а, е, а доминирует над вершиной с, а. Ниже представлен один из общих способов определения такого отношения. Определение 18.2. Если в некоторый момент можно показать, что наилучший потомок вершины у не хуже наилучшего потомка вершины х, то будем говорить, что у доминирует над х и у может убить х.
г1 Существование практических алгоритмов для проверки доминирования очень сильно зависит от рассматриваемой частной задачи. 18А Стратегии метода ветвей и границ Имеется много вариантов применения алгоритма ветвей и гранин к данной задаче; в этом параграфе мы обсудим некоторые нз них. Во-первых, имеются варианты в самом ветвлении — может существовать много способов разбиения пространства решений, как, например, в ЗК нли в общей задаче ЦЛП. Во-вторых, нужно вычислять нижние границы.
При этом часто имеется выбор между границами, которые относительно точны, но требуют относительно большого времени вычисления, и границами, которые не столь точны, но которые можно быстро вычислить. а'(х) лЯ(х) Рнс. 18.8. Возможные способы убивания вор. т ни. Аналогичные противоречия могут существовать и при выборе отношения доминирования. Нижние границы и отношения доминирования можно использовать многими способами. Чтобы объяснить это, обозначим через А5(х) акаигеноемножество в тот момент, когда ветвление производится в вершине х, через СН(х) — множество сыновей вершины х в дереве ветвлений и через (/(х) — верхнюю границу, являющуюся наилучшей стоимостью полного решения в тот момент, когда ветвление производится в вершине х (см.
рис. 18.5). На рис. 18.8 представлены четыре возможных способа, какими вершины могут быть убиты: а) живая вершина из А5(х) может убивать вершины из СН(х); б) вершины из СН(х) могут убивать вершины из АЗ(х); в), г) верхняя граница (l(х) может убивать вершины из АЗ(х) или СН(х). 78.5. Применение к задаче а риеииеании длк канеейера 457 Здесь опять имеется противоречие при выборе того, что применить: время, затрачиваемое на сравнение СН(х) и АЗ(х), может в каждой частной задаче быть оправданным или неоправданным.
В-четвертых, на каждом шаге ветвления можно выбирать, из какой вершины проводить ветвление. Обычно используются методы «вершина с наименьшей нижней оценкой следующая», «последним пришел — первым ушел» нли «первым пришел — первым ушел». Еще одна возможность выбора имеется в начале алгоритма. Часто на практике полезно найти некоторое начальное решение с помощью некоторой эвристической конструкции, аналогичной описанным в гл !7 илн 19.
Это дает нам исходную верхнюю границу У( аа, что может быть очень полезным для убивания вершин на более ранних шагах алгоритма. Однако, как обычно, мы должны сравнить время, необходимое для этой эвристики, с возможным выигрышем. Наконец, следует упомянуть, что алгоритм ветвей и границ часто останавливается, не достигнув оптимальности, либо ввиду его конструкции, либо по необходимости. В таком случае мы имеем полное решение со стоимостью У, и наименьшая нижняя граница е'. по всем живым вершинам является нижней границей оптимальной стоимости. Следовательно, относительная ошибка не превосходит (У вЂ” !.) 'й Теперь должно быть понятно, что метод ветвей и границ — это не один специальный алгори1м, а очень широкий класс алгоритмов.
Эффективное»ь его использования зависи1 от разработки стратегии для частной рассматриваемой задачи и являегся прн этом не только наукой, но и искусе»во«с Обсуждение метода ветвей и границ мы завершим примером его применения к задаче о расписании. 4 о.$ Применение к задаче о расписании дпв конвейера Мы опишем сейчас детально применение метода ветвей и границ к задаче о расписании, представляющей большой интерес — а именно к задаче о двухмашинном конвейерном расписании с критерием суммы времен окончания заданий, определяемой следующим образом.
Определение 18.3. Даны и заданий,/;, 1=1,..., п. Каждое заданиесостоитиздвух частей каждую из которых нужно выполнить на одной из двух машин. Для выполнения задания 77 на машине 1 требуется время тиь н каждое задание на машине ! должно быть завершено раньше, чем начнется выполнение соответствующего задания на машине 2, Пусть Р;; — время окончания задания 1 на машине 1. Сумма времен окончания заданий определяется как сумма времен окончания выполнения каждого задания на «шшпне 2: /= =~',Е„.
Гв. !В. Мвтвд ветвей и границ Задача о сумме времен окончания заданий (ЗСВОЗ) состоит в определении порядка выполнения заданий на машинах, при котором ! достигает минимума. [З Пример 18.6. Стандартный пример ситуации, в которой может возникать задача, аналогичная ЗСВОЗ, дает вычислительная машина, выполняющая программы по очереди. При этом задания можно отождествить с индивидуальными программами, машину !— с центральным процессором и машину 2 — с печатающим устройством. Тогда можно считать, что нам дано множество заданий с известным временем выполнения и печати, и мы хотим упорядочить их так, чтобы сумма времен (или, что эквивалентно, среднее время) окончания заданий была как можно меньше. () Приведем теперь два важных факта о ЗСВОЗ.
Первый, который можно найти в книге Конвея, Максвелла и Миллера (СММ!, позволяет ограничиться поиском единой перестановки, определяющей все расписание. Теорема 18.1. Для ЗСВОЗ имеется оптимальное расписание, при котором задания на обеих машинах вьполнягопгся в одном и том же порядке без простоев между работами. (Такие расписания называются перестановочными.) Второй, более свежий результат, принадлежащий Гэри, Джонсону и Сети (О.)Я, оправдывает серьезное привлечение алгоритма ветвей и границ. Теорема 18.2.
Задача ЗСВОЗ !и'Р-полна. (Естественно, имеется в виду соответствующая ЗСВОЗ задана типа да-нет о существовании решения, стоимость которого меньше или равна некоторому Е ) Пример 18.6. Рассмотрим следующий численный пример с тремя заданиями: Машина ! Машина 2 Задание 1 Задание 2 Задание 3 На рис. !8.9 приведены все 6 возможных перестановочных расписаний, среди которых по теореме 18.1 должно лежать оптимальное расписание. Однозначный оптимум имеет стоимость !8. гз Согласно теореме 18.1, наша задача сводится к нахождению одной перестановки и объектов, поэтому естественный способ ветвления состоит в выборе на первом уровне дерева ветвлений первого 1В.з.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
