Page 203 - Bkhargava_-_Grokaem_algoritmy

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

Короткое объяснение NР-полноты: некоторые задачи прославились слож­
ностью своего решения. Задача о коммивояжере и задача о покрытии
множества - два классических примера. Многие эксперты считают, что
написать быстрый алгоритм для решения таких задач невозможно.

Как определить, что задача является NР-полной?

Джон подбирает игроков для своей команды по
американскому футболу. У него есть список нуж­

ных качеств : хорошо играет в нападении, хорошо
играет в защите, хорошо играет под дождем, хо­
рошо играет под давлением и т. д. Также имеется
список игроков, в котором каждый игрок обладает
определенными качествами .

www.trk.kg