Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 90
Текст из файла (страница 90)
В этой работе приведен алгоритм, время работы которого равно О (пз). Ахо (АЬо), Хопкрофт (Норсгой) и Ульман ((Л1гпап) (5] представили алгоритм, описанный в разделе 15.5. Упражнение 15.5-4 предложено Кнутом (184]. Ху и Такер (Тис1сег) (161] разработали алгоритм для случая, когда все вероятности р; равны 0; время работы этого алгоритма равно О (пз), а количество необходимой для него памяти — О (и). Впоследствии Кнуту (185] удалось уменьшить это время до величины О(п18п). ГЛАВА 16 Жадные алгоритмы Алгоритмы, предназначенные для решения задач оптимизации, обычно представляют собой последовательность шагов, на каждом из которых предоставляется некоторое множество выборов.
Определение наилучшего выбора, руководствуясь принципами динамического программирования, во многих задачах оптимизации напоминает стрельбу из пушки по воробьям; другими словами, для этих задач лучше подходят более простые и эффективные алгоритмы. В жадном алгориигме (атеей а1яог1йш) всегда делается выбор, который кажется самым лучшим в данный момент — т.е. производится локально оптимальный выбор в надежде, что он приведет к оптимальному решению глобальной задачи. В этой главе рассматриваются задачи оптимизации, пригодные для решения с помощью жадных алгоритмов.
Перед освоением главы следует ознакомиться с динамическим программированием, изложенным в главе 15, в частности, с разделом 15.3. Жадные алгоритмы не всегда приводят к оптимальному решению, но во многих задачах они дают нужный результат. В разделе 16.1 рассматривается простая, но нетривиальная задача о выборе процессов, эффективное решение которой можно найти с помощью жадного алгоритма. Чтобы прийти к жадному алгоритму, сначала будет рассмотрено решение, основанное на парадигме динамического программирования„после чего будет показано, что оптимальное решение можно получить, исходя из принципов жадных алгоритмов. В разделе 16.2 представлен обзор основных элементов подхода, в соответствии с которым разрабатываются жадные алгоритмы.
Это позволит упростить обоснование корректности жадных алгоритмов, не используя при этом сравнение с динамическим программированием, как это делается в разделе 16.1. В разделе 16.3 приводится важное приложение методов жадного программирования: разработка кодов Хаффмана (НпПшап) для Глава 16. Жадные алгоритмы 443 сжатия данных. В разделе 16.4 исследуются теоретические положения„на которых основаны комбинаторные структуры, известные под названием "матроиды", для которых жадный алгоритм всегда дает оптимальное решение. Наконец, в разделе 16.5 матроиды применяются для решения задачи о составлении расписания заданий равной длительности с предельным сроком и штрафами. Жадный метод обладает достаточной мощью и хорошо подходит для довольно широкого класса задач.
В последующих главах представлены многие алгоритмы, которые можно рассматривать как применение жадного метода, включая алгоритмы поиска минимальных остовных деревьев (ш!и!шшп-зрапп!пп-ггее) (глава 23), алгоритм Дейкстры (Р!)кз1га) для определения кратчайших путей из одного источника (глава 24) и эвристический жадный подход Чватала (Сача!а!) к задаче о покрытии множества (зег-сочеппя) (глава 35). Алгоритмы поиска минимальных остовных деревьев являются классическим примером применения жадного метода. Несмотря на то, что эту главу и главу 23 можно читать независимо друг от друга, может оказаться полезно читать их одна за другой.
16.1 Задача о выборе процессов В качестве первого примера рассмотрим задачу о составлении расписания для нескольких конкурирующих процессов, каждый из которых безраздельно использует общий ресурс. Цель этой задачи — выбор набора взаимно совместимых процессов, образующих множество максимального размера. Предположим, имеется множество Я = (аы аз,..., а„), состоящее из п нронессов (аспч!г!ез).
Процессам требуется некоторый ресурс, который одновременно может использоваться лишь одним процессом. Каждый процесс а; характеризуется начапьньгм моментом в; и конечны,ы моментом Д, где О < в; < Д < со. Будучи выбран, процесс а; длится в течение полуоткрытою интервала времени [в;, Г,). Процессы а, и а совместимы (сошрайЫе), если интервалы [в;, ~г) и [в, Г" ) не перекрываются (т.е, если гч > Д или в > гг). Задача о выборе процессов (асг!ч!гу-зе!ее!!оп ргоЫещ) заключается в том, чтобы выбрать подмножество взаимно совместимых процессов, образующих множество максимального размера. Например, рассмотрим описанное ниже множество Я процессов, отсортированных в порядке возрастания моментов окончания: (Вскоре станет понятно, почему удобнее рассматривать процессы, расположенные именно в таком порядке.) В данном примере из взаимно совместимых процессов можно составить подмножество (аз, аэ, аы).
Однако оно не является максимапь- Часть 1Ч. Усовершенствованные методы разработки и анализа ным, поскольку существует подмножество (иы и4, ав, ам 1, состоящее из большего количества элементов. Еше одно такое подмножество — (аз, а4, аш аы1. Разобьем решение этой задачи на несколько этапов. Начнем с того, что сформулируем решение рассматриваемой задачи, основанное на принципах динамического программирования. Это оптимальное решение исходной задачи получается путем комбинирования оптимальных решений подзадач.
Рассмотрим несколько вариантов выбора, который делается в процессе определения подзадачи, использующейся в оптимальном решении. Впоследствии станет понятно, что заслуживает внимания лишь один выбор — жадный — и что когда делается этот выбор, одна из подзадач гарантированно получается пустой. Остается лишь одна непустая подзадача. Исходя из этих наблюдений, мы разработаем рекурсивный жадный алгоритм, предназначенный для решения задачи о составлении расписания процессов. Процесс разработки жадного алгоритма будет завершен его преобразованием из рекурсивного в итерационный. Описанные в этом разделе этапы сложнее, чем те, что обычно имеют место при разработке жадных алгоритмов, однако они иллюстрируют взаимоотношение между жадными алгоритмами и динамическим программированием.
Оптимальная подструктура задачи о выборе процессов Как уже упоминалось, мы начнем с того, что разработаем решение для задачи о выборе процессов по методу динамического программирования. Как и в главе! 5, первый шаг будет состоять в том, чтобы найти оптимальную подструктуру и с ее помощью построить оптимальное решение задачи, пользуясь оптимальными решениями подзадач. В главе 15 мы убедились, что для этого нужно определить подходящее пространство подзадач. Начнем с определения множеств ЯΠ— — (аь Е Я: Л < вь < Ь < ау1. Я; — подмножество процессов из множества 5, которые можно успеть выполнить в промежутке времени между завершением процесса сч и началом процесса а .
Фактически множество Я; состоит из всех процессов, совместимых с процессами и, и и, а также теми, которые оканчиваются не позже процесса а; и теми, которые начинаются нс ранее процесса и . Для представления всей задачи добавим фиктивные процессы ао и а„ч.1 и примем соглашение, что го = О и вь~.1 = со. Тогда Я = Яс „~м а,пдексы 1 и у находятся в диапазоне О < г, т < п + 1. Дополпнтельнь . ограничения диапазонов индексов 1 и 1 можно получить с помощью привсденнь х ниже рассуждений.
Предположим, что процессы отсортированы в порядке возрастания соответствующих им конечных моментов времени: Глава 16. Жадные алгоритмы 445 Утверждается, что в этом случае Я, = И, если т > ?. Почему? Предположим, что существует процесс аь Е Яг для некоторого т > т', так что процесс а, следует после процесса а„если расположить их в порядке сортировки. Однако из определения Я, следует соотношение (, < вь < )ь < в < Д, откуда Х, < Д, что противоречит предположению о том, что процесс а, следует после процесса аз если расположить их в порядке сортировки. Можно прийти к выводу, что если процессы отсортированы в порядке монотонного возрастания времени их окончания, то пространство подзадач образуется путем выбора максимального подмножества взаимно совместимых процессов из множества Я, для О < з < у < и+ 1 (мы знаем, что все прочие ог — пустые).
Чтобы понять подструктуру задачи о выборе процессов, рассмотрим некоторую непустую подзадачу 5; ' н предположим, что ее решение включает некоторый процесс аы так что Г; < аь < Хь < в . С помощью процесса аь генерируются две подзадачи, Я;ь (процессы, которые начинаются после окончания процесса а, н заканчиваются перед началом процесса аь) и Яя (процессы, которые начинаются после окончания процесса аь и заканчиваются перед началом процесса а ), каждая из которых состоит из подмножества процессов, входящих в о'; . Решение задачи ог представляет собой обьединение решений задач авэо Яь и процесса аь.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
