Разделите людей на команды для большей части удовлетворенности
Просто вопрос о любопытстве. Помните, когда в классе groupwork преподаватель разделил бы людей на группы определенного числа (n)?
Некоторые мои преподаватели взяли бы список n люди каждый хочет работать с и n люди каждый не хочет работать с от каждого студента и затем волшебно оказываться группами n где студенты подошлись бы в людях, они предпочитают и не работают с людьми, которых они не предпочитают.
Мне этот алгоритм много походит на Задачу о ранце, но я думал, что расспрошу тут и там о том, каков Ваш подход к этому виду проблемы был бы.
Править: Найденный статьей ACM, описывающей что-то точно как мой вопрос. Прочитайте второй абзац для дежа вю.
3 ответа
Для меня это больше похоже на какую-то проблему с кликами.
Как я вижу проблему, я бы создал следующий граф:
- Вершинами будут студенты
- Два студента будут соединены ребром, если выполняются оба следующих условия:
- По крайней мере, один из двух студентов хочет работать с другим.
- Ни один из двух студентов не хочет работать с другим.
Затем нужно разбить граф на клики размера n. (Предполагается, что число студентов кратно n)
Если бы это было невозможно, я бы, вероятно, допустил первое ограничение на ребра, и имел бы ребра между двумя людьми до тех пор, пока ни один из них явно не скажет, что не хочет работать с другим.
Что касается подхода к эффективному решению этой проблемы, я понятия не имею, но это, надеюсь, поможет вам приблизиться к пониманию проблемы.
Эту проблему можно использовать методом грубой силы, поэтому мой подход будет заключаться в том, чтобы сначала ее применить, а затем исправить, когда у меня появится лучшее представление.
Вы можете легко смоделировать это как проблему кластеризации, и вам даже не понадобится определять пространство, вы можете просто определить расстояния:
Сделайте двух людей очень близкими, если они оба хотят работать вместе. Близко, если один из них хочет работать с другим. Среднее расстояние, если есть только апатия. Далеко, если один из них не хочет работать с другим.
Тогда вы можете просто найти кластеры, ура. Затем разделить любые кластеры слишком большого размера, с уверенностью, что люди в кластерах будут прекрасно работать вместе.