Разделите n человек на m групп по k раз с минимальным перекрытием

Question

Допустим, у меня есть

• от 60 до 100 человек, которых я хочу разделить на
• от 3 до 5 групп
• от 10 до 25 человекдля каждой группы, и я хочу сделать это
• от 3 до 5 раз

таким образом, чтобы каждый встречал как можно больше людей с минимальным количеством повторений.

Я пытался провести какое-то собственное исследование, но не смог найти ничего похожего на то, что я искал.

Если вам нужна дополнительная информация, просто дайте мне знать.

Заранее спасибо

Answer 1

Это можно сформулировать как целочисленную задачу программирования.

Определить двоичную переменную A[i,g,t] = 1, если персона i in N принадлежит группе g in G в момент времени t in T и 0 в противном случае.Тогда M[i,j] = sum(A[i,g,t] * A[j,g,t] for g in G, t in T) равно 1, если i и j встретятся.

Скажем, вы хотите максимизировать количество пар людей, которые встречаются хотя бы один раз.Затем ваша цель становится sum(M[i,j] for i, j in N).

Вы можете выразить свои ограничения линейно:

1. Размеры группы ограничены: forall g in G, forall t in T, sum(A[i,g,t] for i in N) <= quota[g,t].
2. Каждому человеку назначаетсяровно одной группе в каждый период: forall i, forall t, sum(A[i,g,t] for g in G) = 1.

Существует несколько решателей с открытым исходным кодом, которые должны хорошо работать в предложенном вами масштабе.

Answer 2

Это близкий вариант проблемы социального игрока в гольф.Есть алгоритм из-за Триски и Муслиу, который работает хорошо;см. https://github.com/FelixHenninger/socialgolfer.js/tree/master для реализации.