Алгоритм для соответствия предпочтенным партнерам в группы трех
Оказалось, что это связано с размером файла. Я оставлю этот вопрос и отвечу, если кому-то еще это понадобится.
.pdf, который я использовал, составлял 2,8 МБ, но это не удалось, я использовал гораздо меньший файл ~ 125 КБ, и это работало нормально.
4 ответа
Это похоже на стабильную проблему соединения, но с 3 сторонами вместо два.
Взгляните на эффективные решения для прежней проблемы (биграф, соответствующий), и адаптируйте их к своим потребностям.
http://en.wikipedia.org/wiki/Stable_marriage_problem
Одна адаптация могла быть для первого создания рабочих пар из групп A и B только. Затем эти пары должны быть соединены с рабочим от группы C каждый. Позвольте парам только предпочесть рабочих, о которых оба члена пары договариваются (учитывая их списки). Обратите внимание, что это только даст локальный оптимум.
Оптимальное решение соответствия k-partite является NP-трудным для нахождения:
http://www.math.tau.ac.il/~safra/PapersAndTalks/k-DM.ps
См. данную статью для неоптимального решения k-partite соответствие проблеме:
Я уверен, что можно найти других на Google сами теперь, когда Вы знаете, что условия ищут. Я не знаю, существует ли эффективный алгоритм, дающий оптимальное решение для k=3.
Это отличается от расширения стабильной проблемы соединения, с тех пор поскольку я понимаю вопрос OP, у людей в каждой группе нет заказанного списка того, с кем они хотят работать от большинства до наименьшего; это - двоичные отношения (желающий/не желающий).
Это может быть сформулировано как проблема целочисленного программирования, которая может быть решена вполне быстро. Я даю математическую формулировку проблемы ниже; можно использовать пакет как glpk или AMPL/CPLEX для обработки данных.
Определите следующие матрицы:
M1 = |A| x |B| матрица, где
M1(a,b) = 1 если (данный члена A) готово работать с b (данный члена B), и 0 иначе
M2 = |A| x |C| матрица, где M2(a,c) = 1 если (данный члена 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 стабильной проблемы соответствия). Независимо, хотя, это - 3D проблема соответствия который известный быть NP-трудным (см. Garey и Johnson). Для решения такой проблемы разумным способом вероятно, что необходимо будет использовать некоторую форму ограничения, целое число или линейное программирование (методы других существуют). Что-то, что могло бы быть полезным, является новой Microsoft Solver Foundation, поэтому проверьте ее.
Прежде всего, можно устранить любые факты, где у этих двух сторон есть непересекающиеся списки того, с кем они будут работать в третьей группе. Затем запустите грубую силу, поиск в глубину, всегда выбирающий от наименее популярного до самого популярного.
С другой стороны, эквивалентный вышеупомянутому устранению, сформируйте список всех возможных трио и работы от этого вместо этого.