Алгоритм C # для определения группировки людей на основе значения

Question

Я пытаюсь написать алгоритм, который создает группы людей на основе их «оценки». У человека есть два параметра, имя и оценка. (Диапазон баллов составляет от -10 до 10, но это на самом деле не имеет значения) Я ищу создание групп с равным количеством людей (если возможно, исходя из количества представленных людей), где средний балл членов группы то же самое (или очень близко к тому же).

Например:

Группа 1 (Средний балл = 2) - Джон Доу, оценка 2 - Джейн Доу, оценка 7 - Джек Блэк, оценка -3

Группа 2 (Средний балл = 2) - Бобби Флай, оценка 4 - Кэри Пейдж, оценка -3 - Линус Тарвал, оценка 5

Answer 1

Это пахнет как вариант классической проблемы разбиения , которая является NP-Hard, хотя существует некоторая эвристика. Вы можете получить добычу на странице википедии ... вероятно, жадный подход будет работать в вашем случае.

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

Answer 2

Это сложная проблема. Лучшее, что вы, вероятно, сделаете, - это эвристика, но k-средних - это хорошо: http://en.wikipedia.org/wiki/K-means_clustering