После того, как мы договорились рассматривать только наборы, содержащие заявку номер 1, все несовместные с ней заявки можно выкинуть, и задача сводится к выбору оптимального набора заявок из множества оставшихся заявок (совместных с заявкой номер 1). Другими словами, мы свели задачу к аналогичной задаче с меньшим числом заявок. Рассуждая по индукции, получаем, что, делая на каждом шаге жадный выбор, мы придем к оптимальному решению.
Когда применим жадный алгоритм?
Как узнать, даст ли жадный алгоритм оптимум применительно к данной задаче? Общих рецептов тут нет, но существует две особенности, характерные для задач, решаемых жадными алгоритмами. Это принцип жадного выбора и свойство оптимальности для подзадач.
Говорят, что к оптимизационной задаче применим принцип жадного выбора (greedy-choiceproperty), если последовательность локально оптимальных (жадных) выборов дает глобально оптимальное решение. Различие между жадными алгоритмами и динамическим программированием можно пояснить так: на каждом шаге жадный алгоритм берет "самый жирный кусок", а потом уже пытается сделать наилучший выбор среди оставшихся, каковы бы они ни были; алгоритм динамического программирования принимает решение, просчитав заранее последствия для всех вариантов.
Как доказать, что жадный алгоритм дает оптимальное решение? Это не всегда тривиально, но в типичном случае такое доказательство следует схеме, использованной в доказательстве теоремы 1. Сначала мы доказываем, что жадный выбор на первом шаге не закрывает пути к оптимальному решению: для всякого решения есть другое, согласованное с жадным выбором и не худшее первого. Затем показывается, что подзадача, возникающая после жадного выбора на первом шаге, аналогична исходной, и рассуждение завершается по индукции.
Говоря иными словами, решаемые с помощью жадных алгоритмов задачи обладают свойством оптимальности для подзадач (haveoptimalsubstructure): оптимальное решение всей задачи содержит в себе оптимальные решения подзадач. (С этим свойством мы уже встречались, говоря о динамическом программировании). Например, при доказательстве теоремы 1 мы видели, что если А – оптимальный набор заявок, содержащий заявку номер 1, то А’=A \{1} – оптимальный набор заявок для меньшего множества заявок S’, состоящего из тех заявок, для которых si³f1.
Жадный алгоритм или динамическое программирование?
И жадные алгоритмы, и динамическое программирование основываются на свойстве оптимальности для подзадач, поэтому может возникнуть искушение применить динамическое программирование в ситуации, где хватило бы жадного алгоритма, или, напротив, применить жадный алгоритм к задаче, в которой он не даст оптимума. Мы проиллюстрируем возможные ловушки на примере двух вариантов классической оптимизационной задачи.
Дискретная задача о рюкзаке (0-1 knapsackproblem) состоит в следующем. Пусть вор пробрался на склад, на котором хранится n вещей. Вещь номер i стоит viдолларов и весит wi килограммов (vi и wi - целые числа). Вор хочет украсть товара на максимальную сумму, причем максимальный вес, который он может унести в рюкзаке, равен W ( число W тоже целое). Что он должен положить в рюкзак?
Непрерывная задача о рюкзаке ( fractionalknapsackproblem)) отличается от дискретной тем, что вор может дробить краденые товары на части и укладывать в рюкзак эти части, а не обязательно вещи целиком (если в дискретной задаче вор имеет дело с золотыми слитками, то в непрерывной – с золотым песком).
Обе задачи о рюкзаке обладают свойством оптимальности для подзадач. В самом деле, рассмотрим дискретную задачу. Вынув вещь номер j из оптимально загруженного рюкзака, получим решение задачи о рюкзаке с максимальным весом W – wj и набором из n-1 вещи ( все вещи, кроме j-й). Аналогичное рассуждениеподходит и для непрерывной задачи: вынув из оптимально загруженного рюкзака, в котором лежит w килограммов товара номер j, весь этот товар, получим оптимальное решение непрерывной задачи, в которой максимальный вес равен W-w(вместо W), а количествоj-го товара равно wj-w( вместо wj).
Хотя две задачи о рюкзаке и похожи, жадный алгоритм дает оптимум в непрерывной задаче о рюкзаке и не дает в дискретной. В самом деле, решение непрерывной задачи о рюкзаке с помощью жадного алгоритма выглядит так. Вычислим цены (в расчете на килограмм) всех товаров (цена товара номер i равна vi/wi ). Сначала вор берет по максимуму самого дорогого товара; если весь этот товар кончился, а рюкзак не заполнен, вор берет следующий по цене товар, затес следующий, и так далее, пока не наберет вес W. Поскольку товары надо предварительно отсортировать по ценам, на что уйдет время О(nlogn), время работы описанного алгоритма будет О(nlogn).
Чтобы убедиться в том, что аналогичный жадный алгоритм не обязан давать оптимум в дискретной задаче о рюкзаке, взгляните на рис. 2(а). Грузоподъемность рюкзака 50кг, на складе имеются три вещи, весящие 10, 20 и 30кг и стоящие 60, 100 и 120 долларов соответственно. Цена их в расчете на единицу веса равна 6,5 и 4. Жадный алгоритм для начала положит в рюкзак вещь номер 1; однако оптимальное решение включает предметы номер 2 и 3.
Для непрерывной задачи с теми же исходными данными жадный алгоритм, предписывающий начать с товара номер 1, дает оптимальное решение (рис. 2(в)). В дискретной задаче такая стратегия не срабатывает: положив в рюкзак предмет номер 1, вор лишается возможности заполнить рюкзак «под завязку», а пустое место в рюкзаке снижает цену наворованного в расчете на единицу веса. Здесь, чтобы решить, класть ли данную вещь в рюкзак, надо сравнить решения двух подзадач: когда данная вещь заведомо лежит в рюкзаке и когда этой вещи в рюкзаке заведомо нет. Тем самым дискретная задача о рюкзаке порождает множество перекрывающихся подзадач – типичный признак того, что может пригодиться динамическое программирование. И действительно, к дискретной задаче о рюкзаке оно применимо .
Рис. 2. В дискретной задаче о рюкзаке жадная стратегия может не сработать. (а) Вор должен выбрать две вещи из трех с тем, чтобы их суммарный вес не превысил 50кг. (б) Оптимальный выбор – вторая и третья вещи; если положить в рюкзак первую, то выбор оптимальным не будет, хотя именно она дороже всех в расчете на единицу веса. (в) Для непрерывной задачи о рюкзаке с теми же исходными данными выбор товаров в порядке убывания цены на единицу веса будет оптимален.
В результате исследования литературы по вопросу оптимизации задач, мы отдали предпочтение использованию «жадных алгоритмов», которые дают нам следующие возможности:
-Сократить время принятия решения
-Проверять все возможные варианты решения на данный момент времени.
Литература
1. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Глава 16. Жадные алгоритмы
2. Кормен Т и др. Алгоритмы: построение и анализ. – М.: МЦНМО, 2000
3. Алфёрова З.В. Теория алгоритмов. – М.: Статистика, 1973