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

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. Те штаты, которые входят в зону покрытия станции, больше не нужны:

states_needed -= states_covered

Цикл продолжается, пока множество states_needed не станет пустым. Полный код цикла for выглядит так:

while states_needed:

  best_station = None

  states_covered = set()

  for station, states in stations.items():

    covered = states_needed & states

    if len(covered) > len(states_covered):

      best_station = station

      states_covered = covered

states_needed -= states_covered

final_stations.add(best_station)

Остается вывести содержимое final_stations:

>>> print final_stations

set(['ktwo', 'kthree', 'kone', 'kfive'])

Этот результат совпадает с вашими ожиданиями? Вместо станций 1, 2, 3 и 5 можно было выбрать станции 2, 3, 4 и 5. Сравним время выполнения жадного алгоритма со временем точного алгоритма.