локально-оптимальное решение, а в итоге вы получаете глобально-оптимальное решение. Хотите верьте, хотите нет, но этот простой алгоритм успешно находит оптимальное решение задачи составления расписания!
Конечно, жадные алгоритмы работают не всегда. Но они так просто реализуются! Рассмотрим другой пример.
Задача о рюкзаке
Представьте, что вы жадный воришка. Вы забрались в магазин с рюкзаком, и перед вами множество товаров, которые вы можете украсть. Однако емкость рюкзака не бесконечна: он выдержит не более 35 фунтов.
Требуется подобрать набор товаров максимальной стоимости, которые можно сложить в рюкзак. Какой алгоритм вы будете использовать?
И снова жадная стратегия выглядит очень просто:
1. Выбрать самый дорогой предмет, который поместится в рюкзаке.
2. Выбрать следующий по стоимости предмет, который поместится в рюкзаке… И так далее.
Вот только на этот раз она не работает! Предположим, есть три предмета.
В рюкзаке поместятся товары общим весом не более 35 фунтов. Самый дорогой товар — магнитофон, вы выбираете его. Теперь ни для чего другого места уже не осталось.
Вы набрали товаров на $3000. Погодите-ка! Если бы вместо магнитофона вы выбрали ноутбук и гитару, то стоимость добычи составила бы $3500!
Очевидно, жадная стратегия не дает оптимального решения. Впрочем, результат не так уж далек от оптимума. В следующей главе я расскажу, как вычислить правильное решение. Но вор, забравшийся в магазин, вряд ли станет стремиться к идеалу. «Достаточно хорошего» решения должно хватить.
Второй пример приводит нас к следующему выводу: иногда идеальное — враг хорошего. В некоторых случаях достаточно алгоритма, способного решить задачу достаточно хорошо. И в таких областях жадные алгоритмы работают просто отлично, потому что они просто реализуются, а полученное решение обычно близко к оптимуму.
Упражнения
8.1 Вы работаете в фирме по производству мебели и поставляете мебель по всей стране. Коробки с мебелью размещаются в грузовике. Все коробки имеют разный размер, и вы стараетесь наиболее эффективно использовать доступное пространство. Как выбрать коробки для того, чтобы загрузка имела максимальную эффективность? Предложите жадную стратегию. Будет ли полученное решение оптимальным?
8.2 Вы едете в Европу, и у вас есть семь дней на знакомство с достопримечательностями. Вы присваиваете каждой достопримечательности стоимость в баллах (насколько вы хотите ее увидеть) и оцениваете продолжительность поездки. Как обеспечить максимальную стоимость (увидеть все самое важное) во время поездки? Предложите жадную стратегию. Будет ли полученное решение оптимальным?
Рассмотрим еще один пример, в котором без жадных алгоритмов практически не обойтись.
Задача о покрытии множества
Вы открываете собственную авторскую программу на радио и хотите, чтобы вас слушали во всех 50 штатах. Нужно решить, на каких радиостанциях должна транслироваться ваша передача. Каждая станция стоит денег, поэтому количество станций необходимо свести к минимуму. Имеется список станций.
Каждая станция покрывает определенный набор штатов, эти наборы перекрываются.
Как найти минимальный набор станций, который бы покрывал все 50 штатов? Вроде бы простая задача, верно? Оказывается, она чрезвычайно сложна. Вот как это делается:
1. Составить список всех возможных подмножеств станций — так называемое степенное множество. В нем содержатся 2^n возможных подмножеств.
2. Из этого списка выбирается множество с наименьшим набором станций, покрывающих все 50 штатов.
Проблема в том, что вычисление всех возможных подмножеств станций займет слишком много времени. Для n станций оно потребует времени O(2^n). Если станций немного, скажем от 5 до 10, — это допустимо. Но подумайте, что произойдет во всех рассмотренных примерах при большом количестве элементов. Предположим, вы можете вычислять по 10 подмножеств в секунду.
Не существует алгоритма, который будет вычислять подмножества с приемлемой скоростью! Что же делать?
Приближенные алгоритмы
На помощь приходят жадные алгоритмы! Вот как выглядит жадный алгоритм, который выдает результат, достаточно близкий к оптимуму:
1. Выбрать станцию, покрывающую наибольшее количество штатов, еще не входящих в покрытие. Если станция будет покрывать некоторые штаты, уже входящие в покрытие, это нормально.
2. Повторять, пока остаются штаты, не входящие в покрытие.
Этот алгоритм является приближенным. Когда вычисление точного решения занимает слишком много времени, применяется приближенный алгоритм. Эффективность приближенного алгоритма оценивается по:
• быстроте;
• близости полученного решения к оптимальному.
Жадные алгоритмы хороши не только тем, что они обычно легко формулируются, но и тем, что простота обычно оборачивается быстротой выполнения. В данном случае жадный алгоритм выполняется за время O(n^2), где n — количество радиостанций.
А теперь посмотрим, как эта задача выглядит в программном коде.
Подготовительный код
В этом примере для простоты будет использоваться небольшое подмножество штатов и станций.
Сначала составьте список штатов:
states_needed = set(["mt", "wa", "or", "id", "nv", "ut",
"ca", "az"]) Переданный массив преобразуется в множество
В этой реализации я использовал множество. Эта структура данных похожа на список, но каждый элемент может встречаться в множестве не более одного раза. Множества не содержат дубликатов. Предположим, имеется следующий список:
>>> arr = [1, 2, 2, 3, 3, 3]
Этот список преобразуется в множество:
>>> set(arr)
set([1, 2, 3])
Значения 1, 2 и 3 встречаются в списке по одному разу.
Также понадобится список станций, из которого будет выбираться покрытие. Я решил воспользоваться хешем:
stations = {}
stations["kone"] = set(["id", "nv", "ut"])
stations["ktwo"] = set(["wa", "id", "mt"])
stations["kthree"] = set(["or", "nv", "ca"])
stations["kfour"] = set(["nv", "ut"])
stations["kfive"] = set(["ca", "az"])
Ключи — названия станций, а значения — сокращенные обозначения штатов, входящих в зону охвата. Таким образом, в данном примере станция kone вещает в штатах Айдахо (id), Невада (nv) и Юта (ut). Все значения являются множествами. Как вы вскоре увидите, хранение данных во множествах упрощает работу.
Наконец, нам понадобится структура данных для хранения итогового набора станций:
final_stations = set()
Вычисление ответа
Теперь необходимо вычислить набор используемых станций. Взгляните на диаграмму и попробуйте предсказать, какие станции следует использовать.
Учтите, что правильных решений может быть несколько. Вы перебираете все станции и выбираете ту, которая обслуживает больше всего штатов, не входящих в текущее покрытие. Будем называть ее best_station:
best_station = None
states_covered = set()
for station, states_for_station in stations.items():
Множество states_covered содержит все штаты, обслуживаемые этой станцией, которые еще не входят в текущее покрытие. Цикл for перебирает все станции и находит среди них наилучшую. Рассмотрим тело цикла for:
covered = states_needed & states_for_station
if len(covered) > len(states_covered)
Новый синтаксис! Эта операция называется "пересечением множеств"
best_station = station
states_covered = covered
В коде встречается необычная строка:
covered = states_needed & states_for_station
Что здесь происходит?
Множества
Допустим, имеется множество с названиями фруктов.
Также имеется множество с названиями овощей.
С двумя множествами можно выполнить ряд интересных операций.
• Объединение множеств означает слияние элементов обоих множеств.
• Под операцией пересечения множеств понимается поиск элементов, входящих в оба множества (в данном случае — только помидор).
• Под разностью множеств понимается исключение из одного множества элементов, присутствующих в другом множестве.
Пример:
>>> fruits = set(["avocado", "tomato", "banana"])
>>> vegetables = set(["beets", "carrots", "tomato"])
>>> fruits | vegetables Объединение множеств
set(["avocado", "beets", "carrots", "tomato", "banana"])
>>> fruits & vegetables Пересечение множеств
set(["tomato"])
>>> fruits – vegetables Разность множеств
set(["avocado", "banana"])
>>> vegetables – fruits Как вы думаете, как будет выглядеть результат?
Еще раз напомню основные моменты:
• множества похожи на списки, но множества не содержат дубликатов;
• с множествами можно выполнять различные интересные операции — вычислять их объединение, пересечение и разность.
Вернемся к коду
Продолжим рассматривать исходный пример.
Пересечение множеств:
covered = states_needed & states_for_station
Множество covered содержит штаты, присутствующие как в states_needed, так и в states_for_station. Таким образом, covered — множество штатов, не входящих в покрытие, которые покрываются текущей станцией! Затем мы проверяем, покрывает ли эта станция больше штатов, чем текущая станция best_station:
if len(covered) > len(states_covered):
best_station = station
states_covered = covered
Если условие выполняется, то станция сохраняется в best_station. Наконец, после завершения цикла best_station добавляется в итоговый список станций:
final_stations.add(best_station)
Также необходимо обновить содержимое states_needed. Те штаты, которые входят в зону покрытия станции, больше не нужны: