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

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

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

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

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

Ответ 1

Для меня это больше похоже на проблему clique.

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

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

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

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

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

Ответ 2

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

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

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

Ответ 3

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

Ответ 4

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

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

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

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