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

Question

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

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

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

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

Answer 1

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

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

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

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

Оптимальное решение к-дольных соответствие является NP-трудной найти:

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

Смотрите эту бумагу для неоптимального решения задачи согласования к-дольных:

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) готов работать с Ь (данный член B), и 0 в противном случае

M2 = |A| x |C| матрица, где M2(a,c) = 1, если (данный член A) готов работать с с (с учетом члена с), и 0 в противном случае

M2 = |B| x |C| матрица, WH прежде чем

M3(b,c) = 1 если б (данный член B) готов работать с с (с учетом члена С), и 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

Для всех значений Ь: Sum[(all i, k) X(i, b, k)] <= 1

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

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

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

Answer 4

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

Answer 5

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

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

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