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

Задача составления расписания

Допустим, имеется учебный класс, в котором нужно провести как можно больше уроков. Вы получаете список уроков.

Провести в классе все уроки не получится, потому что некоторые из них перекрываются по времени.

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

Вроде бы сложная задача, верно? На самом деле алгоритм оказывается на удивление простым. Вот как он работает:

1. Выбрать урок, завершающийся раньше всех. Это первый урок, который будет проведен в классе.

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

Продолжайте действовать по тому же принципу — и вы получите ответ! Давайте попробуем. Рисование заканчивается раньше всех уроков (в 10:00), поэтому мы выбираем именно его.

Теперь нужно найти следующий урок, который начинается после 10:00 и завершается раньше остальных.

Английский язык отпадает — он перекрывается с рисованием, но математика подходит. Наконец, информатика перекрывается с математикой, но музыка подходит.

Итак, эти три урока должны проводиться в классе.

Я очень часто слышу, что этот алгоритм подозрительно прост. Он слишком очевиден, а значит, должен быть неправильным. Но в этом и заключается красота жадных алгоритмов: они просты! Жадный алгоритм прост: на каждом шаге он выбирает оптимальный вариант. В нашем примере при выборе урока выбирается тот урок, который завершается раньше других. В технической терминологии: на каждом шаге выбирается локально-оптимальное решение, а в итоге вы получаете глобально-оптимальное решение. Хотите верьте, хотите нет, но этот простой алгоритм успешно находит оптимальное решение задачи составления расписания!

Конечно, жадные алгоритмы работают не всегда. Но они так просто реализуются! Рассмотрим другой пример.

Задача о рюкзаке

Представьте, что вы жадный воришка. Вы забрались в магазин с рюкзаком, и перед вами множество товаров, которые вы можете украсть. Однако емкость рюкзака не бесконечна: он выдержит не более 35 фунтов.

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

И снова жадная стратегия выглядит очень просто:

1. Выбрать самый дорогой предмет, который поместится в рюкзаке.

2. Выбрать следующий по стоимости предмет, который поместится в рюкзаке… И так далее.

Вот только на этот раз она не работает! Предположим, есть три предмета.

В рюкзаке поместятся товары общим весом не более 35 фунтов. Самый дорогой товар — магнитофон, вы выбираете его. Теперь ни для чего другого места уже не осталось.

Вы набрали товаров на $3000. Погодите-ка! Если бы вместо магнитофона вы выбрали ноутбук и гитару, то стоимость добычи составила бы $3500!

Очевидно, жадная стратегия не дает оптимального решения. Впрочем, результат не так уж далек от оптимума. В следующей главе я расскажу, как вычислить правильное решение. Но вор, забравшийся в магазин, вряд ли станет стремиться к идеалу. «Достаточно хорошего» решения должно хватить.

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

Упражнения

8.1 Вы работаете в фирме по производству мебели и поставляете мебель по всей стране. Коробки с мебелью размещаются в грузовике. Все коробки имеют разный размер, и вы стараетесь наиболее эффективно использовать доступное пространство. Как выбрать коробки для того, чтобы загрузка имела максимальную эффективность? Предложите жадную стратегию. Будет ли полученное решение оптимальным?

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

>>> 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 возможных маршрута.

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

Сколько возможных маршрутов существует для шести городов? 720, говорите? Да, вы правы. 5040 для 7 городов, 40 320 для 8 городов.

Такая зависимость называется факториальной (помните, что об этом говорилось в главе 3?) Итак, 5! = 120. Допустим, есть 10 городов. Сколько существует возможных маршрутов? 10! = 3 628 800. Уже для 10 городов приходится вычислять более 3 миллионов возможных маршрутов. Как видите, количество возможных маршрутов стремительно растет! Вот почему невозможно вычислить «правильное» решение задачи о коммивояжере при очень большом количестве городов.

У задачи о коммивояжере и задаче покрытия множества есть кое-что общее: вы вычисляете каждое возможное решение и выбираете кратчайшее/минимальное. Обе эти задачи являются NP-полными.

Приближенное решение

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

Я бы сделал это примерно так: начальный город выбирается произвольно, после чего каждый раз, когда коммивояжер выбирает следующий город, он перемещается в ближайший город из тех, что он еще не посещал. Допустим, он начинает в Марине.

Суммарное расстояние — 71 миля. Может, это не самый короткий путь, но он достаточно близок к нему.

Короткое объяснение NP-полноты: некоторые задачи прославились сложностью своего решения. Задача о коммивояжере и задача о покрытии множества — два классических примера. Многие эксперты считают, что написать быстрый алгоритм для решения таких задач невозможно.

Как определить, что задача является NP-полной?

Джон подбирает игроков для своей команды по американскому футболу. У него есть список нужных качеств: хорошо играет в нападении, хорошо играет в защите, хорошо играет под дождем, хорошо играет под давлением и т.д. Также имеется список игроков, в котором каждый игрок обладает определенными качествами.

Джон хочет подобрать команду, которая обладает полным набором качеств, но размер команды ограничен. «Минутку, — осознает Джон, — но ведь это задача покрытия множества!»

Для создания команды Джон может воспользоваться тем же приближенным алгоритмом:

1. Найти игрока с большинством качеств, которые еще не были реализованы.

2. Повторять до тех пор, пока не будут реализованы все качества (или пока не кончатся свободные места в команде).

NP-полные задачи встречаются очень часто. И было бы полезно, если бы вы могли понять, что решаемая задача является NP-полной. В этот момент можно прекратить поиски идеального решения и перейти к решению с применением приближенного алгоритма. Но определить, является ли ваша задача NP-полной, непросто. Обычно различия между легко решаемыми и NP-полными задачами весьма незначительны. Например, в предыдущих главах я много говорил о кратчайших путях. Вы знаете, как вычислить кратчайший путь из точки A в точку B.

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

• ваш алгоритм быстро работает при малом количестве элементов, но сильно замедляется при увеличении их числа;

• формулировка «все комбинации X» часто указывает на NP-полноту задачи;

• вам приходится вычислять все возможные варианты X, потому что задачу невозможно разбить на меньшие подзадачи? Такая задача может оказаться NP-полной;

• если в задаче встречается некоторая последовательность (например, последовательность городов, как в задаче о коммивояжере) и задача не имеет простого решения, она может оказаться NP-полной;

• если в задаче встречается некоторое множество (например, множество радиостанций) и задача не имеет простого решения, она может оказаться NP-полной;

• можно ли переформулировать задачу в условиях задачи покрытия множества или задачи о коммивояжере? В таком случае ваша задача определенно является NP-полной.

Упражнения

8.6 Почтальон должен доставить письма в 20 домов. Ему нужно найти кратчайший путь, проходящий через все 20 домов. Является ли эта задача NP-полной?

8.7 Имеется задача поиска максимальной клики в множестве людей (кликой называется множество людей, каждый из которых знаком со всеми остальными). Является ли эта задача NP-полной?

8.8 Вы рисуете карту США, на которой два соседних штата не могут быть окрашены в одинаковый цвет. Требуется найти минимальное количество цветов, при котором любые два соседних штата будут окрашены в разные цвета. Является ли эта задача NP-полной?

Шпаргалка

• Жадные алгоритмы стремятся к локальной оптимизации в расчете на то, что в итоге будет достигнут глобальный оптимум.

• У NP-полных задач не существует известных быстрых решений.

• Если у вас имеется NP-полная задача, лучше всего воспользоваться приближенным алгоритмом.

• Жадные алгоритмы легко реализуются и быстро выполняются, поэтому из них получаются хорошие приближенные алгоритмы.