Алгоритмы - построение и анализ (1021735), страница 90
Текст из файла (страница 90)
Поскольку известно, что при выбранном процессе и,„в оптимальном решении задачи Яз безусловно используется решение задачи Я, нет необходимости решать задачу Я до задачи Я! . Чтобы решить задачу ЯЗ, можно снпчила выбрать а, который представляет собой процесса из 5,1, который заканчивается раньше других, а потом решать задачу Я Заметим также, что существует единый шаблон для всех подзадач, которые подлежат решению. Наша исходная задача — Я = Яц„.„п Предположим, что в качестве процесса задачи Яо „ч.ы который оканчивается раньше других, выбран процесс а,.
(Поскольку процессы отсортированы в порядке монотонного возрастания времени их окончания, и Го = О, должно выполняться равенство тз = 1.) Следующая подзадача — 5, „!.и Теперь предположим, что в качестве процесса задачи 5,„, „.„ы который оканчивается раньше других, выбран процесс а„,я (не обязательно, чтобы пза = 2).
Следующая на очереди подзадача — Я,„, „+~. Продолжая рассуждения, нетрудно убедиться в том, что каждая подзадача будет иметь вид Я„ч „!.з и ей будет соответствовать некоторый номер процесса т+ Другими словами, каждая подзадача состоит из некоторого количества процессов, завершающихся последними, и это количество меняется от одной подзадачи к другой.
Для процессов, которые первыми выбираются в каждой подзадаче, тоже сушествует свой шаблон. Поскольку в задаче Я,„, „„~ всегда выбирается процесс, который оканчивается раньше других, моменты окончания процессов, которые последовательно выбираются во всех подзадачах, образуют монотонно возрастаюшую последовательность. Более того, каждый процесс в процессе решения задачи можно рассмотреть лишь один раз, воспользовавшись сортировкой в порядке возрастания времен окончания процессов. В ходе решения подзадачи всегда выбирается процесс а,„, который оканчивается раньше других.
Таким образом, выбор является жадным в том смысле, что интуитивно для остальных процессов он оставляет как можно больше возможностей войти в расписание. Таким образом, жадный выбор — это такой выбор, который максимизирует количество процессов, пока что не включенных в расписание. Глава 16.
Жадные алгоритмы 449 Рекурсивный жадный алгоритм После того как стал понятен путь упрощения решения, основанного на принципах динамического программирования, и преобразования его в нисходящий метод, можно перейти к рассмотрению алгоритма, работающего исключительно в жадной нисходящей манере. Здесь приводится простое рекурсивное решение, реализованное в виде процедуры Кес1!кз1че Аст1щтч Беьесток.
На ее вход подаются значения начальных и конечных моментов процессов, представленные в виде массивов в и Г, а также индексы 1 и и, определяющие подзадачу Б! „.!.1, которую требуется решить. (Параметр и идентифицирует последний реальный процесс а„в подзадаче, а не фиктивный процесс а„+1, который тоже входит в эту подзадачу.) Процедура возвращает множество максимального размера, состоящее из взаимно совместимых процессов задачи 5! „+!.
В соответствии с уравнением (1б.1), предполагается, что все и входных процессов расположены в порядке монотонного возрастания времени их окончания. Если это не так, их можно отсортировать в указанном порядке за время О (и )ли). Начальный вызов этой процедуры имеет вид Кес~жз!че Аст!ч!тч БеьестОк(в, г, О, и). Кес1жйче Аст1ч!тч БесестОк1в, Г, з, и) ! т — 4+1 2»Ы!е т < и и в,„< Г! 3 Нот — т+1 4 Ыт<и 5 !1зеп гегпгп1а )!!КесОкз!че Аст1ч1тч БесестОк(в,1,т,и) 6 е1ве гегпгп 6 Работа представленного алгоритма для рассматривавшихся в начале этого раздела 11 процессов проиллюстрирована на рис.
16.1. Процессы, которые рассматриваются в каждом рекурсивном вызове, разделены горизонтальными линиями. Фиктивный процесс ао оканчивается в нулевой момент времени, и в начальном вызове, который имеет вид Кесикз1че Аст!ч!тч Беьесток(в, Г", О, 11) „выбирается процесс а!.
В каждом рекурсивном вызове заштрихованы процессы, которые уже были выбраны, а белым цветом обозначен рассматриваемый процесс. Если начальный момент процесса наступает до конечного момента процесса, который был добавлен последним (т.е. стрелка, проведенная от первого процесса ко второму, направлена влево), такой процесс отвергается. В противном случае (стрелка направлена прямо вверх или вправо) процесс выбирается. В последнем рекурсивном вызове процедуры, имеющем вид Кесг!кз1че Аст1Ч1тч Беьесток1в, Г", 11, 11), возвращается 6.
Результирующее множество выбранных процессов — 1а1, а4, ав, аы ). В рекурсивном вызове процедуры кесикз1че Аст1ч1тч Бееесток(в, г",г,и) в цикле» И!е в строках 2-3 осуществляется поиск первого процесса задачи Я! „+!. В цикле проверяются процессы а!+1, а!+з,..., а„до тех пор, пока не будет найден Часть 1Ч. Усовершенствованные методы разработки и анализа 450 о - о И, 1 1 4 ---, " бес!9851~!. лс1!ч!!т 56!и 1(жй.е, О, 111 ж =1 = =:.1 и; отсс!8 оче лс !гатт ж срс!Ож5„Г, 1, 11! 2 3 5 3 О 6 4 5 7 отсел! от лгп е1ге зг! остове,Е,4, !1! а, ~: —::=='ь:: — -":::::1 ~=:=':~а~ !:,::;,,:;а~".;.:.',,~ ~.—,;.," —,; „;;;,-;:, —.Д Г;:%~;"~1~ "'~"~'::::"-'):. % -7 Е л 5 3 8 6 5 9 7 6 1О 8 8 11 Ясссдзов АГ7 м17 51!Ес1ок!',Е, 8.
! !) Г::: ':'а::::::::! Г::.:.Отт3 Е.;:: . з:::3 9 8 !2 а, 1«,. лц,, жК4% с! 6гв:,-7 11 12 14 кос! 15176 667!ч! се зс! Осттжо„е. 11. " ! аме 12 О 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Рис. 16.1. Обработка алгоритмом Квсикзлчв Аст!ч!тч За.ютоа множества из один- надцати процессов первый процесс а, совместимый с процессом а;; для таюго процесса справедливо соотношение з > 71. Если цикл завершается из-за того, что такой процесс найден, то происходит возврат из процедуры в строке 5, в юторой процесс (а,„) обьединяется с подмножеством максимального размера для задачи Я,„+1, которое возвращается рекурсивным вызовом кбс1ж81чб Аст!ч!тч Бн.нсток(в, г", т,77).
Еще одна возможная причина завершения процесса — достижение условия т > и. Глава 16. Жадные алгоритмы 451 В этом случае проверены все процессы, но среди них не найден такой, который был бы совместим с процессом а;. Таким образом, Я! „+! = 9 и процедура возвращает значение 9 в строке б. Если процессы отсортированы в порядке, заданном временем их окончания, время, которое затрачивается на вызов процедуры Кесикз!че Асти!тт Яе!.есток(в,7",О,п), равно О (и). это можно показать следующим образом. сколько бы ни было рекурсивных вызовов, каждый процесс проверяется в цикле зчЬ1!е в строке 2 ровно по одному разу.
В частности, процесс аь проверяется в последнем вызове, югда 1 < Й. Итерационный жадный алгоритм Представленную ранее рекурсивную процедуру легко преобразовать в итеративную. Процедура Кес!!кз!че Асти!тг 5е!.есток почти подпадает под определение оконечной рекурсии (см. задачу 7-4): она оканчивается рекурсивным вызовом самой себя, после чего выполняется операция объединения.
Преобразование процедуры, построенной по принципу оконечной рекурсии, в итерационную— обычно простая задача. Некоторые компиляторы разных языков программирования выполняют эту задачу автоматически. Как уже упоминалось, процедура КЕ- спкз!Уе Аст!ч!тт ЯееестОк выполняется для подзадач о! „+1, т.е. для подзадач, состоящих из процессов, которые оканчиваются позже других. Процедура бкеепу Аст!у!ту Яееесток — итеративная версия процедуры йе- С!!КЗ!ЧЕ АСТ!Ч!Ту ЯЕ1.ЕСТОК.
В ней также предполагается, что входные процессы расположены в порядке монотонного возрастания времен оюнчания. Выбранные процессы обьединяются в этой процедуре в множество А, которое и возвращается процедурой после ее окончания. ОКЕЕРЪ' АСТ!Ч!Ту ЯЕ1.ЕСТОК(в, ! ) 1 и — 1епдй!в] 2 А — (а!) 3 1+ — 1 4 1'ог т — 2 1о п 5 йонв„,> г! б 1!зев А — А 0 (а„,) 7 1 — т 8 гегпгп А Процедура работает следующим образом. Переменная! индексирует самое последнее добавление к множеству А, соответствующее процессу а! в рекурсивной версии. Поскольку процессы рассматриваются в порядке монотонного возрастания моментов их оюнчания, 7! — всегда максимальное время окончания всех Часть |Ч.
Усовершенствованные методы разработки и анализа 452 процессов, принадлежащих множеству А: Л = шах (,гь: аь е А) (16.4) В строках 2-3 выбирается процесс ам инициализируется множество А, содержащее только этот процесс, а переменной з присваивается индекс этого процесса. В цикле 1ог в строках 4-7 происходит поиск процесса задачи Я; „+м оканчивающегося раньше других. В этом цикле по очереди рассматривается каждый процесс а, который добавляется в множество А, если он совместим со всеми ранее выбранными процессами; этот процесс оканчивается раньше других в задаче Яь +и Чтобы узнать, совместим ли процесс а с процессами, которые уже содержатся во множестве А, в соответствии с уравнением (16.4) достаточно проверить (строка 5), что его начальный момент в наступает не раньше момента Д окончания последнего из добавленных в множество А процессов.
Если процесс а удовлетворяет сформулированным выше условиям, то в строках 6-7 он добавляется в множество А и переменной г присваивается значение т. Множество А, возвращаемое процедурой Оккноу Аст!ч1ту Бн.нсток(в, г), совпадает с тем, которое возвращается процедурой кпсикз1чп Аст1чту Бн.исток(в, г, О,п). Процедура Окнепу Аст1чту Бш.веток, как и ее рекурсивная версия, составляет расписание для и-элементного множества в течение времени 6(п).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
