Page 189 - Bkhargava_-_Grokaem_algoritmy

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

РАДИО- .n.ОС.ТУПНА
с.пнцмя 6 шппх
KotJE lt>,IN,ul

K1'wo vJA, \О,~1

k'ТH~I:. ОР., N'l,ct>.
Kfo\IR N'V,V1

Kf'tVE (.A,AZ

•.. /А м. д . ...

Каждая станция покрывает определенный набор штатов, эти наборы пере­

крываются.

Как найти минимальный набор станций, который бы покрывал все 50 шта­
тов? Вроде бы простая задача, верно? Оказывается, она чрезвычайно слож­
на. Вот как это делается:

1. Составить список всех возможных подмножеств станций - так на­
зываемое степен.н.ое множество. В нем содержатся 2 лп возможных
подмножеств.
2. Из этого списка выбирается множество с наименьшим набором станций,
покрывающих все 50 штатов.

www.trk.kg