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