Алгоритм сопоставления предпочтительных партнеров по группам из трех

Question

Какой хороший алгоритм для решения этой проблемы?

У меня есть три группы людей - группа A, группа B и группа C. В каждой группе одинаковое количество людей. У каждого из них есть список людей в других группах, с которыми они готовы работать. Я хочу сгруппировать всех этих людей в группы по 3 человека (одна из A, одна из B и одна из C) так, чтобы все в группе хотели работать с другими людьми в своей группе.

Как я могу быстро найти эти группы? Если нет никакого способа сделать всех счастливыми, то алгоритм должен сначала сделать так, чтобы во многих группах было по три человека, которые хотят работать друг с другом, а затем осчастливить столько же людей в других группах.

И последнее замечание: люди соглашаются с тем, с кем они хотят работать (если человек x хочет работать с человеком y, то y также хочет работать с x). Если бы вы могли также дать оценку времени выполнения вашего алгоритма, это было бы здорово!

Answer 1

Это похоже на проблему стабильного брака, но с тремя партиями вместо двух.

Посмотрите на эффективные решения для прежней проблемы (двухстороннее сопоставление графов) и адаптируйте их к вашим потребностям.

http://en.wikipedia.org/wiki/Stable_marriage_problem

Одна адаптация может состоять в том, чтобы сначала создавать рабочие пары только из групп A и B. Затем эти пары должны быть в паре с рабочим из группы C. Пусть пары предпочитают только тех работников, с которыми согласны оба члена пары (учитывая их списки). Обратите внимание, что это даст только локальный оптимум.

Оптимальное решение для k-раздельного сопоставления трудно найти:

http://www.math.tau.ac.il/~safra/PapersAndTalks/k-DM.ps

См. Эту статью для неоптимального решения проблемы k-разбиения:

http://books.google.com/books?id=wqs31L1MF4IC&pg=PA309&lpg=PA309&dq=k-partite+matching&source=bl&ots=kgBuvi7ym_&sig=j3Y-nyo51y8qp0-HwToyUlkao4A&hl=de&sa=X&oi=book_result&resnum=1&ct=result

Я уверен, что вы можете сами найти других в Google, если вы знаете условия для поиска. Я не знаю, существует ли эффективный алгоритм, дающий оптимальное решение для k = 3.

Answer 2

Это отличается от расширения проблемы стабильного брака, поскольку, как я понимаю вопрос ОП, у людей в каждой группе нет упорядоченного списка тех, с кем они хотят работать, от большинства к минимуму; это бинарные отношения (хочет / не хочет).

Это можно сформулировать как задачу целочисленного программирования, которая может быть решена довольно быстро. Я даю математическую формулировку проблемы ниже; для обработки данных вы можете использовать такой пакет, как 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)]

с учетом следующих ограничений:

// Чтобы никто не попал в две группы

Для всех значений: 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

// Для обеспечения того, чтобы все группы состояли из совместимых лиц

Для всех а, б, в: X(a,b,c) <= M1(a,b)/3 + M2(a,c)/3 + M3(b,c)/3

Answer 3

Просто краткое примечание к этой проблеме. Во-первых, это не пример проблемы стабильного брака и, фактически, ее расширение (то есть проблема трехмерного стабильного сопоставления). Несмотря на это, это проблема 3D-сопоставления, которая известна как NP-сложная (см. Garey and Johnson). Для разумного решения такой проблемы вам, вероятно, потребуется использовать некоторую форму ограничения, целочисленного или линейного программирования (существуют другие методы). Что-то, что может быть полезно, - это новый Microsoft Solver Foundation, так что зацените его.

Answer 4

Я столкнулся с подобной проблемой и только что написал сценарий, который грубо заставляет ее ... http://grouper.owoga.com/

Мои первоначальные мысли были таковы: для большой группы, которая была слишком велика для грубой силы, какой-то генетический алгоритм? Сделайте N случайных перестановок M раз. Оценка каждой новой договоренности с помощью некоторой функции «счастья». Бери лучших, разводи, повторяй.

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

Answer 5

Начнем с того, что вы можете исключить любые факты, в которых две стороны имеют отдельные списки тех, с кем они будут работать в третьей группе. Затем начните перебор, сначала ищите глубину, всегда выбирая от наименее популярного до самого популярного.

В качестве альтернативы, эквивалентной вышеупомянутому исключению, сформируйте список всех возможных трио и вместо этого работайте.