А.М. Андреев, Г.П. Можаров
6
Задача оптимального окончательного определения заключается в
том, чтобы найти подмножество
p
с наибольшим весом
p
w p
w
, где
p n
. Это означает, что необходимо отобрать
n
подмножеств
, пересечения которых образуют последователь-
ность
1
, ...,
n
. В результате окончательного определения каждый
элемент
j
должен быть закреплен только за одним из пересекаю-
щихся подмножеств
j
и исключен из других. При этом сумма весов
подмножеств, за которыми закрепляются элементы
1
, ...,
n
,
должна быть наибольшей.
Для оптимального определения разбиения необходимо: во-
первых, выделить последовательность
1
, ...,
n
, все элементы ко-
торой различны; во-вторых, построить семейство
; в-третьих, из
множеств
j
S
семейства
отобрать
n
разных элементов, сумма ве-
сов которых будет наибольшей [7].
На первом этапе окончательного определения семейства выполним
следующие операции. Найдем пересечение
M
множеств семейства
'
:
1
M
M
P
,
1
1
...
M
M
.
Далее найдем все пересечения
1
M
множеств из
'
, число ко-
торых не превышает числа сочетаний
1
,
1
M i
M
C
M M
:
1
1
,...,
M
,...,
1
,
1
M
M M
.
Построим разбиение вида
1
1
1
1
,
1
1
1
, ...,
M M M
M
M M
M
P
.
Рекуррентно продолжим построение разбиений, отыскивая на шаге
3
i
все пересечения
1
M i
множеств
'
.
Их не более
1
,
1
M i
M
C
M M i
, т. е.
1
1
1
,
1
,...,
M i
M i
M M i
. Рассмотрим неко-
торое пересечение
1
M i
s
, где
1
,
1
s M M i
. Пусть
2
s M i
объединение всех пересечений множеств
'
, найденных на (
i
1)-м
шаге и участвующих в образовании пересечения
1
M i
s
на шаге
3, ...,
1
i
M
. Выполним следующее разбиение:
1
1
1
1
1
1
2
2
,
1
1
2
, ...,
, ...,
.
M i
M i
M i
M i
M i
s
s M i
M M i
M i
M i
P
