Паросочетание

[maxfisher]

Есть N<30000 пользователей, у каждого пользователя есть K<8 интересов. Нужно разбить пользователей по парам за интересами, алгоритм должен быть быстрым и эффективным.

Другая подзадача: нужно для каждого пользователя предложить список более подходящих пользователей для него за интересами.

Как это решать?

[MBo]

Полагаю, подойдет алгоритм Эдмондса (не Эдмондса-Карпа!)

[maxfisher]

Объясните пожалуйста поподробнее как мне использовать этот алгоритм?

[MBo]

Пользователи - узлы
Ребрами соединены пользователи с общими интересами
Указанный алгоритм найдет паросочетание - максимальное по количеству подмножество ребер, разбивающее пользователей на пары (и не пересекающееся по узлам). Идеальный случай - все пользователи разбиты на пары (реберное покрытие)

[maxfisher]

этот алгоритм подойдет, но мне в принципе не нужно максимальное паросочетание. Меня устроит достаточно неплохое паросочетание, но алгоритм должен работать очень быстро.

[MBo]

А сколько интересов всего?
Возможно, какой-либо вид кластеризации подойдет для первичного разбиения на небольшие группы.

[maxfisher]

Сейчас есть около 50 стандартных интересов, но пользователи могут создавать свои собственные.