Page 188 - Bkhargava_-_Grokaem_algoritmy

Задача о покрытии множества 187

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

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

Упражнения

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

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

Рассмотрим еще один пример, в котором без жадных алгоритмов практи­
чески не обойтись.

Задача о покрытии множества

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

www.trk.kg