Жадные алгоритмы

Жадные алгоритмы

В предыдущей статье был рассмотрен: алгоритм Дейкстры. Здесь далее текст пойдёт о жадных алгоритмах.

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

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

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

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

Попробуйте алгоритм на примере таблицы выше. ИЗО заканчивается раньше всех уроков, поэтому выбираем первым уроком. Далее нужно найти и выбрать следующий урок, который начинается после 9:00 и завершается раньше остальных. Английский отпадает, но алгебра подходит. Наконец, информатика пересекается по времени с алгеброй, но физика подходит. Итак, задача решена, эти три урока должны проводится в классе: ИЗО, алгебра, физика.

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

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

Представьте, что вы богатый покупатель или транжира денежных средств. Вы зашли в магазин или супермаркет с рюкзаком и перед вами множество товаров, которые вы обязательно хотите немедленно купить. Однако, ёмкость вашего рюкзака и ваша грузоподъёмность не бесконечна: примерно рюкзак и соответственно вы сможете понести, допустим, 50 кг(как мешок с цементом)! Вы также хотите купить максимально дорогие вещи! Можно легко представить и противоположную ситуацию — у вас абсолютно нет денег и вы хотите всё украсть и также унести 😁. Но задача одна и состоит в том, чтобы подобрать товары максимальной стоимости, которые вы смогли бы унести в своём рюкзаке. Какой алгоритм использовать? Попробуйте жадный алгоритм:

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

Вот только, как можно было догадаться, на этот раз такая стратегия не приводит к лучшему решению и соответственно она не работает! Допустим вы выбираете самый дорогой товар, например, это музыкальный центр. Вы складываете его в рюкзак и место больше ни для чего не остаётся. Пусть он стоил 1000000 рублей и это был самый дорогой товар в магазине. Но допустим, были также ещё и два товара, стоимостью 750000 и 500000 рублей, которые вдвоём поместились бы в ваш рюкзак. Но согласно алгоритму описанному выше вы бы их уже не купили.

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

Рассмотрим ещё пример, в котором без жадных алгоритмов трудно обойтись.

Задача о покрытии множества

Вы открываете собственную авторскую программу по радио. Нужно только решить на каких радиостанциях должна транслироваться ваша программа. Каждая трансляция на радио стоит денег, поэтому количество станций нужно свести к минимуму с максимальным качеством вещаний. Имеется список станций. Каждая станция покрывает определённый набор областей для вещания, эти наборы перекрываются по областям. Как найти минимальный набор станций, который покрывал бы все 89 субъектов и областей? Задача довольно сложна. Составим алгоритм:

1. Составить список всех возможных подмножеств станций – так называемое степенное множество. В нём содержатся 2^n возможных подмножеств.
2. Из этого списка выбирается множество с наименьшим набором станций, покрывающих все 89 субъектов.

Проблема решения данной задачи состоит в том, что вычисление всех возможных подмножеств станций займёт слишком много времени. Для n станций оно потребует времени O(2^n). Если станций немного, скажем от 5 до 10, — это допустимо. Но подумайте, что произойдёт во всех рассмотренных примерах при большом количестве элементов. Предположим, вы можете вычислять по 10 подмножеств в секунду.

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

Приближённые алгоритмы: реализация

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

1. Выбрать станцию, покрывающую наибольшее количество областей, ещё не входящих в покрытие. Если станция будет покрывать некоторые области, уже входящие в покрытие, это нормально.
2. Повторять, пока останутся области, не входящие в покрытие.

Этот алгоритм является приближённым. Когда вычисление точного решения занимает слишком много времени, применяется приближённый алгоритм. Эффективность приближённого алгоритма оценивается по: быстроте, близости полученного решения к оптимальному.

Жадные алгоритмы хороши не только тем, что они обычно легко формулируются, но и тем, что простота обычно оборачивается скоростью выполнения. В данном случае жадный алгоритм выполняется за время где n – количество радиостанций.

Теперь разберёмся как задача будет выглядеть в программном коде на Python.

Подготовительный код

В этом примере для простоты будет использоваться небольшое подмножество областей и станций. Сначала составим список областей:

# Для обозначения субъектов РФ используются коды
# Переданный массив преобразуется в множество
states_needed = set(["28", "29", "30", "31", "32", "33", "34", "35"])

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

stations = {}
stations["one"] = set(["31", "32", "33"])
stations["two"] = set(["29", "31", "28"])
stations["three"] = set(["30", "32", "34"])
stations["four"] = set(["32", "33"])
stations["five"] = set(["34", "35"])

Ключи — названия станций, а значения — сокращенные обозначения областей, входящих в зону охвата. Таким образом, в данном примере станция one вещает в субъектах с кодами 31, 32, 33(Белгородская, Брянская и Владимирская области). Все значения являются множествами. Хранение данных во множествах упрощает работу. Наконец, нам понадобится структура данных для хранения итогового набора станций:

final_stations = set()

Вычисление ответа

Теперь необходимо вычислить набор используемых станций. Правильных решений может быть несколько. Необходимо перебрать все станции и выбрать ту, которая обслуживает больше всего субъектов-областей, не входящих в текущее покрытие. Будем называть её best_station:

while states_needed:
  best_station = None
  states_covered = set()
  for station, states_for_station in stations.items():

Множество states_covered содержит все области, обслуживаемые этой станцией, которые ещё не входят в текущее покрытие. Помните, мы ищем станцию, которая будет обслуживать большинство ещё не охваченных областей. Цикл for перебирает все станции и находит среди них наилучшую. Рассмотрим тело цикла for:

for station, states_for_station in stations.items():
  covered = states_needed & states_for_station # Пересечение множеств
  if len(covered) > len(states_covered):
    best_station = station
    states_covered = covered

Про множества

С двумя множествами можно выполнить ряд операций:

• объединение множеств означает слияние элементов обоих множеств;
• под операцией пересечения множеств понимается поиск элементов, входящих в оба множества;
• под разностью множеств понимается исключение из одного множества элементов, присутствующих в другом множестве.

Основные особенности множеств:

• множества похожи на списки, но не содержат дубликатов;
• с множествами можно выполнять различные операции — объединение пересечение и разность.

Подробнее про множества

Допишем код

Множество covered содержит области, присутствующие как states_needed, так и в states_for_station. Таким образом, covered — множество областей, не входящих в покрытие, которые покрываются текущей станцией! Затем мы проверяем, покрывает ли эта станция больше областей, чем текущая станция best_station. Если условие выполняется, то станция сохраняется в best_station. Наконец, после завершения цикла best_station добавляется в итоговый список станции:

final_station.add(best_station)

Также необходимо обновить содержимое states_needed. Те области(субъекты), которые входят в зону покрытия станций, больше не нужны:

states_needed -= states_covered

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

# Для обозначения субъектов РФ используются коды
# Переданный массив преобразуется в множество
states_needed = set(["28", "29", "30", "31", "32", "33", "34", "35"]) 

stations = {}
stations["one"] = set(["31", "32", "33"])
stations["two"] = set(["29", "31", "28"])
stations["three"] = set(["30", "32", "34"])
stations["four"] = set(["32", "33"])
stations["five"] = set(["34", "35"])

final_stations = set()
while states_needed:
  best_station = None
  states_covered = set()
  for station, states_for_station in stations.items():
    covered = states_needed & states_for_station
    if len(covered) > len(states_covered) and station not in final_stations:
      best_station = station
      states_covered = covered
  if best_station is not None:
    states_needed -= states_covered
    final_stations.add(best_station)
    stations.pop(best_station)
    
print(final_stations)

Вместо станций 1,2,3,5 можно было выбрать станции 2,3,4, и 5. Ниже сравним время выполнения алгоритма:

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

В следующей статье речь пойдёт про динамическое программирование.

Попробуйте сами скопировать и запустить код в окне ниже с интерпретатором Python и повторите примеры из статьи чтобы самим увидеть и понять как всё это работает. Для этого в ячейке с кодом нажмите клавиши на клавиатуре Shift+Enter или запустите код через кнопку Run по значку ▶.