Разделите людей на команды для наибольшего удовлетворения
Просто вопрос любопытства. Помните, когда в групповой работе профессор делил людей на группы определенного числа (n)?
Некоторые из моих профессоров возьмут список n люди, с которыми хочется работать и n людей, с которыми не хочется работать, от каждого студента, а затем волшебным образом собирать группы n где ученики будут сопоставляться с людьми, которых они предпочитают, и избегать работы с людьми, которые им не нравятся.
Для меня этот алгоритм звучит очень похоже на проблему рюкзака, но я подумал, что могу спросить о том, каким будет ваш подход к такого рода проблемам.
РЕДАКТИРОВАТЬ: нашел статью ACM, описывающую что-то в точности как мой вопрос. Прочитайте второй абзац для дежавю.
4 ответа
Для меня это больше похоже на проблему клики.
Как я вижу проблему, я бы настроил следующий график:
- Вершины будут студентами
- Два студента были бы связаны ребром, если бы выполнялись обе следующие вещи:
- По крайней мере, один из двух студентов хочет работать с другим.
- Ни один из двух студентов не хочет работать с другим.
Затем нужно разбить граф на клики размером n. (Предполагая, что количество студентов делится на n)
Если бы это было невозможно, я бы, вероятно, пропустил первое ограничение на ребра и имел ребра между двумя людьми, если ни один из них явно не говорит, что они не хотят работать с другим.
Что касается подхода к эффективному решению этой проблемы, я понятия не имею, но, надеюсь, это поможет вам ближе разобраться в проблеме.
Вы можете легко смоделировать это как проблему кластеризации, и вам даже не нужно будет определять пространство, вы можете просто определить расстояния:
Сделайте двух людей очень близкими, если они оба хотят работать вместе. Закройте, если один из них хочет работать с другим. Среднее расстояние, если есть только апатия. Далеко, если один не хочет работать с другим.
Тогда вы могли бы просто найти кластеры, ура. Затем разделите любые кластеры слишком большого размера, с уверенностью, что люди в кластерах будут хорошо работать вместе.
Эта проблема может быть грубой, поэтому мой подход был бы сначала сделать ее грубой, а затем исправить ее, когда я получу лучшее представление.
Есть пара алгоритмов, которые вы можете использовать. Отличным примером является так называемая "проблема стабильного брака", которая имеет идеальное решение. Вы можете прочитать больше об этом здесь:
http://en.wikipedia.org/wiki/Stable_marriage_problem
Проблема стабильного брака работает только с двумя группами людей (мужчины / женщины в случае брака). Если вы хотите сформировать пару, вы можете использовать вариацию, проблему стабильного соседа по комнате. В этом случае вы создаете пары, но все приходят из одного пула.
Но вы попросили команду (которую я перевожу в>2 человека на команду). В этом случае вы можете разрешить всем заполнить свои лучшие и худшие совпадения, а затем запустить