Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 92
Текст из файла (страница 92)
На ее вход подаются значения начальных и конечных моментов процессов, представленные в виде массивов в и Г, а также индексы 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 Ц,,:;а~'.',.:,5~ ~"!"; ~7»-" ": лт:"",:.;::~~.-.!'.::.',':; 7 .;.; ф.„:У" 5 3 8 6 5 9 7 6 1О 8 8 11 Ясссдзов АГ7 м17 51!Ес1ок!',Е, 8. ! !) Г::: ':'а::::::::! Г::.:.Отт3 Е.;:: . з:::3 9 8 !2 а, 1«,. лц,, 'ж,,493'.'! '~ге:,-7' 11 12 14 кос! 15176 667!71!7 зс! Осттжо„е. 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(п). Это утверждение справедливо в предположении, что процессы уже отсортированы в порядке возрастания времени их окончания. Упражнения 16.1-1. Разработайте алгоритм динамического программирования для решения задачи о выборе процессов, основанный на рекуррентном соотношении (16.3).
В этом алгоритме должны вычисляться определенные выше размеры с [г, 7], а также выводиться подмножество процессов А максимального размера. Предполагается, что процессы отсортированы в порядке, заданном уравнением (16.1). Сравните время работы найденного алгоритма со временем работы процедуры Окннзу Аст1чту Бн.исток. 16.1-2. Предположим, что вместо того, чтобы все время выбирать процесс, который оканчивается раньше других, выбирается процесс, который начинается позже других и совместим со всеми ранее выбранными процессами. Опишите этот подход как жадный алгоритм и докажите, что он позволяет получить оптимальное решение. 16.1-3.
Предположим, что имеется множество процессов, для которых нужно составить расписание при наличии большого количества ресурсов. Цель— включить в расписание все процессы, использовав при этом как можно меньше ресурсов. Сформулируйте эффективный жадный алгоритм, Глава 16. Жадные алгоритмы 453 позволяющий определить, какой ресурс должен использоваться тем или иным процессом. (Эта задача известна также как задача о раскрашивании интервального графа (1пгегча1-йгарЬ со!оийпд ргоЫеш).
Можно создать интервальный граф, вершины которого сопоставляются заданным процессам, а ребра соединяют несовместимые процессы. Минимальное количество цветов, необходимых для раскрашивания всех вершин таким образом, чтобы никакие две соединенные вершины не имели один и тот же цвет, будет равно минимальному количеству ресурсов, необходимых для работы всех заданных процессов.) 16.1-4. Не все жадные подходы к задаче о выборе процессов позволяют получить множество, состоящее из максимального количества взаимно совместимых процессов. Приведите пример, иллюстрирующий, что выбор самых коротких процессов среди тех, что совместимы с ранее выбранными, не дает правильного результата.
Выполните такое же задание для подходов, в одном из которых всегда выбирается процесс, совместимый с ранее выбранными и перекрывающийся с минимальным количеством оставшихся, а в другом — совместимый с ранее выбранными процесс, который начинается раньше других. 16.2 Элементы жадной стратегии Жадный алгоритм позволяет получить оптимальное решение задачи путем осуществления ряда выборов. В каждой точке принятия решения в алгоритме делается выбор, который в данный момент выглядит самым лучшим. Эта эвристическая стратегия не всегда дает оптимальное решение, но все же решение может оказаться и оптимальным, в чем мы смогли убедиться на примере задачи о выборе процессов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
