Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 99
Текст из файла (страница 99)
Если процесс а удовлетворяет сформулированным выше условиям, то в строках 6 и 7 он добавляется в множество А и переменной к присваивается значение гп. Множество А, возвращаемое вызовом Океепч-Аст1ч1тч-Яееесток(в, 1), в точности совпадает с тем, которое возвращается вызовом Кес11кз1че-Аст1ч1тч-бееесток(в, 1, О, и). Процедура Океегьч-Аст1ч1тч-бн.есток, как и рекурсивная версия алгоритма, составляет расписание для и-элементного множества в течение времени Й(п).
Это утверждение справедливо в предположении, что процессы уже отсортированы в порядке возрастания времени их окончания. Упражнения 1б.1.1 Разработайте алгоритм динамического программирования для решения задачи о выборе процессов, основанный на рекуррентном соотношении (16.2).
В этом алгоритме должны вычисляться определенные выше размеры с(1, з] и должно выводиться подмножество взаимно совместимых процессов максимального размера. Предполагается, что процессы отсортированы в порядке, заданном уравнением (16.1). Сравните время работы найденного алгоритма со временем работы процедуры Окее1зч-Аст!ч! тч-Яееестое.
1б.1.2 Предположим, что вместо того, чтобы все время выбирать процесс, который оканчивается раньше других, выбирается процесс, который начинается позже других и совместим со всеми ранее выбранными процессами. Опишите этот подход как жадный алгоритм и докажите, что он позволяет получить оптимальное решение. 16.1.3 К максимальному множеству взаимно совместимых процессов приводит не любой жадный подход.
Приведите пример, демонстрирующий, что подход, основанный на выборе процессов с минимальным временем работы среди совместимых с уже выбранными процессами, не работает. Выполните то же самое для подходов с выбором совместимого процесса, который перекрывается с наименьшим количеством остающихся процессов или с выбором из доступных процессов с самым ранним временем начала работы. 16.1.4 Предположим, что имеется множество процессов, для которых нужно составить расписание при наличии большого количества ресурсов.
Например, это может быть расписание лекций в разных аудиториях, и наша задача — составить расписание лекций, которое бы использовало как можно меньше аудиторий. (Эта задача известна также как задача о раскраяепвамии графа отрезков ((пзегча!-ятарЬ со1опппя ргоЫеш). Можно создать граф отрезков, вершины которого сопоставляются заданным процессам, а ребра соединяют несовместимые процессы. Минимальное количество цветов, необходимых для раскрашивания всех вершин 457 Глава!д Жадные алгоритмы таким образом, чтобы никакие две соединенные вершины не имели один и тот же цвет, будет равно минимальному количеству ресурсов, необходимых для работы всех заданных процессов.) 16.1.5 Рассмотрим модификацию задачи о выборе процессов, в которой каждый процесс гч в дополнение ко времени начала и конца работы имеет некоторое значение сь Наша цель теперь заключается не в максимизации количества отобранных процессов, а в достижении максимальной суммы их значений.
То есть мы хотим выбрать множество А совместимых процессов, такое, что сумма 2, доя является максимальной. Разработайте алгоритм решения этой задачи с полиномиальным временем работы. 16.2. Элементы жадной стратегии Жадный алгоритм позволяет получить оптимальное решение задачи путем осуществления ряда выборов. В каждой точке принятия решения в алгоритме делается выбор, который в данный момент выглядит самым лучшим. Эта эвристическая стратегия не всегда дает оптимальное решение, но все же решение может оказаться и оптимальным, в чем мы смогли убедиться на примере задачи о выборе процессов. В настоящем разделе рассматриваются некоторые общие свойства жадных методов.
Процесс разработки жадного алгоритма, рассмотренный в разделе 16.1, несколько сложнее, чем обычно. Были пройдены перечисленные ниже этапы. 1. Определена оптимальная подструктура задачи. 2. Разработано рекурсивное решение. (Для задачи выбора процессов мы сформулировали рекуррентное соотношение (16.2), но пропустили разработку алгоритма на его основе.) 3, Показано, что при жадном выборе у нас остается только одна подзадача. 4. Доказано, что жадный выбор всегда безопасен. (Этапы 3 и 4 могут следовать в любом порядке.) 5.
Разработан рекурсивный алгоритм, реализующий жадную стратегию. 6. Рекурсивный алгоритм преобразован в итеративный, В ходе выполнения этих этапов мы во всех подробностях смогли рассмотреть, как динамическое программирование послужило основой для жадного алгоритма. Например, в задаче о выборе процессов сначала определяются подзадачи Я,", в которых изменяются оба индекса — и 1, и 5.
Затем мы выяснили, что если всегда делается жадный выбор, то подзадачи можно было бы ограничить видом Яы Можно предложить и альтернативный подход, в котором оптимальная подструктура приспосабливалась бы специально для жадного выбора, т.е. второй индекс можно было бы опустить и определять подзадачи в виде Я,. Затем можно 45л Часть 1У. Усовершенствованные методы разработки и аназиза было бы доказать, что жадный выбор (процесс а, который оканчивается первым в Яь) в сочетании с оптимальным решением для остаюшегося множества Я совместимых между собой процессов приводит к оптимальному решению задачи Яь.
Обобщая сказанное, опишем процесс разработки жадных алгоритмов в виде последовательности перечисленных далее этапов. 1. Привести задачу оптимизации к виду, когда после сделанного выбора остаегся решить толью одну подзадачу. 2. Доказать, что всегда существует такое оптимальное решение исходной задачи, которое можно получить путем жадного выбора, так что такой выбор всегда допустйм. 3. Продемонстрировать оптимальную структуру, показав, что после жадного выбора остается подзадача, обладающая тем свойством, что объединение оптимального решения подзадачи со сделанным жадным выбором приводит к оптимальному решению исходной задачи. Описанный выше более прямой процесс будет использоваться в последующих разделах данной главы.
Тем не менее заметим, что в основе каждого жадного алгоритма почти всегда находится более сложное решение в стиле динамического программирования. Как определить, способен ли жадный алгоритм решить конкретную задачу оптимизации? Обшего пути здесь нет, однако можно выделить два ключевых компонента — свойство жадного выбора и оптимальную подструктуру. Если удается продемонстрировать, что задача обладает двумя этими свойствами, то с большой вероятностью для нее можно разработать жадный алгоритм.
Свойство жадного выбора Первая из названных выше основных составляюших жадного алгоритма— сяовслеео жадного выбора: глобальное оптимальное решение можно получить, делая локально оптимальный (жадный) выбор. Другими словами, рассматривая, какой выбор следует сделать, мы делаем выбор, который кажется самым лучшим в текущей задаче; результаты возникаюших подзадач при этом не рассматриваются. Рассмотрим отличие жадных алгоритмов от динамического программирования. В динамическом программировании на каждом этапе делается выбор, однако обычно этот выбор зависит от решений подзадач. Следовательно, методом динамического программирования задачи обычно решаются в восходяшем направлении, т.е. сначала обрабатываются более простые подзадачи, а затем — более сложные. (В качестве альтернативного пути решения можно решать задачу в нисходящем направлении, но с применением запоминания.
Конечно же, несмотря на то, что код работает в нисходящем направлении, решения подзадач должны быть найдены до того„как будет сделан соответствующий выбор.) В жадном алгоритме делается выбор, который выглядит в данный момент наилучшим, после чего решается подзадача„возникающая в результате этого выбора. Выбор, сделанный в жадном алгоритме, может зависеть от сделанных ранее выборов, но не от каких Глава !д Жадные алгоритмы 459 бы то ни было выборов или решений последующих подзадач.
Таким образом, в отличие от динамического программирования, в котором подзадачи решаются до выполнения первого выбора, жадный алгоритм делает первый выбор до решения подзадач. Алгоритмы динамического программирования работают в восходящем направлении, жадная же стратегия обычно разворачивается в нисходящем, когда жадный выбор делается один за другим, в результате чего каждый экземпляр текущей задачи сводится к меньшему. Конечно же, необходимо доказать, что жадный выбор на каждом этапе приводит к глобально оптимальному решению.
Обычно, как это было в теореме 16.1, в таком доказательстве исследуется глобально оптимальное решение некоторой подзадачи. Затем демонстрируется, что это решение можно преобразовать так, чтобы вместо некоторого другого в нем использовался жадный выбор, приводящий задачу к аналогичной подзадаче меньшего размера. Обычно жадный выбор можно делать более эффективно, чем при рассмотрении большого набора выборов. Например, если в задаче о выборе процессов предварительно отсортировать процессы в порядке монотонного возрастания моментов их окончания, то каждый из них достаточно рассмотреть всего один ры. Зачастую оказывается, что благодаря предварительной обработке входных данных или применению подходящей структуры данных (нередко это очередь с приоритетами) можно ускорить процесс жадного выбора, что приведет к повышению эффективности алгоритма.
Оптимальная подструктура Задача демонстрирует олтимальную лодструктуу, если в ее оптимальном решении содержатся оптимальные решения подзадач. Это свойство является основным признаком применимости как динамического программирования, так и жадных алгоритмов. В качестве примера оптимальной подструктуры напомним результаты, полученные в разделе 16.1. В нем было продемонстрировано, что если оптимальное решение подзадачи ое содержит процесс аы то оно также содержит оптимальные решения подзадач Яеь и Яь5. При наличии этой оптимальной подструктуры было показано, что если известно, какой процесс используется в качестве процесса аы то оптимальное решение задачи К можно построить путем выбора процесса оь и его объединения со всеми процессами в оптимальных решениях подзадач Ягь и Я, .
На основе этого наблюдения удалось получить рекуррентное соотношение (16.2), описывающее оптимальное решение. Обычно при работе с жадными алгоритмами применяется более простой подход. Как уже упоминалось, мы воспользовались предположением, что подзадача получилась в результате жадного выбора в исходной задаче. Все, что осталось сделать, — это обосновать, что оптимальное решение подзадачи в сочетании с ранее сделанным жадным выбором приводит к оптимальному решению исходной задачи. В этой схеме для доказательства того, что жадный выбор на каждом шаге приводит к оптимальному решению, неявно используется индукция по вспомогательным задачам.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
