Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 91
Текст из файла (страница 91)
Таким образом, количество процессов, входящее в состав решения задачи 5;з,— это сумма количества процессов в решении задачи 5;ьн количества процессов в решении задачи Яя и еще одного процесса (аь). Опишем оптимальную подструктуру этой задачи. Предположим, что оптимальное решение А, задачи Яг включает в себя процесс аь. Тогда решения Агя задачи Ягь и Аьу задачи Яь в рамках оптимального решения Я, тоже должны быть оптимальными. Как обычно, это доказывается с помощью рассуждений типа "вырезания и вставки".
Если бы сушествовало решение А,', задачи Яд,, включающее в себя большее количество процессов, чем Апо в решение Ац можно было бы вместо Аьь подставить А',.ь, что привело бы к решению задачи Я,т, в котором содержится больше процессов, чем в А; . Поскольку предполагается, что А, оптимальное решение, мы приходим к противоречию. Аналогично, если бы сушествовало решение Аь задачи Яц, содержащее больше процессов, чем Аь, то путем замены Аь на А', можно было бы получить решение задачи Я;зч в которое входит больше процессов, чем в А, .
Теперь с помошью сформулированной выше оптимальной подструктуры покажем, что оптимальное решение задачи можно составить из оптимальных решений подзадач. Мы уже знаем, что в любое решение непустой задачи Я, входит некоторый процесс аь и что любое оптимальное решение задачи содержит в себе 'Иногда о множествах Ян мы будем говорить не как о множествах пронсссов. а как о вспомогательных задачах. Из контекста всегда будет понятно, что именно обозначает оч — множество пропессов иди вспомогательную задачу, входными данными для которой яавястся зто множество.
Часть!У. Усовершенствованные методы разработки и анализа 446 оптимальные решения подзадач Я,ь и Яя . Таким образом, максимальное подмножество взаимно совместимых процессов множества Я; можно составить путем разбиения задачи на две подзадачи (определение подмножеств максимального рвзмеРа, состоЯщих из взаимно совместимых пРоцессов в задачах Я;ь и Яьз) — собственно нахождения максимальных подмножеств Агь и Аь взаимно совместимых процессов, являющихся решениями этих подзадач, и составления подмножества А; максимального размера, включающего в себя взаимно совместимые задачи: А; =Агя0(аь)ОАь. (16.2) Оптимальное решение всей задачи представляет собой решение задачи Яо „+и Рекурсивное решение Второй этап разработки решения по методу динамического программирования — определение значения, соответствующего оптимальному решению.
Пусть в задаче о выборе процесса с [г, у'] — количество процессов в подмножестве максимального размера, состоящем из взаимно совместимых процессов в задаче ЯО. Эта величина равна нулю при Я; = 9; в частности, с [г, Я = О при г > ~. Теперь рассмотрим непустое подмножество Я; . Мы уже знаем, что если процесс аь используется в максимальном подмножестве, состоящем из взаимно совместимых процессов задачи 5;, то для подзадач Я;ь и Яь также используются подмножества максимального размера. С помощью уравнения (16.2) получаем рекурреитное соотношение с [г, у] = с [г, Й] + с [Й, у] + 1. В приведенном выше рекурсивном уравнении предполагается, что значение 1г известно, но на самом деле это не так.
Это значение можно выбрать из у — г — 1 возможных значений: й = г'+ 1,..., з — 1. Поскольку в подмножестве максимального размера для задачи Я; должно использоваться одно из этих значений Й, нужно проверить, какое из них подходит лучше других. Таким образом, полное рекурсивное определение величины с [г, Я принимает вид: О при Яз =9, с[и,з] = шах (с[1,к]+с[1, т]+1) при Я; ф 9. (16.З) 1<в<1 и ааел,~ Преобразование решения динамического программирования в жадное решение На данном этапе не составляет труда написать восходящий алгоритм динамического программирования, основанный на рекуррентном уравнении (16.3).
Это Глава 1б. Жадные алгоритмы 447 предлагается сделать читателю в упражнении (16.1-1). Однако можно сделать два наблюдения, позволяющие упростить полученное решение. Теорема 16.1. Рассмотрим произвольную непустую задачу Я; и пусть а,„— про- цесс, который оканчивается раньше других: 1„, = пшт Ць . аь Е Я! 1.
В этом случае справедливы такие утверждения. 1. Процесс а,„используется в некотором подмножестве максимального размера, состоящем из взаимно совместимых процессов задачи Я; . 2. Подзадача Я! пустая, поэтому в результате выбора процесса а непустой остается только подзадача Я„,зз Доказатаиьстлво. Сначала докажем вторую часть теоремы, так как она несколько проще. Предположим, что подзадача Я; непустая и существует некоторый процесс аы такой что ~, < аь < гь < а < г' . Тогда процесс аь также входит в решение подзадачи Я;,„, причем он оканчивается раньше, чем процесс а, что противоречит выбору процесса а . Таким образом, мы приходим к выводу, что решение подзадачи Я, — пустое множество. Чтобы доказать первую часть, предположим, что А; — подмножество максимального размера взаимно совместимых процессов задачи ЯЗ, и упорядочим процессы этого подмножества в порядке возрастания времени их окончания.
Пусть аь — первый процесс множества А; . Если аь = а, то доказательство завершено, поскольку мы показали, что процесс а используется в некотором подмножестве максимального размера, состоящем из взаимно совместимых процессов задачи Я; . Если же аь ~ а, то составим подмножество А'," = А, — (аь) 0 1а,„). Процессы в А, 'не перекрываются, поскольку процессы во множестве А; не перекрываются, аь — процесс из множества Ачп который оканчивается раньше всех, и 1 < Гь.
Заметим, что количество процессов во множестве А'," совпадает с количеством процессов во множестве Ачн поэтому А', — подмножество максимального размера, состоящее из взаимно совместимых процессов задачи 5; и включающее в себя процесс а,„. Почему теорема 16.1 имеет такое большое значение? Из раздела 15.3 мы узнали, что оптимальные подструктуры различаются количеством подзадач, использующихся в оптимальном решении исходной задачи, и количеством возможностей, которые следует рассмотреть при определении того, какие подзадачи нужно выбрать. В решении, основанном на принципах динамического программирования, в оптимальном решении используется две подзадачи, а также до т' — 1 — 1 вариантов выбора для подзадачи Я! . Благодаря теореме 16.1 обе эти величины значительно 448 Часть |Ч.
Усовершенствованные методы разработки и анализа уменьшаются: в оптимальном решении используется лишь одна подзадача (вторая подзадача гарантированно пустая), а в процессе решения подзадачи ЯО достаточно рассмотреть только один выбор — тот процесс, который оканчивается раньше других. К счастью, его легко определить. Кроме уменьшения количества подзадач и количества выборов, теорема 16.! дает еще одно преимущество: появляется возможность решать каждую подзадачу в нисходящем направлении, а не в восходящем, как это обычно происходит в динамическом программировании. Чтобы решить подзадачу ЯО, в ней выбирается процесс а, который оканчивается раньше других, после чего в зто решение добавляется множество процессов, использующихся в оптимальном решении подзадачи 5 з.
Поскольку известно, что при выбранном процессе и,„в оптимальном решении задачи Яз безусловно используется решение задачи Я, нет необходимости решать задачу Я до задачи Я! . Чтобы решить задачу ЯЗ, можно снпчила выбрать а, который представляет собой процесса из 5,1, который заканчивается раньше других, а потом решать задачу Я Заметим также, что существует единый шаблон для всех подзадач, которые подлежат решению. Наша исходная задача — Я = Яц„.„п Предположим, что в качестве процесса задачи Яо „ч.ы который оканчивается раньше других, выбран процесс а,. (Поскольку процессы отсортированы в порядке монотонного возрастания времени их окончания, и Го = О, должно выполняться равенство тз = 1.) Следующая подзадача — 5, „ч.п Теперь предположим, что в качестве процесса задачи 5,„, „.„ы который оканчивается раньше других, выбран процесс а„,я (не обязательно, чтобы пза = 2).
Следующая на очереди подзадача — Я,„, „+~. Продолжая рассуждения, нетрудно убедиться в том, что каждая подзадача будет иметь вид Я„ч „!.з и ей будет соответствовать некоторый номер процесса т+ Другими словами, каждая подзадача состоит из некоторого количества процессов, завершающихся последними, и это количество меняется от одной подзадачи к другой. Для процессов, которые первыми выбираются в каждой подзадаче, тоже сушествует свой шаблон. Поскольку в задаче Я,„, „„~ всегда выбирается процесс, который оканчивается раньше других, моменты окончания процессов, которые последовательно выбираются во всех подзадачах, образуют монотонно возрастаюшую последовательность. Более того, каждый процесс в процессе решения задачи можно рассмотреть лишь один раз, воспользовавшись сортировкой в порядке возрастания времен окончания процессов.
В ходе решения подзадачи всегда выбирается процесс а,„, который оканчивается раньше других. Таким образом, выбор является жадным в том смысле, что интуитивно для остальных процессов он оставляет как можно больше возможностей войти в расписание. Таким образом, жадный выбор — это такой выбор, который максимизирует количество процессов, пока что не включенных в расписание. Глава 16. Жадные алгоритмы 449 Рекурсивный жадный алгоритм После того как стал понятен путь упрощения решения, основанного на принципах динамического программирования, и преобразования его в нисходящий метод, можно перейти к рассмотрению алгоритма, работающего исключительно в жадной нисходящей манере. Здесь приводится простое рекурсивное решение, реализованное в виде процедуры Кес1!кз1че Аст1щтч Беьесток.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
