Задача: имеется набор подмножеств некоторого множества (списков снарядов, на которых выступает каждый атлет). Требуется выяснить попарную степень сходства снарядов, базируясь на предположении, что атлетов ставят на снаряды, как можно лучше подходящие к их способностям.
Алгоритм: Первоначально все снаряды неразличимы (связаны пружинами длиной 0).
Для каждого атлета каждая пара снарядов (Х, Y), где X принадлежит к подмножеству снарядов, на которых он выступает, а Y - к подмножеству, на которых он не выступает, увеличивает длину пружины между X и Y на некоторую величину M.
M определяется так: число пар (X, Y) равно K*(N-K), где N - общее число снарядов, а K - число снарядов, на которых выступает атлет. Если какой-то из множетелей равен нулю (атлет выступает на всех снарядах или вообще не выступает), то мы его игнорируем, иначе M = L/(K*(N-K)) для данного атлета, где L я выбрал таким, чтобы все числа получались целые, а именно 360.
В результате получаем:
floor -- vault [len=844]; paral -- hibar [len=1014]; floor -- hibar [len=1041]; horse -- paral [len=1063]; floor -- paral [len=1094]; vault -- hibar [len=1099]; vault -- paral [len=1112]; rings -- paral [len=1136]; rings -- hibar [len=1158]; rings -- vault [len=1176]; floor -- horse [len=1185]; horse -- hibar [len=1225]; horse -- vault [len=1243]; floor -- rings [len=1338]; horse -- rings [len=1387];
Сумма длин у rings - 6195, у [pommel]horse - 6103. Самое короткое ребро, идущее от rings - 1136, идущее от horse - 1063. Но если отбросить (что интересно, самое длинное) ребро, соединяющее horse и rings, то среди следующих четырех самых длинных будет три, идущих от horse, и только одно - от rings. Какой критерий считать бо́льшим "отшибом" с точки зрения расположения на графе - дело вкуса.
Вот что выходит, если нормализовать длину для получения изображения разумного размера и скормить это в GraphViz (с русскими обозначениями):
Оказывается, расположение узлов результирующего графа очень чувствительно к именам узлов и масштабу - иногда выпуклая оболочка выходит не шестиугольником, а пятиугольником с hibar в середине, хотя минимум суммы длин у floor (5502), а не у hibar (5537). Вчера в какой-то момент мне показалось, что horse дальше от остальных узлов, чем rings; посмотрев в отсортированный список и увидев много horse в его конце, я решил, что так оно и есть, и так и сформулировал.
Ну хотя бы в том, что два самых близких снаряда - это floor и vault, а третий к ним - hibar, нет сомнений.