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

Question

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

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

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

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

Answer 1

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

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

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

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

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

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

Answer 2

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

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

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

Answer 3

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

Answer 4

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

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

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

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