Page 204 - Bkhargava_-_Grokaem_algoritmy

NР-полные задачи 203

иrРОК КАЧЕСТIН

МЭТТ ФОРТЕ
WF. / МРОШО ИrРАЕТ
БРЕНдАН МАРШ А ЛЛ ПОД ДАВЛЕНИЕМ

QB / '1-ОРОШО ИrРА ЕТ
А. А РОН РОдl.ЕРС
ПОД ДА ВЛЕНИЕМ

Джон хочет подобрать команду, которая обладает полным набором качеств,
но размер команды ограничен . «Минутку, - осознает Джон, - но ведь это
задача покрытия множества!»

Для создания команды Джон может воспользоваться тем же приближенным
алгоритмом:

1. Найти игрока с большинством качеств, которые еще не были реализо­
ваны.
2. Повторять до тех пор, пока не будут реализованы все качества (или пока
не кончатся свободные места в команде).
NР-полные задачи встречаются очень часто. И было бы полезно, если бы
вы могли понять, что решаемая задача является NР-полной. В этот момент
можно прекратить поиски идеального решения и перейти к решению с при ­
менением приближенного алгоритма. Но определить, является ли ваша
задача NР-полной, непросто. Обычно различия между легко решаемыми
и NР-полными задачами весьма незначительны. Например, в предыдущих

www.trk.kg