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

>>> 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. В этой задаче коммивояжер должен был посетить пять разных городов.

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

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

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

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

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

Однако в каких-то ситуациях начальный город не задан. Допустим, вы работаете в курьерской службе FedEx и должны доставить пакет в пределах города. Пакет перевозится из Чикаго в один из 50 филиалов FedEx. Затем пакет будет перегружен в машину, которая разъезжает по разным местам и доставляет пакеты. В какой филиал отгрузить пакет? На этот раз начальная точка неизвестна, и в задаче о коммивояжере вам придется вычислить как оптимальный путь, так и начальную точку.

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

Два города = два возможных маршрута.

Сколько маршрутов?

На первый взгляд может показаться, что это один маршрут. Разве расстояние СФ>Марин не совпадает с расстоянием Марин>СФ? Не всегда. В некоторых городах (в том числе и в Сан-Франциско) много улиц с односторонним движением, и тогда вам не удается вернуться по тому пути, по которому вы приехали. Иногда приходится проехать лишнюю пару миль, чтобы найти выезд на шоссе. Так что эти два маршрута не всегда совпадают.

Три города

Теперь добавим к двум городам еще один. Сколько возможных маршрутов существует в этой конфигурации?

Если начать в Беркли, вы можете посетить два города.

Всего шесть возможных маршрутов: по два для каждого города, с которого вы можете начать.

Итак, три города = шесть возможных маршрутов.

Четыре города

Добавим еще один город — Фремонт. Теперь допустим, что вы начали с Фремонта.

Мы знаем, что во Фремонте начинаются шесть возможных маршрутов. Ого! Да они очень похожи на шесть маршрутов, которые вы вычислили ранее, когда городов было всего три! Только теперь во всех маршрутах появился дополнительный город, Фремонт! Начинает проявляться закономерность. Предположим, из четырех городов выбирается начальный город Фремонт. Остается еще три города. И вы знаете, что для перемещения между тремя городами есть шесть разных маршрутов. Итак, если начать с Фремонта, существуют шесть возможных маршрутов. Также возможно начать с одного из других городов.

Четыре возможных начальных города, шесть возможных маршрутов для каждого начального города = 4 × 6 = 24 возможных маршрута.

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