Как реализовать алгоритм распределения мест для лекций

Question

у нас есть около 1000 бесплатных мест для наших лекций в нашем университете, и около 2000 рабочих мест (может быть, 500 студентов требуют 4 места в каждом).
Я разрабатываю веб-приложение с CakePHP, которое позволяет студентам создаватьсписок желаний и введите 4 лекции на блок, с приоритетами от 1 до 4. (Это затем входит в базу данных MySQL)

Теперь веб-интерфейс завершен, действия администратора (добавление лекций, добавление лекторов,и т. д.) все готово ... осталось только написать алгоритм распределения.

Как мне лучше всего это сделать?MySQL-скрипт кажется полезным, но mysql не очень дружелюбен, когда дело доходит до циклов и if-конструкций, верно?
Было бы разумно экспортировать данные куда-нибудь и позволить другому языку решить проблему?

Редактировать: dnagirl запросила дополнительную информацию об алгоритме: у нас нет бизнес-правил для алгоритма.Мы адаптировали существующее (очень дорогое) приложение от кого-то другого в другом университете, в котором есть правила, которые мы только что адаптировали.
То, что он делает (и то, что я пытаюсь клонировать, чтобы сэкономить большую плату за семестр),это:

• Все события (лекции, упражнения и т. д.) принадлежат блоку (например, «Международная политика», в котором может быть 4 или 5 различных событий)
• Студенты могут подать заявкудо 4 событий на блок с приоритетами от 1 до 4.
• Алгоритм работает на блок.Для каждого блока разделите студентов на разные группы в соответствии с их рейтингом.(Рейтинг «чем выше, тем лучше». Обычные рейтинги - от 0 до 20)
• Из группы студентов с наивысшим рейтингом выберите случайным образом один.Дайте ему место в событии, которое он выбрал с приоритетом 1. Если это событие заполнено, дайте ему место, которое он выбрал с приоритетом 2;и т. д. до 4.
• Выберите следующего ученика и делайте то же самое, пока каждый ученик с таким рейтингом не получит место.Затем перейдите к следующему более низкому рейтингу и сделайте все снова.Когда этот блок закончен, сделайте все снова со следующим блоком, пока все блоки не будут завершены.

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

Answer 1

Возможно, вам нужен какой-то генетический алгоритм:

• Создание случайного распределения студентов по лекциям
• Рассчитать балл (высокий балл исполненных желаний, перебронированные лекции дают штраф и т.
• Внести изменения (например, перевести одного студента на другую лекцию). Если счет увеличивается, сохраните его, в противном случае отклоните.
• Продолжайте итерацию, пока не будет найдено никаких изменений, которые увеличивают счет: вы нашли локальный минимум
• Повторите все это несколько раз, чтобы найти другие локальные минимумы. Тогда выбирайте лучшее решение.

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

MySQL не очень подходит для этого; Вы лучше решите это в PHP, а затем сохранитесь за один раз. Если производительность не достаточно хорошая, вы можете даже подумать о ее реализации в C ++, но я советую сначала попробовать PHP и посмотреть, достаточно ли он быстр. Не похоже, что вы будете запускать это каждые 2 секунды.