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

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. Сравним время выполнения жадного алгоритма со временем точного алгоритма.

Упражнения

Для каждого из приведенных ниже алгоритмов укажите, является этот алгоритм жадным или нет.

8.3 Быстрая сортировка.

8.4 Поиск в ширину.

8.5 Алгоритм Дейкстры.

NP-полные задачи

Для решения задачи о покрытии множества необходимо вычислить каждое возможное подмножество.

Вероятно, вы вспомнили задачу о коммивояжере из главы 1. В этой задаче коммивояжер должен был посетить пять разных городов.

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

Сколько маршрутов необходимо вычислить для пяти городов?

Задача о коммивояжере — шаг за шагом

Начнем с малого. Допустим, городов всего два. Выбирать приходится всего из двух маршрутов.

Логично спросить: в задаче о коммивояжере существует ли конкретный город, с которого нужно начинать? Допустим, коммивояжер живет в Сан-Франциско и должен посетить еще четыре города. Сан-Франциско должен быть