Алгоритмы - построение и анализ (1021735), страница 91
Текст из файла (страница 91)
Это утверждение справедливо в предположении, что процессы уже отсортированы в порядке возрастания времени их окончания. Упражнения 16.1-1. Разработайте алгоритм динамического программирования для решения задачи о выборе процессов, основанный на рекуррентном соотношении (16.3). В этом алгоритме должны вычисляться определенные выше размеры с [г, 7], а также выводиться подмножество процессов А максимального размера. Предполагается, что процессы отсортированы в порядке, заданном уравнением (16.1). Сравните время работы найденного алгоритма со временем работы процедуры Окннзу Аст1чту Бн.исток.
16.1-2. Предположим, что вместо того, чтобы все время выбирать процесс, который оканчивается раньше других, выбирается процесс, который начинается позже других и совместим со всеми ранее выбранными процессами. Опишите этот подход как жадный алгоритм и докажите, что он позволяет получить оптимальное решение.
16.1-3. Предположим, что имеется множество процессов, для которых нужно составить расписание при наличии большого количества ресурсов. Цель— включить в расписание все процессы, использовав при этом как можно меньше ресурсов. Сформулируйте эффективный жадный алгоритм, Глава 16. Жадные алгоритмы 453 позволяющий определить, какой ресурс должен использоваться тем или иным процессом. (Эта задача известна также как задача о раскрашивании интервального графа (1пгегча1-йгарЬ со!оийпд ргоЫеш). Можно создать интервальный граф, вершины которого сопоставляются заданным процессам, а ребра соединяют несовместимые процессы.
Минимальное количество цветов, необходимых для раскрашивания всех вершин таким образом, чтобы никакие две соединенные вершины не имели один и тот же цвет, будет равно минимальному количеству ресурсов, необходимых для работы всех заданных процессов.) 16.1-4. Не все жадные подходы к задаче о выборе процессов позволяют получить множество, состоящее из максимального количества взаимно совместимых процессов. Приведите пример, иллюстрирующий, что выбор самых коротких процессов среди тех, что совместимы с ранее выбранными, не дает правильного результата. Выполните такое же задание для подходов, в одном из которых всегда выбирается процесс, совместимый с ранее выбранными и перекрывающийся с минимальным количеством оставшихся, а в другом — совместимый с ранее выбранными процесс, который начинается раньше других.
16.2 Элементы жадной стратегии Жадный алгоритм позволяет получить оптимальное решение задачи путем осуществления ряда выборов. В каждой точке принятия решения в алгоритме делается выбор, который в данный момент выглядит самым лучшим. Эта эвристическая стратегия не всегда дает оптимальное решение, но все же решение может оказаться и оптимальным, в чем мы смогли убедиться на примере задачи о выборе процессов. В настоящем разделе обсуждаются некоторые общие свойства жадных методов. Процесс разработки жадного алгоритма, рассмотренный в разделе 16.1, несколько сложнее„чем обычно.
Были пройдены перечисленные ниже этапы. 1. Определена оптимальная подструктура задачи. 2. Разработано рекурсивное решение. 3. Доказано, что на любом этапе рекурсии один из оптимальных выборов является жадным. Из этого следует, что всегда можно делать жадный выбор. 4. Показано, что все возникающие в результате жадного выбора подзацачи, кроме одной, — пустые. 5. Разработан рекурсивный алгоритм, реализующий жадную стратегию. 6. Рекурсивный алгоритм преобразован в итеративный. Часть 1Ч.
Усовершенствованные методы разработки и анализа 454 В ходе выполнения этих этапов мы во всех подробностях смогли рассмотреть, как динамическое программирование послужило основой для жадного алгоритма. Однако обычно на практике при разработке жадного алгоритма эти этапы упрощаются. Мы разработали подструктуру так, чтобы в результате жадного выбора оставалась только одна подзадача, подлежащая оптимальному решению. Например, в задаче о выборе процессов сначала определяются подзадачи ЯО, в которых изменяются оба индекса, — и г, и з'. Потом мы выяснили, что если всегда делается жадный выбор, то подзадачи можно было бы ограничить видом Я; „еп Можно предложить альтернативный подход, в котором оптимальная подструктура приспосабливалась бы специально для жадного выбора — т.е. второй индекс можно было бы опустить и определить подзадачи в виде Я; = (аь е Я: )'; < вь).
Затем можно было бы доказать, что жадный выбор (процесс, который оканчивается первым в задаче Я;) в сочетании с оптимальным решением для множества Я остальных совместимых между собой процессов приводит к оптимальному решению задачи Яо Обобщая сказанное, опишем процесс разработки жадных алгоритмов в виде последовательности перечисленных ниже этапов. 1. Привести задачу оптимизации к виду, югда после сделанного выбора остается решить только одну подзадачу. 2.
Доказать, что всегда существует такое оптимальное решение исходной задачи, которое можно получить путем жадного выбора, так что такой выбор всегда допустим. 3. Показать, что после жадного выбора остается подзадача, обладающая тем свойством, что объединение оптимального решения подзадачи со сделанным жадным выбором приводит к оптимальному решению исходной задачи. Описанный выше упрощенный процесс будет использоваться в последующих разделах данной главы. Тем не менее, заметим, что в основе каждого жадного алгоритма почти всегда находится более сложное решение в стиле динамичесюго программирования. Как определить, способен ли жадный алгоритм решить стоящую перед нами задачу оптимизации? Общего пути здесь нет, однако можно выделить две основные составляющие — свойство жадного выбора и оптимальную подструктуру. Если удается продемонстрировать, что задача обладает двумя этими свойствами, то с большой вероятностью для нее можно разработать жадный алгоритм.
Свойство жадного выбора Первый из названных выше основных составляющих жадного алгоритма— свойство жад>сего выбора: глобальное оптимальное решение можно получить, делая локальный оптимальный 1жадный) выбор. Другими словами, рассуждая по поводу того, какой выбор следует сделать, мы делаем выбор, который кажется Глава 16. Жадные алгоритмы 455 самым лучшим в текущей задаче; результаты возникающих подзадач при этом не рассматриваются.
Рассмотрим отличие жадных алгоритмов от динамического программирования. В динамическом программировании на каждом этапе делается выбор, однако обычно этот выбор зависит от решений подзадач. Следовательно, методом динамического программирования задачи обычно решаются в восходящем направлении, т.е. сначала обрабатываются более простые подзадачи, а затем — более сложные. В жадном алгоритме делается выбор, который выглядит в данный момент наилучшим, после чего решается подзадача, возникающая в результате этого выбора.
Выбор, сделанный в жадном алгоритме, может зависеть от сделанных ранее выборов, но он не может зависеть от каких бы то ни было выборов или решений последующих подзадач. Таким образом, в отличие от динамического программирования, где подзадачи решаются в восходящем порядке, жадная стратегия обычно разворачивается в нисходящем порядке, когда жадный выбор делается один за другим, в результате чего каждый экземпляр текущей задачи сводится к более простому. Конечно же, необходимо доказать, что жадный выбор на каждом этапе приводит к глобальному оптимальному решению, и здесь потребуются определенные интеллектуальные усилия.
Обычно, как это было в теореме 16.1, в таком доказательстве исследуется глобальное оптимальное решение некоторой подзадачи. Затем демонстрируется, что решение можно преобразовать так, чтобы в нем использовался жадный выбор, в результате чего получится аналогичная, но более простая подзадача. Свойство жадного выбора часто дает определенное преимущество, позволяющее повысить эффективность выбора в подзадаче. Например, если в задаче о выборе процессов предварительно отсортировать процессы в порядке монотонного возрастания моментов их окончания, то каждый из них достаточно рассмотреть всего один раз. Зачастую оказывается, что благодаря предварительной обработке входных данных или применению подходящей структуры данных (нередко это очередь с приоритетами) можно ускорить процесс жадного выбора, что приведет к повышению эффективности алгоритма.
Оптимальная подструктура Оптимальная подструктура проявляется в задаче, если в ее оптимальном решении содержатся оптимальные решения подзадач. Это свойство является основным признаком применимости как динамического программирования, так и жадных алгоритмов. В качестве примера оптимальной подструктуры напомним результаты раздела 1б.1. В нем было продемонстрировано, что если оптимальное решение подзадачи Я; содержит процесс аы то оно также содержит оптимальные решение подзадач Я;ь и Яьз. После выявления этой оптимальной подструктуры Часть 1Ч. Усовершенствованные методы разработки и анализа 456 было показано, что если известно, какой процесс используется в качестве процесса аь, то оптимальное решение задачи Я; можно построить путем выбора процесса аь и объединения его со всеми процессами в оптимальных решениях подзадач Ягь и Яь . На основе этого наблюдения удалось получить рекуррентиое соотношение (16.3), описывающее оптимальное решение.
Обычно при работе с жадными алгоритмами применяется более простой подход. Как уже упоминалось, мы воспользовались предположением, что подзадача получилась в результате жадного выбора в исходной задаче. Все, что осталось сделать, — это обосновать, что оптимальное решение подзадачи в сочетании с ранее сделанным жадным выбором приводит к оптимальному решению исходной задачи. В этой схеме для доказательства того, что жадный выбор на каждом шаге приводит к оптимальному решению, неявно используется индукция по вспомогательным задачам. Сравнение жадных алгоритмов и динамического программирования Поскольку свойство оптимальной подструктуры применяется и в жадных алгоритмах, и в стратегии динамического программирования, может возникнуть соблазн разработать решение в стиле динамического программирования для задачи, в которой достаточно применить жадное решение.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
