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

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

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

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

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

Ответ 1

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

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

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

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

Оптимальное решение для k-partite-сопоставления NP-сложно найти:

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

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

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.

Ответ 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)]

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

//Чтобы гарантировать, что никто не будет помещен в две группы

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

Ответ 3

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

Ответ 4

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

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

Ответ 5

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

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

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