Алгоритмы - построение и анализ (1021735), страница 89
Текст из файла (страница 89)
Как и в главе! 5, первый шаг будет состоять в том, чтобы найти оптимальную подструктуру и с ее помощью построить оптимальное решение задачи, пользуясь оптимальными решениями подзадач. В главе 15 мы убедились, что для этого нужно определить подходящее пространство подзадач. Начнем с определения множеств ЯΠ— — (аь Е Я: Л < вь < Ь < ау1. Я; — подмножество процессов из множества 5, которые можно успеть выполнить в промежутке времени между завершением процесса сч и началом процесса а .
Фактически множество Я; состоит из всех процессов, совместимых с процессами и, и и, а также теми, которые оканчиваются не позже процесса а; и теми, которые начинаются нс ранее процесса и . Для представления всей задачи добавим фиктивные процессы ао и а„ч.1 и примем соглашение, что го = О и вь~.1 = со. Тогда Я = Яс „~м а,пдексы 1 и у находятся в диапазоне О < г, т < п + 1. Дополпнтельнь . ограничения диапазонов индексов 1 и 1 можно получить с помощью привсденнь х ниже рассуждений.
Предположим, что процессы отсортированы в порядке возрастания соответствующих им конечных моментов времени: Глава 16. Жадные алгоритмы 445 Утверждается, что в этом случае Я, = И, если т > ?. Почему? Предположим, что существует процесс аь Е Яг для некоторого т > т', так что процесс а, следует после процесса а„если расположить их в порядке сортировки.
Однако из определения Я, следует соотношение у, < вь < )ь < в < Д, откуда Х, < Д, что противоречит предположению о том, что процесс а, следует после процесса аз если расположить их в порядке сортировки. Можно прийти к выводу, что если процессы отсортированы в порядке монотонного возрастания времени их окончания, то пространство подзадач образуется путем выбора максимального подмножества взаимно совместимых процессов из множества Я, для О < з < у < и+ 1 (мы знаем, что все прочие ог — пустые). Чтобы понять подструктуру задачи о выборе процессов, рассмотрим некоторую непустую подзадачу 5; ' н предположим, что ее решение включает некоторый процесс аы так что Г; < аь < Хь < в .
С помощью процесса аь генерируются две подзадачи, Я;ь (процессы, которые начинаются после окончания процесса а, н заканчиваются перед началом процесса аь) и Яя (процессы, которые начинаются после окончания процесса аь и заканчиваются перед началом процесса а ), каждая из которых состоит из подмножества процессов, входящих в о'; . Решение задачи ог представляет собой обьединение решений задач авэо Яь и процесса аь.
Таким образом, количество процессов, входящее в состав решения задачи 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 з.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
