Методы разработки алгоритмов. «Жадные» алгоритмы

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

     Говоря  иными словами, решаемые с помощью  жадных алгоритмов задачи обладают свойством  оптимальности для подзадач  (have optimal substructure): оптимальное решение всей задачи содержит в себе оптимальные решения подзадач. (С этим свойством мы уже встречались, говоря о динамическом программировании). Например, при доказательстве теоремы 1 мы видели, что если А – оптимальный набор заявок, содержащий заявку номер 1, то А’=A \{1} – оптимальный набор заявок для меньшего множества заявок S’, состоящего из тех заявок, для которых s_i ³ f₁. 

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

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

       Дискретная задача о рюкзаке  (0-1 knapsack problem) состоит в следующем. Пусть вор пробрался на склад, на котором хранится n вещей. Вещь номер i  стоит v_i  долларов и весит w_i  килограммов (v_i и w_i - целые числа). Вор хочет украсть товара на максимальную сумму, причем максимальный вес, который он может унести в рюкзаке, равен W ( число W тоже целое). Что он должен положить в рюкзак?

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

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

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

   Чтобы  убедиться в том, что аналогичный  жадный алгоритм не обязан давать оптимум в дискретной задаче о рюкзаке, взгляните на рис. 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