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