Грокаем алгоритмы

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

Упражнения

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()

Вычисление ответа