Книга является наиболее полным руководством по разработке эффективных ал

Часть I. Практическая разработка алгоритмов 
жен алгоритм, чтобы составить наименьший набор билетов, которые нужно купить, 
чтобы гарантировать выигрыш, по крайней мере, одного приза. 
— При условии, что ясновидец не ошибается? 
— Да, при условии, что ясновидец не ошибается. Нам нужна программа, которая рас-
печатывает список всех возможных комбинаций выигрышных номеров билетов, кото-
рые он должен купить с минимальными затратами. Можете ли вы помочь нам с реше-
нием этой задачи? 
Может быть, они и в самом деле были ясновидцами, т. к. они обратились как раз туда, 
куда надо. Определение наилучшего подмножества номеров билетов попадает в разряд 
комбинаторных задач. А точнее, это какой-то тип задачи о покрытии множества, в ко-
торой каждый покупаемый билет "покрывает" некоторые из возможных четырехэле-
ментных подмножеств увиденного ясновидцем пятнадцатиэлементного множества. 
Определение наименьшего набора билетов для покрытия всех возможностей представ-
ляет собой особый экземпляр NP-полной задачи
о 
покрытии множества
(рассматри-
вается в 
разделе 18.1
) и считается вычислительно неразрешимой. 
Данная задача действительно была особым экземпляром задачи о покрытии множест-
ва, полностью определяемая всего лишь четырьмя числами: размером 
n
возможного 
множества 
S
(
n
≈ 15), количеством номеров 
k
на каждом билете (
k
≈ 6), количеством 
обещаемых ясновидцем выигрышных номеров 
j
из множества 
S 
(
j
= 4) и, наконец, ко-
личеством совпадающих номеров 
l
, необходимых, чтобы выиграть приз (
l
= 3). На 
рис. 1.10 показано покрытие экземпляра меньшего размера, где 
n
= 5, 
j
= 
k = 
3, 
l
= 2. 
Рис. 1.10. 
Покрытие всех пар множества {1, 2, 3, 4, 5}
номерами билетов {1, 2, 3}, {1, 4, 5}, {2, 4, 5}, {3, 4, 5} 
— Хотя найти точный минимальный набор билетов с помощью эвристических методов 
будет трудно, я должен буду дать вам покрывающий набор номеров, достаточно близ-
кий к самому дешевому, — ответил я ему. — Вам этого будет достаточно? 
— При условии, что ваша программа создает лучший набор номеров, чем программа 
моего конкурента, это будет то, что надо. Его система не всегда гарантирует выигрыш. 
Очень признателен за вашу помощь, профессор Скиена. 

---