разделение группы по предпочтениям

Question

Я пытаюсь взять группу из двадцати человек (помеченных 1 - 20) и разделить их на пять подгрупп по 4 в каждой, исходя из выраженных предпочтений того, с кем эти люди хотят быть.

Каждый человек в группе из 20 человек может выразить 0, 1, 2, 3 или 4 предпочтения. Например, person1 может выбрать 0 (без предпочтения, с кем они), или 14 (в группе с person14) или может быть выражено, чтобы быть в группе с лицами 14, 20, 6 и 7. В идеале каждый человек с предпочтением будет в группе, по крайней мере, с одним выбором.

Идеи по алгоритму?

Answer 1

Проблема, с которой вы столкнулись, на самом деле не связана с C #, алгоритм не зависит от языка.

Классическая реализация для этих проблем - возврат .

Дополнительная информация:

• Проблемы удовлетворения ограничений в Википедии
• Рекомендовано: Глава 5 «Искусственный интеллект - современный подход», 2-е издание

Другой подход (я бы пошел на это): Генетические алгоритмы .

Answer 2

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

Как говорит Виктор Хурдугачи , это в основном алгоритмическая проблема, не зависящая от языка (хотя я бы хотел, чтобы мой пример, приведенный ниже, был реализован с помощью LINQ!)

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

Наивное решение для грубой силы (псевдокод)

Мы начнем с набора людей (здесь: 4, чтобы упростить вещи):

people = { a, b, c, d }

Мы можем найти все возможные подгруппы фиксированного размера (здесь: 2), используя оператор choose:

groups = people.choose(2)  // = { {a,b} {a,c} {a,d} {b,c} {b,d} {c,d} }

Мы можем найти все возможные комбинации подгрупп, снова используя оператор choose:

combi = groups.choose(4/2) // = { {ab,ac} {ab,ad} {ab,bc} {ab,bd}
                           //     {ab,cd} {ac,ad} {ac,bc} {ac,bd}
                           //     {ac,cd} {ad,bc} {ad,bd} {ad,cd}
                           //     {bc,bd} {bc,cd} {bd,cd} }

Очевидно, что люди не могут быть в двух группах одновременно, поэтому мы удаляем все недопустимые комбинации:

combi2 = combi.select(g => g.bigUnion().size == 4)
                           // = { {ab,cd}, {ac,bd}, {ad,bc} }

Теперь вам нужно найти «лучший» элемент, основанный на некоторой функции пригодности, то есть комбинации, которая набирает наибольшее количество баллов с учетом предпочтений.

result = combi2.maximumBy(g => fitness(g))

Например, если a имеет предпочтение для b, а b, c и d не имеют никаких предпочтений, тогда calculateScore должно вернуть более высокий балл для {ab,cd}, чем для {ac,bd} и {ad,bc}.

Улучшенное решение

Существует несколько алгоритмов, которые решают эту проблему оптимизации. Я думаю, что алгоритм альпинизм хорошо бы здесь подходил.