Алгоритм сопоставления предпочтительных партнеров по группам из трех
https://stackoverflow.com/questions/294660
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Какой хороший алгоритм для решения этой проблемы?
У меня есть три группы людей - группа A, группа B и группа C. В каждой группе одинаковое количество людей. У каждого из них есть список людей в других группах, с которыми они готовы работать. Я хочу сгруппировать всех этих людей в группы по 3 человека (одна из A, одна из B и одна из C) так, чтобы все в группе хотели работать с другими людьми в своей группе.
Как я могу быстро найти эти группы? Если нет никакого способа сделать всех счастливыми, то алгоритм должен сначала сделать так, чтобы во многих группах было по три человека, которые хотят работать друг с другом, а затем сделать так, чтобы как можно больше людей в других группах были счастливы.
И последнее замечание: люди соглашаются с тем, с кем они хотят работать (если человек x хочет работать с человеком y, то y также хочет работать с x). Если бы вы могли также оценить время выполнения вашего алгоритма, это было бы здорово!
Решение
Это похоже на проблему стабильного брака, но с тремя партиями вместо двух.
Посмотрите на эффективные решения для прежней проблемы (двухстороннее сопоставление графов) и адаптируйте их к вашим потребностям.
http://en.wikipedia.org/wiki/Stable_marriage_problem
Одна адаптация может состоять в том, чтобы сначала создать рабочие пары только из групп A и B. Затем эти пары должны быть в паре с рабочим из группы C. Пусть пары предпочитают только тех работников, с которыми согласны оба члена пары (учитывая их списки). Обратите внимание, что это даст только локальный оптимум.
Оптимальное решение для k-раздельного сопоставления трудно найти:
http://www.math.tau.ac .il / ~ Сафра / PapersAndTalks / k-DM.ps
В этой статье приведено неоптимальное решение проблемы k-разбиения:
Я уверен, что вы можете сами найти других в Google, если знаете условия поиска. Я не знаю, существует ли эффективный алгоритм, дающий оптимальное решение для k = 3.
Другие советы
Это отличается от расширения проблемы стабильного брака, поскольку, как я понимаю вопрос ОП, у людей в каждой группе нет упорядоченного списка тех, с кем они хотят работать, от большинства к минимуму; это бинарные отношения (хочет / не хочет).
Это можно сформулировать как задачу целочисленного программирования, которая может быть решена довольно быстро. Я даю математическую формулировку проблемы ниже; вы можете использовать такой пакет, как glpk или AMPL / CPLEX для обработки данных.
Определите следующие матрицы:
M1 = |A| x |B| матрица, где
M1(a,b) = 1 если a (данный член A) готов работать с b (данный член B), и 0 в противном случае
M2 = |A| x |C| матрица, где M2(a,c) = 1, если a (данный член A) готов работать с c (данный член C), и 0 в противном случае
M2 = |B| x |C| матрица, где
M3(b,c) = 1 если b (данный член B) готов работать с c (данный член C), и 0 в противном случае
Теперь определите новую матрицу, которую мы будем использовать для нашей максимизации:
X = |A| x |B| x |C| матрица, где
X(a,b,c) = 1 если мы заставим a, b и c работать вместе.
Теперь определим нашу целевую функцию:
// Максимизируем количество групп
увеличить Sum[(all a, all b, all c) X(a,b,c)]
при условии соблюдения следующих ограничений:
// Чтобы никто не попал в две группы
Для всех значений a: Sum[(all j, k) X(a, j, k)] <= 1
Для всех значений b: Sum[(all i, k) X(i, b, k)] <= 1
Для всех значений c: Sum[(all i, j) X(i, j, c)] <= 1
// Чтобы убедиться, что все группы состоят из совместимых людей
Для всех a, b, c: X(a,b,c) <= M1(a,b)/3 + M2(a,c)/3 + M3(b,c)/3
Просто краткое замечание по этой проблеме. Во-первых, это не пример проблемы стабильного брака и, фактически, ее расширение (то есть проблема трехмерного стабильного сопоставления). Несмотря на это, это проблема 3D-сопоставления, которая известна как NP-сложная (см. Garey and Johnson). Для разумного решения такой проблемы вам, вероятно, потребуется использовать некоторую форму ограничения, целочисленного или линейного программирования (существуют другие методы). Что-то, что может быть полезно, это новый Microsoft Solver Foundation, так что зацените его.
Начнем с того, что вы можете исключить любые факты, в которых две стороны имеют отдельные списки тех, с кем они будут работать в третьей группе. Затем начните перебор, поиск в глубину, всегда выбирая от наименее популярного до самого популярного.
В качестве альтернативы, эквивалентной приведенному выше исключению, сформируйте список всех возможных трио и вместо этого работайте.
Я столкнулся с подобной проблемой и только что написал сценарий, который грубо заставляет ее ... http: // grouper. owoga.com/
Мои первые мысли были: для большой группы, которая была слишком велика для грубой силы, какой-то генетический алгоритм? Сделайте N случайных перестановок M раз. Оценка каждой новой договоренности с помощью некоторой функции «счастья». Бери лучших, разводи, повторяй.
Для небольших групп я в итоге получал лучшие результаты, перебирая несколько групп, находя «лучший» обмен (тот, который принес наибольший общий выигрыш «счастья»), делая это, затем повторяя.
