|
РАДИО
СТАНЦИЯ
|
ДОСТУПНА 6 ШТАТАХ
|
Ко vie
|
IDjN'/jUT
|
KTvOO
|
vJa,Id,kt
|
Ктнреб
|
OB.,NV,cA
|
KFovjR
|
Ыч,о T
|
KFiVE
|
CA,AZ
|
... и ИЛ. д....
Каждая станция покрывает определенный набор штатов, эти наборы перекрываются.
Как найти минимальный набор станций, который бы покрывал все 50 штатов? Вроде бы простая задача, верно? Оказывается, она чрезвычайно сложна. Вот как это делается:
Составить список всех возможных подмножеств станций — гак называемое степенное множество. В нем содержатся 2 лп возможных подмножеств.
Из этого списка выбирается множество с наименьшим набором станций, покрывающих все 50 штатов.
МНОЖЕСТВО 1 ...
|
множество а ,
|
МНОЖЕСТВО 500
|
/ч\
кгй<^
|
(Л £ \
|
Г%
%\
|
|
с \
4< У
|
А О/
|
... и м. д. ... ... м ил. д. ... ... и си. д. ...
Проблема в том, что вычисление всех возможных подмножеств станций займет слишком много времени. Для п станций оно потребует времени 0(2Лп). Если станций немного, скажем от 5 до 10, — это допустимо. Но подумайте, что произойдет во всех рассмотренных примерах при большом количестве элементов. Предположим, вы можете вычислять по 10 подмножеств в секунду.
Не существует алгоритма, который будет вычислять подмножества с приемлемой скоростью! Что же делать?
КОЛИЧЕСТВО
|
НЕОБХОЛИМОЕ
|
СТАНЦИЙ
|
ВРЕМЯ
|
5
|
3.2с
|
1$6
|
102.4 с
|
32
|
13.6 ГОЛА
|
1ФР
|
4-xlo1 ГОЛА
|
Приближенные алгоритмы
На помощь приходят жадные алгоритмы! Вот как выглядит жадный алгоритм, который выдает результат, достаточно близкий к оптимуму:
Выбрать станцию, покрывающую наибольшее количество штатов, еще не входящих в покрытие. Если станция будет покрывать некоторые штаты, уже входящие в покрытие, это нормально.
Повторять, пока остаются штаты, не входящие в покрытие.
Этот алгоритм является приближенным. Когда вычисление точного решения занимает слишком много времени, применяется приближенный алгоритм. Эффективность приближенного алгоритма оценивается по:
быстроте;
близости полученного решения к оптимальному.
Жадные алгоритмы хороши не только тем, что они обычно легко формулируются, но и тем, что простота обычно оборачивается быстротой выполнения. В данном случае жадный алгоритм выполняется за время 0(иЛ2), где п — количество радиостанций.
А теперь посмотрим, как эта задача выглядит в программном коде.
Подготовительный код
В этом примере для простоты будет использоваться небольшое подмножество штатов и станций.
Сначала составьте список штатов:
states_needed = set(["mt", "wa", "or", "id", "nv", "ut",
"ca", "az"]) < Переданный массив преобразуется в множество
В этой реализации я использовал множество. Эта структура данных похожа на список, но каждый элемент может встречаться в множестве не более одного раза. Множества не содержат дубликатов. Предположим, имеется следующий список:
>>> агг = [1, 2, 2, з, з, з]
Этот список преобразуется в множество:
>>> set(arr) set([l, 2, 3])
Значения 1, 2 и 3 встречаются в списке по одному разу.
П
МН0ЯЕСТ60
РЕОБРЛ-
— Г ЗУЕТСЯ 60 -*•
МН0*ЕСТ60
Также понадобится список станций, из которого будет выбираться покрытие. Я решил воспользоваться хешем:
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"])
Ключи — названия станций, а значения — сокращенные обозначения штатов, входящих в зону охвата. Таким образом, в данном примере станция копе вещает в штатах Айдахо (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 добавляется в итоговый список станций:
Do'stlaringiz bilan baham: |
