Вот решение в том случае, если вы ищете оптимальное сочетание ваших участников (всех) по вашим критериям:
Тогда нужно найти идеальное соответствие в графе участников.
Создайте график с n
вершинами, n
- количество участников. Мы можем обозначить u_p
вершину, соответствующую участнику p
.
Затем создайте взвешенные ребра следующим образом:
Для каждой пары участников p, q
(p! = Q) создайте ребро (u_p, u_q)
и сравните его с количеством интересов, общих для этих двух участников.
Затем запустите алгоритм идеального соответствия минимального веса на вашем графике, и работа завершена. Вы получите оптимальный результат (т. Е. Наилучший из возможных или один из наилучших возможных соответствий) за полиномиальное время.
Алгоритм идеального сопоставления минимального веса: задача строго эквивалентна алгоритму сопоставления максимального веса. Найдите ребро максимального веса (обозначим C
его вес). Затем замените вес w
каждого ребра на C-w
и запустите алгоритм согласования максимального веса на полученном графике.
Я бы посоветовал вам использовать Алгоритм цветения Эдмонда , чтобы найти идеальное соответствие на вашем графике. Во-первых, потому что это эффективно и хорошо документировано, во-вторых, потому что я считаю, что вы можете найти реализации в большинстве существующих языков, но также потому, что это действительно очень, очень красивый алгоритм (его не зря называют цветением).
Еще одна возможность: если вы уверены, что число участников будет небольшим (вы упомянули 8), вы также можете использовать алгоритм перебора, то есть проверить все возможные способы объединения участников.
Тогда алгоритм будет выглядеть так:
find_best_matching(participants, interests, pairs):
if all participants have been paired:
return sum(cost(p1, p2) for p1, p2 in pairs), pairs // cost(p1, p2) = number of interests in common
else:
p = some participant which is not paired yet
best_sum = + infinite
best_pairs = empty_set
for all participants q which have not been paired, q != p:
add (p, q) to pairs
current_sum, current_pairs = find_best_matching(participants, interests, pairs)
if current_sum < best_sum:
best_sum = current_sum
best_pairs = current_pairs
remove (p, q) from pairs
return best_sum, best_pairs
Сначала позвоните по номеру find_best_matching(participants, interests, empty_set_of_pairs)
, чтобы получить наилучший способ подбора участников.