Алгоритм сортировки людей по комнатам по возрасту и национальности

Question

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

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

По сути, в школе у ​​нас целая куча разных комнат - от одноместных до общежитий на 8 человек. У нас много разных национальностей со всего мира, и мы всегда стараемся сделать так, чтобы в каждом номере были разные национальности. Там, где есть несколько национальностей, мы стараемся их сбалансировать. Возраст также важен, мы всегда собираем учеников одного возраста, все еще пытаясь смешать национальности, и для нас непривычно, что студенты делятся между собой более двух лет.

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

Надеюсь, я четко объясню, чего я пытаюсь достичь ... таким образом, это звучит очень просто, но я пытаюсь придумать, как это сделать простым способом, то есть путем сортировки по национальности, а затем по возрасту. но это не сокращает это, и я знаю, что должен быть лучший способ приблизиться к этому. Когда я делаю это «вручную» на листе Excel, это выглядит довольно интуитивно.

Спасибо всем, кто предлагает помощь / совет.

Answer 1

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

Answer 2

Как насчет того, вы думаете о комнате как о чем-то, что отталкивает учеников уже имеющейся национальности и привлекает учеников близкого возраста к тому, что у нее уже есть. Чем ближе средний возраст к среднему, тем больше он привлекает его, и чем больше в комнате парней X-образной национальности, тем больше они отталкивают парней X-национальной национальности.

Тогда, для каждого добавляемого нового студента, вы должны пройтись по каждой комнате и посмотреть, какая из них привлекает больше. Я думаю, что если комната пуста, вы можете установить все силы на 0. Кроме того, у вас будет пара констант, которые умножают каждую из обеих «сил», так что вы можете откалибровать ее в зависимости от того, насколько важен одинаковый возраст и насколько важен это иметь разные национальности.

Answer 3

Прежде всего вы можете найти это интересным: Устойчивая проблема соседей по комнате (википедия) . К сожалению, он не отвечает на ваш вопрос.

Попробуйте генетический алгоритм .

Существует три основных критерия использования генетического алгоритма:

• способность представлять решение в виде изменяемого массива. У нас может быть массив целых чисел, так что [i] - это комната для i-го студента.

• мутация состояния должна давать предсказуемые результаты. В нашем случае это правда. Мутирование массива предсказуемо будет перетасовывать студентов между комнатами.

• легко написать быструю функцию пригодности. Не должно быть слишком сложно написать функцию пригодности O (n).

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

Answer 4

Формулировка как общая задача оптимизации

Будет полезно формализовать ограничения и параметры.Предположим, что для 1 <= i <= 8 у нас есть n_i комнат размером i.Теперь давайте наложим жесткое ограничение на то, что в конкретной комнате S на каждые два студента a, b \ in S мы имеем следующее: </p>

|Grade(a) - Grade(b)| <= 2 (1)

Теперь мы заинтересованы в оптимизации функции «разнообразия», которая интуитивнопредставляет идею, что мы хотим, чтобы комнаты были как можно более смешанными.Таким образом, мы можем представить эту цель в виде:

max over all arrangements {{ Sum over all rooms S of DiversityScore(S) }}
    where we have DiversityScore(S) = # of Different Nationalities in the Room

Формулировка в виде задачи о графике

Это наиболее общий параметр, но, очевидно, максимальное значение по всем схемам неосуществимо в вычислительном отношении.Теперь давайте представим это как своего рода графическую проблему с жесткими ограничениями на оценку.Обозначим всех студентов как вершину в графе G. Соедините две вершины, если студенты удовлетворяют ограничению (1).Теперь клика на этом графике представляет группу студентов, которых можно разместить в одной комнате.Теперь действуйте в жадной манере.Выберите самую большую клику размера 4, которая имеет наибольшую оценку разнообразия.Затем поместите их в комнату и продолжайте, пока все комнаты не будут заполнены.Этот метод поиска клики может также включать в себя гендерные ограничения, что полезно, но не так, чтобы определение клики было трудной задачей NP.

Теперь, прежде чем пытаться придумать что-то, что может быть быстрее, давайте подумаем, как ослабитьжесткое ограничение (1).Мы можем помассировать нашу графическую формулировку, включив граничные веса в изображение.Поэтому, если жесткое ограничение выполнено, обозначим граничный вес от i до j как 1. Если два ученика i и j отклоняются на возраст более 2, обозначим граничный вес как 1 / (разница в возрасте) ^ 2 или что-то еще.Тогда оценка клики должна быть произведением весов края клики с некоторой оценкой разнообразия.Однако становится ясно, что теперь проблема заключается в полном графе, который является лишь общей оптимизацией, которую мы надеялись избежать, поэтому нам необходимо наложить некоторые жесткие ограничения для уменьшения связности нашего графа.

Базовая сортировкаАлгоритм аппроксимации

Сортировка всех учеников по возрасту, поэтому у нас есть отсортированный массив, в котором все ученики в [i] имеют одинаковый возраст, и все ученики в [i] старше всех учеников в [i]j] для всех j

Answer 5

Общая тема «назначить x для y в отношении ограничений при оптимизации некоторого количества» относится к исследованию операций или, более конкретно, http://en.wikipedia.org/wiki/Mathematical_optimization. Обычный подход заключается в том, чтобы формально определить проблему и использовать универсальный решатель оптимизации, такой как как один из перечисленных в http://en.wikipedia.org/wiki/List_of_optimization_software.

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

Answer 6

Я бы проанализировал каждого учащегося и создал бы вектор «личности», основываясь на его / ее возрасте и национальности.Затем я сортировал векторы и, возможно, немного сортировал результаты после сортировки, чтобы поощрить разнообразие.