Page 190 - Bkhargava_-_Grokaem_algoritmy

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

МНОJЕ.СТ&О 1 МНОJЕ.СТ&О б MHOJE.CT&O 500

... ц м. д . ... ... ц м. д . . "

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

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

k'ОЛИЧЕ.СТ&О ~ E.OБXOJI.llMOE.
спнuм~ 6PE.MJI
5 З.2с
19) 19S2.4c
32 1 3 . 6 ro.a.~
1Ф~ 4')(1 о~ ro.a.~

Приближенные алгоритмы

На помощь приходят жадные алгоритмы! Вот как выглядит жадный алго­
ритм, который выдает результат, достаточно близкий к оптимуму:

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

www.trk.kg