Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 91
Текст из файла (страница 91)
Т)римеиеипе к задаче о расписании дли конвейера задания в расписании, на следующем уровне — второго задания и т. д. Далее требуется подобрать функцию, вычисляющую нижние границы. Игналл и Шрейдж 1151 описали очень эффективный метод вычисления нижних границ, который мы сейчас ныведем. ПредположИМ, ЧтО МЫ НаХОДИМСЯ В Маш„„а3 ! ! 222 3 3 некоторой вершине, в ко- Машина2 ! 2 3 33 .к=!9 торой задания из множе- 1 1 Т ства мс: — (1,...,и) уже машина! ! ! 3 з 2 г 2 вставлены в расписание, "Тащима 2 ! з з з 2 где (М1=г. Пусть Ть, й=- 11 =1,..., и — порядковый Машкина 1 2 г 2 ! ! з з н мер Те-го 3 ания в М~щниа 2 2 ! З З 3 У=2О о. - ад 1 1 пРоизводьном Расписании, Маши„а ! 2223311 являющемся потомком рас Машина 2 г з з з ! 2! сматриваемой вершины.
1 Т1 Стоимость этого расписа- Машина ! 3 3 ния, которую мы хотим Машина 2 з з з ! оценить, равна 11 1 Машина! Ззгггг! (18,5) Машина 2 3 3 3 2 19 ~ем счм 11 Т Если выполнение каждого Рис. ТВ.Э. Шесть возможных перестзноночных расписаний и примере 1Юб и соотьетзадания на машине 2 МО стнующие им стоимости. Стрелки указывают жег начинатьси сразу же время окончания работ нз машине 2. после завершения ее выполнения на машине 1, то вторая сумма в (!8.5) примет вид ь 5,= Х (гн +(и — й+1)т„+тм„~ (18.6) (см.
задачу 3). В противном случае 3, ноже! только возрасти, по- этому у= Тв У= 39 Следовател ьно, Т ~) ~ й и + птах (5ы 53). Чем (18. 1О) ~Ем>вп (18.7) ем Аналогично, если выполнение каждого задания на машине 2 может быть начато сразу же после окончания выполнения на машине 2 предыдущего задания, то вторая сумма в (18.5) примет вид л Я, ~ ГгпахТ'Рм, Ги +ш(птхг'Т+(и — й+1)тм ). (188) е=~ч~1 ~ " ' чем у Это опять дает нижнюю оценку Х Е„~8;. (18.9) ЦМ За. тд. Метод ветвей и граниЦ Эта оценка зависит через („от порядка, в котором оставшиеся задания войдут в расписание.
Однако эту зависимость можно !:сключить, заметив, что 5, будет минимально, если !д выбрать так, чтобы задания с длиной т„, шли в возрастающем порядке, и 5, будет минимально, если !а выбрать так, чтобы задания с длиной т„также шли в возрастающем порядке. Обозначим получаемые в результате минимальные величины через 5, и 5,.
Тогда получаем следующую нижнюю границу: ) ) ~, г"и+шах (5„5,), (18.!1) гем О!9 Я9 Рис. !8.!О. Дерево поиска или примера !8,6. дерево поиска, в котором в качестве вершины ветвления выбирается каждый раз вершина с наименьшей нижней границей, а в случае, если таких вершин несколько, выбирается самая левая из них. Как только приходим к оптимальному решению (1, 3, 2), оно убивает все остальные решения. В заключение опишем естественное отношение доминирования, также предложенное Игиаллом и Шрейджем !15!. Пусть две вершины ! и и представляют частичные расписания, содержащие одно которая легко вычисляется. Пример 18.6 (продолжение).
На первом шаге ветвления неравенство (!8.1!) дает нижние границы 18, если задание ! выполняется первым, 20, если задание 2 выполняется первым, 18, если задание 3 выполняется первым. Результаты, приведенные на рис. 18.9, показывают, что первые две из этих оценок точные. На рис. 18.10 приведено полностью 1СС.о. Линомичесное нроердммиросднйз то же множество заданий М.
Пусть й-ми по поряд у задансся. и частичных расписаниях 1 и и будут соответственно задания сь ию /г=1,..., г. Тогда если Рос„( Р,„, (18.12) выполнение множества заданий из М на машине 2 при частичном асписании 1 заканчивается не позднее, чем при расписании и) если уже полученная суммарная стоимость при частичном рас:исании 1 не больше, чем при расписании и, т. е. Х Рее(в расписании! Е еэс Рсе!в расппсапис и, (18 13) сем СЕМ о наилучшая достройка расписания ( не хуже, чем наилучшая до:тройка расписания и. Поэтому неравенства (18.12) и (18.13) опре!еляют отношение доминирования с над и. Пример 18.8 (продолжение). Рассмотрим вершины (=(1, 2) с и=(2, 1) (не порождена на рис.
!8.10). Тогда 1 доминирует над с. С другой стороны, с=(1, 3) не доминирует над и= — (3,1). Этот дример слишком мал, чтобы показать реальную силу отношения доминирования. ( ! 1о.б Динамическое программирование Метод динамического программирования близок к методу ветвей и границ в том смысле, что он производит разумный перебор всех допустимых точек некоторой задачи, но делает это другим способом. Идея его состоитвтом, чтобы идти от последних решений к более ранним решениям. Пусть для решения некоторой комбинаторной задачи оптимизации нам нужно принять последовательность из и решений, скажем 0„0„..., 0„.
Тогда, если эта последовательность оптимальна, последние й решений 0„„„, 0„„,..., 0„должны быть оптимальны. То есть заеерсиающая часть оптимальной последовательности решений должна быть оптимальной. Это утверждение часто называют принципом оптимальности. Обычно применение динамического программирования включает в себя разбиение задачи на этапы, на каждом из которых принимаются решения, и нахождение рекуррентного соотношения, которое позволяет переходить от произвольного этапа к предыдусцему этапу.
Мы объясним этот метод на примерах, начав с задачи о кратчайшем пути для слоистых сетей, в которой последовательность принимаемых решений от последнего до первого очевидна. Пример 18.7 (динамическое программирование для задачи о кратчайшем пути в слоистых сетях). Рассмотрим слоистую сеть, приведенную на рис. 18.11, в которой требуется найти кратчайший путь из з в й Пусть таблица(с) — это таблица оптимальных спо- Гл. !8.
Меитод ееамей и границ 462 собов продолжения кратчайшего пути при условии, что мы находимся в т'-м слое от стока Г; т. е, таблица(1) содержит наилучшее решение для каждой вершины в слое, отстоящем на т дуг от г. Тогда первой таблицей будет просто. вершина (й(пт таблит!а(1)= следующая вершина ( ( ! 1 общая стоимость 5 1 4 2 Рассмотрим геперь построение таблицы(2). Из вершины д мы можем перейти в 1 или й. Из таблицы(1) нам известна стоимость Рис. !а.т!. Задача о кратчайвтем пути в слои.
стой сети. оптимального продолжения пути из 1 и и, поэтому мы можем найти наилучшее решение в вершине д, сравнивая стоимость дуги ~д, 1) плюс стоимость продолжения пути из 1 со стоимостью дуги (я, й) плюс стоимость продолжения пути из й. Проделывая то же са.
мое для вершин й и т, получаем таблицу(2): вершина й (т 1 таблица(2)= следующая вершина й й лт общая стоимость 3 4 5 Далее находим вершина с(е у таблш!а(3)= следующая вершина 6 (т (т общая стоимость б 5 6 !8.6. Днноминееное прогроммпроеонме лаз п>абли>(а(4) = таблица(5) = вершина а (> с следующая вершина е! с( 7 общая стоимость 8 7 7 вершина 3 следующая вершина с общая стоимость 11 Геперь можно восстановить оптимальный путь, просматривая таб>ицы в обратном порядке, в результате чего получаем путь (з, с, ', й, Ф, !) со стоимостью 11. ! ) Конечно, в более сложных задачах применение динамического >рограммирования сталкивается с проблемами времени и памяти, >оскольку размер таблиц может расти экспоненциально от этапа < этапу.
Лля иллюстрации этого приведем в заключение формули>овку ЗК с использованием динамического программирования. Пример !8.8 (динамическое программирование и ЗК!НК31). 1ус>ь даны множество 5~(2, З,...,п) и й Е5. Обозначим через ."(5, я) оптимальную стоимость пути, начинающегося из города 1, троходящего по всем городам множества 5 и заканчивающегося в городе й. Начнем с нахождения С(5, й) для !5 !=--1, что дает просто С(!>е», й)=>1,„для всех я=2, ..., н. (18.14) Этот минимум нужно вычислить для всех множеств 5 данной мощности и для каждого возможного ~орода т из 5.
(При этом необходимо хранить город т, для которого достигается минимум, с тем, чтобы можно было восстановить оптимальный обход обратным просмотром.) Если считать, что для каждого значения С(5, й) требуется одна ячейка памяти, то в целом требуется память и-! Х А ~ ) = (и — 1) 2' - '= О (п2") й (18.16) ячеек [НКЗ), а число сложений и сравнений равняется и-! Х й (й — !) ( )+ ( — 1) = = (и — 1) (и — 2) 2' '+(и — 1) =0(пе2п), (18,17) Г(ля вычисления С(5, й) при Д>1 мы используем тот факт, что пля нахождения наилучшего маршрута из города ! в город й, проходящего через все города множества 5, достаточно рассмотреть для каждого т вариант, в котором т посещается непосредственно перед А, и обратиться к С(5 — (й», т) в предыдущей таблице.
Таким образом, С (5, lг) = ппп»С (5 — (>е», т) +>( 1. (18 15) и е я — пп Гл. !В. Метод ветвей и границ 464 Эти функции экспоненциальны относительно размера задачи и и могут показаться недопустимо большими. Однако, если вспомнить тот факт, что при простом переборе имеется (а — !)! различных аб. ходов, можно понять, что на самом деле этот подход дает огромный выигрыш. Поскольку для ЗК не известно алгоригмов, лучших, чем экспоненциальиые, то подход с помощью динамического програм. мирования нельзя отбрасывать, хотя доказано, что алгоритмы ветвей и границ в данном случае более эффективны, Как видно из приведенных двух примеров, динамическое программирование является очень общей идеей и может требовать большей или меньшей изобретательности для нахождения хороших способов разбиения задачи на этапы, при которых можно найти удМ- нос рекуррентное соотношение.
Нетрудно заметить, что некоторые из алгоритмов, рассмотренных ранее в этой книге, можно рассматривать как применения динамического программирования (см. задачи 7 и 8 и 8 !7.3, посвященный задаче 0-)-РЮКЗАК). Задачи 1. Докажите, что алгоритм ветвей и границ при применении к задаче ЦЛП приводит к опгимальностн за число шагов, ограниченное экспонентой от размера задачи. 2. Опишите алгоритм с оценкой времени 0(пэ) для нахождении минимального 1-дерева по данной (лил)-матрице расстояний.
3, Докажите, что равенства (18.6) и (18.8) правильно вычисляюг указанные нижние границы. 4. Проанализируйте сложность по времени н памяти алгоритма дннамиче. ского программирования для задачи о кратчайшем пути в слоистой сети н срав. инте ее со сложностью по времени н памяти алгоритма Дейкстры (гл 6), приме. ненного к той же задаче. 6. Установите справедливость равенств (!8.16) и (18.17), определяющих потребности в памяти и времени алгоритма динамического программирования для ЗК. Каков асимптотический выигрыш во времени по сравнению с полным перебором (л — 1)1 обходов? 6.
Является лн необходимым требование, чтобы на шаге ветвления общего алгоритма ветвей и гранин множество решений разбивалось на нелгресгкающигся части? 7. Проинтерпретируйте алгоритм Дейкстры (гл 6) для эздзчн о кратчай~пем пути (с неотрицательными расстояниями] как применение динамического про. грзммнрования Дайте явное определение этапа, рекуррентного соотношения и начальных условий, аналогично (18.!4) н (18 16]. 8 Повгорите задачу 7 для алгоритма Флойда — Уоршелла (см.
4 6,5). 9. Построим, используя динамическое программирование, алгоритм со сложностью 0()У)а) для задачи о кратчайшем пути для;лучзя. когда допускаются отрицательные расстояния Рассмотрим неорненэированный граф 0=(У, Е) с исходной вершиной в и матрицей расстояний !В!7!. а) Пусть рг(х) означает кратчайшую длину пути из исходной вершины в в вершину х, использующего г или меньше промежуточных ребер. Запишите рекурпенгное соотношение для рг(х) и соответствующее начальное условие. б) Покажите, что гслн нрн переходе от»тапа 1 к этапу 1+1 никакое р1(х) не изменяется, то это означает, что мы достигли огпимальностн и можем остановиться.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
