Адитья Бхаргава – Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих (страница 21)

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"])