Разделите людей на команды для наибольшего удовлетворения

Question

Просто вопрос из любопытства. Помните, когда в групповой работе профессор делил людей на группы определенного числа (n)?

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

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

РЕДАКТИРОВАТЬ : Нашел статью ACM , описывающую что-то в точности как мой вопрос. Прочитайте второй абзац для дежавю.

Answer 1

Для меня это больше похоже на какую-то клику проблему.

Как я вижу проблему, я бы настроил следующий график :

• Вершинами будут студенты
• Два студента были бы соединены ребром, если выполняются обе следующие вещи:
  1. По крайней мере, один из двух студентов хочет работать с другим.
  2. Ни один из двух студентов не хочет работать с другим.

Тогда нужно разбить граф на клики размером n. (Предполагая, что число студентов делится на n)

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

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

Answer 2

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

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

Тогда вы могли бы просто найти кластеры, ура. Затем разделите любые кластеры слишком большого размера, с уверенностью, что люди в кластерах будут хорошо работать вместе.

Answer 3

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

Answer 4

Есть пара алгоритмов, которые вы можете использовать. Отличным примером является так называемая «проблема стабильного брака», которая имеет идеальное решение. Подробнее об этом можно прочитать здесь:

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

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

Но вы попросили команду (которую я перевожу в> 2 человека на команду). В этом случае вы можете позволить всем заполнить свои лучшие и худшие матчи, а затем запустить