Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 98
Текст из файла (страница 98)
оаелм Мы можем разработать рекурсивный алгоритм и применить к нему запоминание либо заполнять таблицу, работая в восходящем направлении. Но можно обратить внимание на еше одну важную характеристику задачи выбора процесса, которая позволяет существенно усовершенствовать решение поставленной задачи. Осушествление жадного выбора Что если мы могли бы выбирать процесс для добавления в оптимальное реагение, не решая предварительно все подзадачи? Это могло бы спасти нас от необходимости рассматривать все выборы, возникающие в рекуррентном соотношении (16.2).
В действительности в задаче выбора процессов нужно рассмотреть только один выбор, а именно — жадный. Что означает "жадный выбор" применительно к задаче выбора процессов? Интуиция подсказывает нам, что это должен быть выбор, который оставляет ресурсы доступными как можно большему количеству процессов. В выбранном нами множестве процессов один из них должен завершаться первым. Подсказка интуиции заключается в том, что этот процесс должен завершиться как можно раньше, чтобы оставить процессам, выполняющимся после него, как можно больше времени. 1Еслн таких процессов с наиболее ранним временем завершения в Я имеется несколько, можно выбрать любой из них.) Другими словами, поскольку процессы отсортированы в возрастающем порядке времени завершения, жадный выбор представляет собой выбор процесса ап Выбор процесса, завершающегося первым, — не единственный жадный выбор для поставленной задачи; в упр. 16.1.3 предлагается рассмотреть другие варианты жадного выбора для этой задачи.
Делая жадный выбор, мы остаемся только с одной нерешенной подзадачей: поиска процессов, которые начинаются после завершения аь Почему мы не должны рассматривать процессы, завершающиеся до того, как начнется процесс ат? Мы имеем н1 ( ?ы а ~з — самое раннее время завершения любого процесса. Следовательно, никакие процессы не могут иметь время завершения, меньшее или равное времени яь Таким образом, все совместимые с а1 процессы должны начинаться после завершения процесса аь Кроме того, мы уже установили, что задача выбора процессов демонстрирует оптимальную подструктуру.
Пусть оь = 1а, Е Я: гч ) 5ь) является множеством процессов, начинающихся после завершения процесса аь. Если мы делаем жадный выбор процесса аы то нам остается решить единственную подзадачу Яз.' Оптимальная подструктура говорит нам о том, что если аг представляет собой г Мм иногда говорим о множествах яа квк о подтавачвх, а ие как о множествак продессов. Но ит контевега всегда понятно, что именно мы имеем в виду. упоминая Яа. 4бг Часть ГК усовершенствованные методы разработан и ана~иза оптимальное решение, то оптимальное решение исходной задачи состоит из процесса а1 и всех процессов в оптимальном решении подзадачи Яь Остается нерешенным главный вопрос: не подводит ли нас наша интуиция? Всегда ли жадный выбор — при котором мы выбираем процесс, завершающийся первым, — является частью некоторого оптимального решения? Приведенная далее теорема показывает, что это так и есть. Теорема 16.1 Рассмотрим любую непустую подзадачу Яы и пусть а представляет собой процесс в Яы завершающийся раньше других.
Тогда а входит в некоторое подмножество взаимно совместимых процессов Бь максимального размера. Докозоявельсовво. Пусть Аь представляет собой подмножество взаимно совместимых задач Яы имеющее максимальный размер, и пусть а является процессом в Аь с самым ранним временем завершения. Если а = а, доказательство завершено, поскольку мы показали, что а находится в некотором подмножестве взаимно совместимых процессов Яь максимального размера. Если аз ~ а, пусть множество А,', = Аь — (а ) О (а ) представляет собой множество Аы в котором а заменено на а . Процессы в Аь не перекрываются, что следует из того, что процессы в Аь не перекрываются, а является процессом из Аы завершающимся первым, и 1 ( Д.
Поскольку ~А'„! = (Аь~, мы заключаем, что А'„— подмножество взаимно совместимых процессов Яь максимального размера, и оно включает а Таким образом, мы видим, что хотя задачу выбора процессов можно решать методами динамического программирования, необходимости в этом нет. (Кроме того, нам даже не нужно проверять, имеются ли в задаче выбора процессов перекрывающиеся подзадачи.) Вместо этого можно многократно выполнять выбор процесса, завершающегося первым, оставляя при этом толью процессы, совместимые с выбранным, и повторяя эти действия до тех пор, пока не останется ни одного процесса.
Более того, поскольку мы всегда выбираем процесс с наиболее ранним временем завершения, времена завершения выбранных процессов должны находиться в строго возрастающем порядке. Мы можем рассматривать каждый процесс однократно, в порядке возрастания времен завершения процессов. Алгоритму решения задачи выбора процессов нет необходимости работать в восходящем направлении, как это делал бы табличный алгоритм динамического программирования.
Вместо этого он может работать в нисходящем направлении, выбирая процесс для помещения в оптимальное решение с последуюшим решением подзадачи выбора процессов из множества совместимых с уже выбранными. Жадные алгоритмы обычно имеют нисходящий дизайн: они сначала делают выбор, а затем решают подзадачу, в отличие от восходящего метода, который решает подзадачи перед тем, как сделать выбор. Глава!б. Жадные атгориптыы 455 Рекурсивный жадный алгоритм Теперь, после того как мы увидели, каким образом можно отказаться от решения, основанного на принципах динамического программирования, и вместо этого использовать нисходящий жадный алгоритм, можно написать простую рекурсивную процедуру для решения задачи выбора процессов.
Процедура Кесбкз!че-Аст1ч!тч-Бесесток получает значения начальных и конечных моментов процессов, представленные в виде массивов л и /,~ а также индекс Й, определяющий подзадачу Яы которую требуется решить, и размер и исходной задачи. Процедура возвращает множество максимального размера, состоящее из взаимно совместимых процессов в Яы Предполагается, что все и входных процессов уже отсортированы и расположены в порядке монотонного возрастания времени их окончания согласно (16.1). Если это не так, их можно отсортировать в указанном порядке за время 0(и 1я и), произвольным образом разрешая могущие возникнуть неоднозначности.
Начальный вызов этой процедуры имеет вид КЕСУКБ1ЧЕ-АСТ1Ч1ТУ-ЯЕ1.ЕСТОК (л, /, О, п). КЕСОКЗ!ЧЕ-АСТ!Ч1ТЧ-БЕСЕСТОК(л, /, й, п) 1 т=й+1 2 нййе т < и и л[т) < /[й) // Находим первый подходяший // процесс в Яь 3 та =т+1 4 1Тт<п 5 гегпгп (а ) 0 Кесокз1че-Аст1ч!тч-бееесток(л, /, ти, и) 6 е1бе гетнгп й Работа представленного алгоритма проиллюстрирована на рис. 16.1. В рекурсивном вызове процедуры Кесикз1че-Аст!ч!тч-Бееесток(л,/,к,п), в цикле тгййе в строках 2 и 3, осуществляется поиск первого завершающегося процесса в Яы В цикле процессы аь+1, аь+з,..., а„проверяются до тех пор, пока не будет найден первый процесс а, совместимый с процессом аь! для такого процесса справедливо соотношение н > /ь. Если цикл завершается из-за того, что такой процесс найден, то в строке 5 происходит возврат из процедуры объединения (а ) с подмножеством максимального размера для задачи о', которое возвращается рекурсивным вызовом Кесокз1че-Аст!ч1тч-Бесесток(л, /, т, п).
Еше одна возможная причина завершения процесса — достижение условия т > п. В этом случае проверены все процессы в Яы но среди них не найден такой, который был бы совместим с процессом аы В этом случае Яь = 9, и процедура возвращает () в строке 6. В предположении, что все процессы отсортированы в соответствии со временами их окончания, время работы вызова Кесикз1че-Аст!ч1тчБн.есток(а,/,О,п) равно 63(п), в чем можно убедиться следующим образом. зноскольку псевдокол получает е и / в виде массивов, они индексируются с применением записи с квадратными скобками. а ие нижними индексами. Часть 1Г Усовершенствованные матт)ы разработки и аназиза ~ Р=.=Ч е! Н оя -Астмтт-зиястсвбьй О, П) «о '.
т=) 0 — 0 1 1 4 ЮЮЮй ' 2 3 5 3 0 б 4 5 7 пзсстпч-лсптпт-Бн.зсссагзаб 4, 1 ! ) е! ВЮИЮВГЗИ)Ю ьб 3 9 6 5 9 7 6 1О т 8 В 8 11 Несьтпв-Аспптт-Вижтсе!заб В. 11) 88)6% ' 888%! 9 8 12 к~о 10 2 14 июяюв вюаюи 11 12 1б Нас!азот.Аснтпт"Вместса!з,й 11, 11) ~ аиВЮИ 0 1 2 3 4 5 б 7 8 9 10 11 12 13 14 15 16 Рис. 16.1. Работа процедурм Кнсоик)тл-Аст)ч)тт-бн.лоток с заданными ранее 11 процессами. Процессы, рассматриваемые при кткдом рекурсивном вьпове, располагаются между горизонтальными линиями.
Фиктивный процесс ао завершается в момент О, и начальный вызов кесокз)УВ-Аст)чттт-Бньнстол(в, Х, О, 11) выбирает процесс а!. В каждом рекурсивном вызове отобранные процессы показаны иплтрихованлыми, а проверяемме процессы показаны белыми прямоугавьниками. Если процесс начинается до окончания последнего добавленного процесса (стрелка мещау этими моментами указыюет влево), он отвергается. В противном случае (стрелха указывает вверх или вправо) процесс выбирается. Последний рекурсивный вызов, Кесокз)че-Аот!9177-$льнстои(в, т, 11, 11), возвращает 9.
Полученное в резулыате мнакество процессов имеет вид (аг, ав, ае, ам). Глава 16. Жадные алгаритмы 455 Сколько бы ни было рекурсивных вызовов, каждый процесс проверяется в цикле иййе, в строке 2, по одному разу. В частности, процесс а; проверяется в последнем вызове, когда /с ( т.
Итеративный жадный алгоритм Представленную ранее рекурсивную процедуру легко преобразовать в итеративную. Процедура Кеспкз1че-Аст!ч!тч-Бн.есток почти подпадает под определение оконечной рекурсии (см, задачу 7.4): она оканчивается рекурсивным вызовом самой себя, после чего выполняется операция объединения. Преобразование процедуры, построенной по принципу оконечной рекурсии, в итерационную — обычно простая задача (некоторые компиляторы разных языков программирования выполняют зту задачу автоматически).
Как уже упоминалось, процедура Кесаз1че-Аст!ч1тч-Бепсток выполняется для подзадач Яы т.е. для подзадач, состоящих нз процессов, которые оканчиваются позже других. Процедура бкеепч-Аст!ч1ту-Бесесток — итеративная версия процедуры Кес11кз1че-Аст1ч1тч-Бесесток. В ней также предполагается, что входные процессы расположены в порядке монотонного возрастания времен окончания. Выбранные процессы объединяются в этой процедуре в множество А, которое и возвращается процедурой после ее окончания.
1лкеепч-Аст! ч!тч-бе1.естОЕ(з, 5 ) 1 и = з.!епд16 2 А=!а!1 3 1=1 4 Тогтп = 2!оп 5 Из[то] > ~[(е] 6 А = А!5(а„,) 7 1е = т 8 ге!игл А Процедура работает следующим образом. Переменная к индексирует последнее добавление в множество А, соответствующее процессу аъ в рекурсивной версии. Поскольку процессы рассматриваются в порядке монотонного возрастания моментов их окончания, 7ъ — всегда максимальное время окончания всех процессов, принадлежащих множеству А, т.е. 5ь = !пах ( тв: а! Е А) (16.3) В строках 2 и 3 выбирается процесс а1 и инициализируется множество А, содержащее только этот процесс, а переменной к присваивается индекс этого процесса.
В цикле 1ог в строках 4-7 происходит поиск процесса задачи Яы оканчивающегося раньше других. В этом цикле по очереди рассматривается каждый процесс а, который добавляется в множество А, если он совместим со всеми ранее выбранными процессами; этот процесс оканчивается в Яъ раньше других. Чтобы узнать, совместим ли процесс а с процессами, которые уже содержатся во множестве А, в соответствии с уравнением (16.3) достаточно проверить (строка 5), 45б Часть Тк Усовершенствованные методы равработни и анаиыа что его начальный момент в наступает не раньше момента 1ь окончания последнего из добавленных в множество А процессов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
