Максимальное количество «команд»

Question

У меня есть определение для группы людей. Мне нужно найти наибольшее количество команд, которые я могу получить на основе списка людей (и их соответствующих слотов), учитывая, что, как только человек «используется» для слота, их нельзя использовать снова.

Упрощенный пример:

**Team Requirements** 
Slot A: 2 People 
Slot B: 1 Person 
Slot C: 1 Person 

**People And Which Slots Are Applicable** 
Person 1: A 
Person 2: A,C 
Person 3: A,B 
Person 4: B 
Person 5: A,B 
Person 6: C 
Person 7: C 
Person 8: A 

Возможный ответ

Team 1 
A: P1, P8 
B: P4 
C: P6 

Team 2 
A: P2, P3 
B: P5 
C: P7 

Для моей реальной проблемы, у меня есть несколько слотов (1-10 на группу) и 1-1000 людей, которые могут иметь до до 20 слотов каждый.

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

Answer 1

Это можно решить, найдя Maximum Cardinality Bipartite Matching в каждой из серии графиков в O (n^2,5 log n) времени в целом.

Для этого сначала конвертируйте каждый слот типа в набор соответствующего количества отдельных слотов, так что мы завершаем слотами A1, A2, B, C. Окончательное решение назначит человека (например, Person 3 до слота A2 в Team 1), но мы можем просто забыть «2» (а также упорядочить команды, которые также являются чисто искусственными).

Начните с расчета оптимистической оценки k числа команд: RoundDown (n/4) будет делать, поскольку каждая команда использует 4 человека, поэтому у нас не может быть больше команд, чем это. Теперь сделайте 4k вершин в одной части двудольного графа, т. Е. Вершины для каждого из 4 слотов в каждой из k потенциальных команд: A1_1, A2_1, B_1, C_1, A1_2, A2_2, B_2, C_2, .. ., A1_k, A2_k, B_k, C_k. В другой части двудольного графа сделайте вершину для каждого человека. Наконец, подключите каждую человеческую вершину со всеми вершинами слота, которые им разрешено заполнить: Так, например, если человек x может занять слоты A или C, они должны быть соединены краем с каждым слотом, начинающимся с «A» или «C» (это будет 6 ребер для примера с 8 людьми).

Затем устраните проблему с MCBM на этом графике, например. в O (n^2,5), используя Hopcroft-Karp algorithm. Результатом будет подмножество ребер, которое можно интерпретировать как назначение каждому человеку не более одного слота в команде и заполнение каждого слота в команде не более чем одним человеком. Если это приведет к заполнению каждого слота, ура! У нас есть максимально возможное количество команд. В противном случае, если есть некоторые слоты для команды, оставленные незаполненными любым человеком, уменьшите количество команд и повторите попытку. (Вы можете сократить количество команд на 1 каждый раз, что приводит к линейному числу проблем с MCBM, которые необходимо решить, но вы можете сэкономить время путем двоичного поиска. Это означает, что, начиная с сокращения вдвое числа команд и после чего уменьшалось или увеличивалось количество команд на половину предыдущей суммы, уменьшая, когда какая-то команда имеет незаполненную позицию и увеличивается, когда ее нет, до конвергенции.)