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

Просыпается Гоша, а уже утро.

Гоша: Блин, уже суббота?

Рыба из аквариума: Да, а ты что думал? Мы вот есть хотим, покорми нас!

Гоша: Так, пора на свежий воздух, наверное.

И пошёл на улицу. Около офиса он встретил Аллу и Тимофея.

Гоша: Ой, привет, я тут вчера с задачей засиделся и заснул, представляете?

Алла: Кстати, про задачи. Мне нужна помощь, есть время?

Гоша: Ну... В общем, есть, наверное.

Алла: Планируется открыть новую радиопрограмму. Нужно, чтобы её слушали во всех населённых пунктах из списка. Требуется определить, на каких радиостанциях передача должна транслироваться. За каждую станцию нужно платить, поэтому желательно свести их количество к минимуму.

Есть список станций, каждая из которых транслируется в определённых населённых пунктах:

Некоторые станции транслируются в одних и тех же городах.

Гоша: Нужно просмотреть возможные наборы станций и выбрать те, которые покрывают все города. Подойдёт тот набор, в котором меньше всего станций

Тимофей: Кажется, это не очень хорошее решение.

Тимофей: Потребуется рассмотреть 2ⁿ- 1 вариантов подмножеств. Станций всего n. Подмножеств из n элементов может быть 2ⁿ. Потому что каждый элемент множества может входить в подмножество, а может не входить. По правилу произведения получаем 2ⁿ.

Гоша: По какому такому правилу?

Тимофей: По правилу произведения! У тебя разве не было комбинаторики?

Гоша: Ну как же, была, но тогда ещё Dota вышла... В общем, не помню я никакого правила произведения!

Тимофей: Смотри, пусть нужно выполнить n действий. Первое может быть выполнено n₁ способами, второе — n₂ и так до n-го. Тогда общее количество способов будет n₁ × n₂ × n₃ × ...

Гоша: А, ну да, было что-то такое!

Тимофей: В нашем случае каждое действие — включение или невключение станции в множество. То есть для каждой станции есть два варианта. Получается, что всего вариантов 2 × 2 × 2 × ... × 2 = 2ⁿ. Но один из наборов соответствует случаю, когда никакая станция не включена. Он нам не подходит, так как передача точно нигде не будет транслироваться. То есть ответ 2ⁿ - 1.

Предложенный алгоритм неэффективный. Если n небольшое, то его ещё можно использовать. При больших n он будет работать очень долго. А насколько я знаю, со временем предполагается охват всё большего количества городов.

Гоша: И что же делать? И вообще, что это за странные названия населённых пунктов у вас в списке? Что за Удотинск (UT), Тупоград (TG), Лажапетровск (LP)? Где вы это взяли?

Алла: В смысле где? Удотинск — столица Трешландии.

Гоша: Чего столица?

Тимофей: Трешландии, а ты, по-твоему, где?

Гоша: До недавнего времени думал, что в России.

Алла: Так, перестань. Мы понимаем, что никому сейчас здесь не хочется находиться, но ничего не поделаешь. И вообще, нужно думать над решением задачи, а то Кондратий нам всем головы оторвёт!

Гоша: Какой Кондратий?

Тимофей: Ну ты чего, Кондратий — король Трешландии.

Тимофей: И, кстати, у меня, кажется, появилась идея решения. Смотрите! Можно применить жадный алгоритм!

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

Это приближённый алгоритм. Но он работает довольно быстро. Кондратий приказал, чтобы алгоритм работал не дольше, чем за O(n²).

Гоша: Чего? Приказал?

Алла: Ну да, чего ты удивляешься, у него часто бывают задачи со строгими и порой очень странными ограничениями!

Тимофей: Так, хватит болтать! Вообще эффективность приближённых алгоритмов оценивается по их быстроте и близости результата к точному решению. В данном случае приближённый алгоритм выполнится за O(n²), где n — количество радиостанций. При этом решение будет близко к оптимальному. Напишем код, у нас осталось совсем немного времени!

Составим список городов:

Скопировать кодPYTHON
states_needed = set (["mt", "wa", "or", "tg", "nv", "ut", "lp", "az"])

Переданный массив преобразуется в множество.

Также нужно хранить информацию о том, какие станции какие города покрывают.

Для этого удобно использовать хеш-таблицу. Подробно про то, как устроена эта структура данных, вы узнаете позднее в курсе.

Скопировать кодPYTHON
stations = {}
stations["kone"] = set (["tg", "nv", "ut"])
stations["ktwo"] = set (["wa", "tg", "mt"])
stations["kthree"] = set (["or", "nv", "lp"])
stations["kfour"] = set (["nv", "ut"])
stations["kfive"] = set (["lp", "az"])

Ещё понадобится структура данных, для хранения итогового набора станций:

Скопировать кодPYTHON
final_stations = set()

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

Скопировать кодPYTHON
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):
        best_station = station
        states_covered = covered

Если условие выполняется, добавим best_station во множество final stations, и уберём города, которые она покрывает, из множества городов states_needed:

Скопировать кодPYTHON
states_needed -= states_covered
final_stations.add(best_station)

Сравним время выполнения точного и приближённого алгоритмов:

Алла: Да уж, пожалуй, выберем второй!