Грокаем а Иллюстрированное пособие для программистов и любопытствующих

11:00

ИНФ-КА	10:30	11:30
МУЗЫКА	11:00	12:00

Английский язык отпадает — он перекрывается с рисованием, но матема­тика подходит. Наконец, информатика перекрывается с математикой, но музыка подходит.

РИС.	3:00	10:00
АНГЛ.	3:30	10:30
МАТ-КА	10:00	11:00
ИНФ-КА	10:30	11:30
МУЗЫКА	11:00	12:00

V
X
у
X

Итак, эти три урока должны проводиться в классе.

я
Я
зо Хо 1СУ.5о ₁₂
' ^{1 1} I
РИСОВАНИЕ. МАТЕМАТИКА МУЗЫКА
Я очень часто слышу, что этот алгоритм подозрительно прост. Он слишком очевиден, а значит, должен быть неправильным. Но в этом и заключается красота жадных алгоритмов: они просты! Жадный алгоритм прост: на каж­дом шаге он выбирает оптимальный вариант. В нашем примере при выборе урока выбирается тот урок, который завершается раньше других. В техни­ческой терминологии: на каждом шаге выбирается локально-оптимальное решение, а в итоге вы получаете глобально-оптимальное решение. Хотите верьте, хотите нет, но этот простой алгоритм успешно находит оптимальное решение задачи составления расписания!
Конечно, жадные алгоритмы работают не всегда. Но они так просто реали­зуются! Рассмотрим другой пример.
З
адача о рюкзаке
Представьте, что вы жадный воришка. Вы забрались в магазин с рюкзаком, и перед вами множество товаров, которые вы можете украсть. Однако емкость рюкзака не бесконечна: он выдержит не более 35 фунтов.
Т ребуется подобрать набор то­варов максимальной стоимости,
которые можно сложить в рюкзак, какой алгоритм вы будете использовать?
И снова жадная стратегия выглядит очень просто:

1. 
   Выбрать самый дорогой предмет, который поместится в рюкзаке.
   
2. 
   Выбрать следующий по стоимости предмет, который поместится в рюк­заке... И так далее.
   

В
<и>


НОУТБУК


ГИТАРА
$1500
15фунтов


МАГНИТОФОН
30 фунтов


$2000 2 0 ФУНТОВ

от только на этот раз она не работает! Предположим, есть три предмета.
В рюкзаке поместятся товары общим весом не более 35 фунтов. Самый до­рогой товар — магнитофон, вы выбираете его. Теперь ни для чего другого места уже не осталось.
\
30 ФУНТОВ: МАГНИТОФОН

ОБЩАЯ СТОИМОСТЬ:
43000

ЕМКОСТЬ РЮКЗАКА: 35 ФУНТОВ
5 ФУНТОВ НЕ ИСПОЛЬЗУЮТСЯ
В
15 ФУНТОВ: ГИТАРА


го ФУНТОВ: НОУТБУК


ОБЩАЯ СТОИМОСТЬ: 43500


ы набрали товаров на $3000. Погодите-ка! Если бы вместо магнитофона вы выбрали ноутбук и гитару, то стоимость добычи составила бы $3500!
Очевидно, жадная стратегия не дает оптимального решения. Впрочем, ре­зультат не так уж далек от оптимума. В следующей главе я расскажу, как вы­числить правильное решение. Но вор, забравшийся в магазин, вряд ли станет стремиться к идеалу. «Достаточно хорошего» решения должно хватить.
Второй пример приводит нас к следующему выводу: иногда идеальное — враг хорошего. В некоторых случаях достаточно алгоритма, способного решить задачу достаточно хорошо. И в таких областях жадные алгоритмы работают просто отлично, потому что они просто реализуются, а получен­ное решение обычно близко к оптимуму.
Упражнения

1. 
   Вы работаете в фирме по производству мебели и поставляете мебель по всей стране. Коробки с мебелью размещаются в грузовике. Все коробки имеют разный размер, и вы стараетесь наиболее эффективно использовать доступное пространство. Как выбрать коробки для того, чтобы загрузка имела максимальную эффективность? Предложите жадную стратегию. Будет ли полученное решение оптимальным?
   
2. 
   Вы едете в Европу, и у вас есть семь дней на знакомство с достопри­мечательностями. Вы присваиваете каждой достопримечательности стоимость в баллах (насколько вы хотите ее увидеть) и оцениваете продолжительность поездки. Как обеспечить максимальную стои­мость (увидеть все самое важное) во время поездки? Предложите жадную стратегию. Будет ли полученное решение оптимальным?
   

Рассмотрим еще один пример, в котором без жадных алгоритмов практи­чески не обойтись.
З адача о покрытии множества
Вы открываете собственную авторскую програм­му на радио и хотите, чтобы вас слушали во всех г< 50 штатах. Нужно решить, на каких радиостанци- Шг ях должна транслироваться ваша передача. Каждая n станция стоит денег, поэтому количество станций не­обходимо свести к минимуму. Имеется список станций.