Page 191 - Bkhargava_-_Grokaem_algoritmy

190 Глава 8. Жадные алгоритмы

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

1:1 близости полученного решения к оптимальному.

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

А теперь посмотрим, как эта задача выглядит в программном коде.

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

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

Сначала составьте список штатов:

states_needed • set( [ "mt", "wa", "or", "id", "nv", "ut",
"са", "az"] ) <С···"· ·· Переданный массив преобразуется в множество

В этой реализации я использовал множество. Эта структура данных похо­
жа на список, но каждый элемент может встречаться в множестве не более
одного раза. Множества не содержат дубликатов. Предположим, имеется
следующий список:
>>> arr = [1, 2, 2, 3, 3, 3]

Этот список преобразуется в множество:

»> set(arr)
set([l, 2, 3])

Значения 1, 2 и 3 встречаются в списке по одному разу.

ЛРЕОБРА- ~ (1,2,1)
[1,2,2,3,3,)] _. .3УЕТU 60
МНОЯ.ЕСТ60
МНОЯ.ЕС.Т60

www.trk.kg