Оптимальность для подзадач

Принцип жадного выбора

Когда применим жадный алгоритм

Общих рецептов определения, применимости жадного алгоритма нет, но существуют две особенности, характерные для задач, решаемых жадными алгоритмами. Это принцип жадного выбора и свойство оптимальности для подзадач.

Говорят, что к оптимизационной задаче применим принцип жадного выбора, если последовательность локально оптимальных (жадных) выборов дает глобально оптимальное решение. Различие между жадными алгоритмами и динамическим программированием можно пояснить так: на каждом шаге жадный алгоритм берёт «самый жирный кусок», а потом уже пытается сделать наилучший выбор среди оставшихся, каковы бы они ни были; алгоритм динамического программирования принимает решение, просчитав заранее последствия для всех вариантов.

Как доказать, что жадный алгоритм даёт оптимальное решение? Это не всегда тривиально, но в типичном случае такое доказательство следует схеме, использованной в задаче о заявках. Сначала мы доказываем, что жадный выбор на первом шаге не закрывает пути к оптимальному решению: для всякого решения есть другое, согласованное с жадным выбором и не худшее первого. Затем показывается, что подзадача, возникающая после жадного выбора на первом шаге, аналогична исходной, и рассуждение завершается по индукции.

Говоря иными словами, решаемые с помощью жадных алгоритмов задачи обладают свойством оптимальности для подзадач: оптимальное решение всей задачи содержит в себе оптимальные решения подзадач. (С этим свойством мы уже встречались, говоря о динамическом программировании.) Например, задаче о заявках мы видели, что если — оптимальный набор заявок, содержащий заявку номер 1, то — оптимальный набор заявок для меньшего множества заявок , состоящего из тех заявок, для которых .

2.2.3 Жадный алгоритм или динамическое программирование?

И жадные алгоритмы, и динамическое программирование основываются на свойстве оптимальности для подзадач, поэтому может возникнуть искушение применить динамическое программирование в ситуации, где хватило бы жадного алгоритма или напротив, применить жадный алгоритм к задаче, в которой он не даст оптимума. Проиллюстрируем возможные ловушки на примере двух вариантов классической оптимизационной задачи.

Дискретная задача о рюкзаке состоит в следующем. На складе хранится вещей. Вещь номер стоит гривен и весит килограммов (- целые числа). Необходимо набрать в рюкзак товара на максимальную сумму, причём максимальный вес, который можно унести в рюкзаке, равен (число тоже целое). Что нужно положить в рюкзак?

Непрерывная задача о рюкзаке отличается от дискретной тем, что можно дробить товары на части и укладывать в рюкзак эти части, а не обязательно вещи целиком (если в дискретной задаче мы имеем дело с золотыми слитками, то в непрерывной — с золотым песком).

Обе задачи о рюкзаке обладают свойством оптимальности для подзадач. В самом деле, рассмотрим дискретную задачу. Вынув вещь номер из оптимально загруженного рюкзака, получим решение задачи о рюкзаке с максимальным весом и набором из вещи (все вещи, кроме -ой). Аналогичное рассуждение проходит и для непрерывной задачи: вынув из оптимально загруженного рюкзака, в котором лежит килограммов товара номер , весь этот товар, получим оптимальное решение непрерывной задачи, в которой максимальный вес равен (вместо ), а количество -готовара равно (вместо ).

Хотя две задачи о рюкзаке и похожи, жадный алгоритм даёт оптимум в непрерывной задаче о рюкзаке и не даёт в дискретной. В самом деле, решение непрерывной задачи о рюкзаке с помощью жадного алгоритма выглядит так. Вычислим цены (в расчёте на килограмм) всех товаров (цена товара номер равна ). Сначала берём по максимуму самого дорогого товара; если весь этот товар кончился, а рюкзак не заполнен, то берём следующий по цене товар, затем следующий, и так далее, пока не наберём вес . Поскольку товары надо предварительно отсортировать по ценам, на что уйдёт время , время работы описанного алгоритма будет .

Чтобы убедиться в том, что аналогичный жадный алгоритм не обязан давать оптимум в дискретной задаче о рюкзаке, рассмотрим следующий пример. Грузоподъемность рюкзака 50 кг. На складе есть три вещи, весящие 10, 20 и 30 кг и стоящие 60, 100 и 120 гривен соответственно. Цена их в расчёте на единицу веса равна 6, 5 и 4. Жадный алгоритм для начала положит в рюкзак вещь номер 1, а затем 2. Это даст 160 гривен. Но оптимальное решение включает предметы номер 2 и 3 и дает 220 гривен.

Для непрерывной задачи с теми же исходными данными жадный алгоритм даст правильное решение. В дискретной задаче, положив предмет номер 1, мы лишаемся возможности заполнить рюкзак «под завязку», а пустое место снижает цену товаров в рюкзаке. Здесь, чтобы решить, стоит ли класть вещь в рюкзак, следует рассмотреть две подзадачи: если данная вещь заведомо лежит в рюкзаке и если вещи заведомо нет. Тем самым дискретная задача порождает множество перекрывающихся подзадач – типичный признак того, что может пригодиться динамическое программирование. И действительно, в данном случае оно применимо.

Введем величину - максимальную стоимость множества товаров, чьи номера не превышают (), а суммарная масса точно равна (). Тогда максимальная стоимость товаров, которые можно положить в рюкзак, есть .

Определим формулы для расчета .

Для значение при равно 0. Если (т.е. товар номер 1 помещается в рюкзак), то следует положить - это стоимость единственного товара с номером 1, который положили в рюкзак.

Для значение рассчитывается следующим образом. Если положить товар в рюкзак (а это можно сделать, если ), то максимальная набираемая стоимость составит . Если же товар в рюкзак не класть, то максимальная набираемая стоимость есть . Таким образом, получим формулу

.

Получаем следующий алгоритм. Проходим по от 1 до включительно. Для каждого перебираем от 0 до и применяем выведенные выше формулы. Перебрав все , выбираем - это максимальная стоимость. Запомним , которое приносим максимум . Теперь, перебирая от до 1, определяем, какие товары нужно было положить в рюкзак. Для каждого выполняем следующие действия. Если , то товар в рюкзак класть не следует. Иначе если , то товар в рюкзак класть также не следует. Иначе кладем товар в рюкзак и полагаем .