Алгоритм для создания школьного расписания

Обновление: от комментариев ... должен иметь эвристики тоже!

Я бы пошел с Prolog ... затем используйте Ruby или Perl или что-то, чтобы очистить ваше решение в более красивую форму.

teaches(Jill,math).
teaches(Joe,history).

involves(MA101,math).
involves(SS104,history).

myHeuristic(D,A,B) :- [test_case]->D='<';D='>'.
createSchedule :- findall(Class,involves(Class,Subject),Classes),
                  predsort(myHeuristic,Classes,ClassesNew),
                  createSchedule(ClassesNew,[]).
createSchedule(Classes,Scheduled) :- [the actual recursive algorithm].

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

Для такого планирования часто используются генетические алгоритмы.

Найден этот пример (Составление расписания классов с использованием генетического алгоритма) , который вполне соответствует вашему требованию.

Это беспорядок. Королевский беспорядок. Чтобы добавить к ответам, уже очень завершено, я хочу указать на мой семейный опыт. Моя мама была учителем и использовалась участвовать в процессе.

Оказывается, что наличие компьютера для этого не только трудно кодировать SE-SE, он также сложно, потому что есть условия, которые трудно указать на предварительно испеченную компьютерную программу. Примеры:

• Учитель учит как в вашей школе, так и в другом институте. Очевидно, что если он заканчивает урок туда в 10.30, он не может начать в ваших помещениях в 10.30, потому что ему нужно какое-то время для поездки между институтами.
• Два учителя женаты. В целом, это считается хорошей практикой, чтобы не иметь двух женатых учителей в том же классе. Поэтому эти два учителя должны иметь два разных класса
• , два учителя женаты, и их ребенок посещает ту же школу. Опять же, вы должны помешать двум учителям преподавать в конкретном классе, где их ребенок.
• Школа имеет отдельные объекты, как однажды класс в одном институте, а другой день класс в другом.
• Школа имеет общие лаборатории, но эти лаборатории доступны только на определенные будни (по соображениям безопасности, например, где требуется дополнительный персонал).
• Некоторые учителя имеют предпочтения на свободный день: некоторые предпочитают в понедельник, некоторые в пятницу, некоторые в среду. Некоторые предпочитают приходить рано утром, некоторые предпочитают прийти позже.
• У вас не должно быть ситуаций, когда у вас есть урок, история в первый час, затем три часа математики, затем еще один час истории. Это не имеет смысла для студентов, ни для учителя.
• Вы должны раскрывать аргументы равномерно. Не имеет смысла иметь первые дни в неделю только математика, а затем остальная часть недели только литература.
• Вы должны дать некоторым учителям два часа подряд, чтобы сделать оценочные тесты.

Как вы можете видеть, проблема не является NP-завершением, это NP-безумный.

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

Вот несколько ссылок, которые я нашел:

Школьное расписание - Перечисляет некоторые проблемы

Гибридный генетический алгоритм для школьного расписания

Утилиты и инструменты планирования

Одним из моих полуурочных заданий было создание генетически-алгоритмической школьной таблицы.

Целая таблица - это один "организм". В подходе к генерированию общих генетических алгоритмов были внесены некоторые изменения и предостережения:

• Были составлены правила для "незаконных таблиц": два класса в одном классе, один учитель, преподающий две группы одновременно и т.д. Эти мутации считались смертельными сразу же, и вместо "умершего" сразу же прорастали новые "организмы". Первоначальный был сгенерирован серией случайных попыток получить легальный (если он бессмысленный). Смертельная мутация не учитывалась при подсчете мутаций в итерации.

• Мутации "Обмена" встречались гораздо чаще, чем мутации "Изменения". Изменения происходили только между теми частями гена, которые имели смысл - не подменяя учителя классом.

• Маленькие бонусы назначались для связывания определенных 2 часов вместе, для последовательного выделения одного и того же общего класса для одной и той же группы, для поддержания рабочего времени учителя и непрерывной нагрузки на класс. Умеренные бонусы были назначены за правильное распределение кабинетов по данному предмету, сохранение рабочего времени в пределах ограничений (утром или днем) и тому подобное. Большие бонусы назначались за правильное количество заданных предметов, заданную нагрузку на преподавателя и т.п.

• Учителя могли создавать свои рабочие графики "хотят работать тогда", "хорошо работать тогда", "не любит работать тогда", "не может работать тогда", с назначенными правильными весами. Все 24 часа были легальными рабочими днями, за исключением того, что ночное время было очень нежелательным.

• Функция веса... о да. Функция веса была огромным, чудовищным продуктом (как в умножении) весов, присвоенных выбранным характеристикам и свойствам. Она была чрезвычайно крутой, одно свойство легко могло изменять ее на порядок вверх или вниз - и в одном организме были сотни или тысячи свойств. Это приводило к абсолютно огромным числам в качестве весов, и, как прямой результат, к необходимости использования библиотеки бинумов (gmp) для выполнения вычислений. Для небольшого теста около 10 групп, 10 учителей и 10 классных комнат начальный набор начинался с отметки 10^-200something и заканчивался 10^+300something. Он был абсолютно неэффективен, когда был более плоским. Кроме того, с большими "школами" значения выросли на гораздо большее расстояние.

• Во время вычислений была небольшая разница между небольшим населением (100) в течение длительного времени и большим населением (10k+) в течение меньшего количества поколений. Вычисления за то же время производили примерно того же качества.

• Расчет (на некоторых 1 ГГц процессоре) занял бы около 1 часа, чтобы стабилизироваться около 10^+300, генерируя графики, которые выглядели бы довольно неплохо, для упомянутого тестового случая 10x10x10.

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

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

Эта проблема сложнее, чем кажется.

Как уже упоминали другие, это NP-полная проблема, но давайте проанализируем, что это значит.

По сути, это означает, что вам нужно рассматривать все возможные комбинации.

Но «посмотри» мало что скажет о том, что вам нужно делать.

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

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

Для этого вам нужно больше, чем просто «возможно ли это решение».

Например, один и тот же учитель работает 5 дней в неделю в течение X недель подряд? Даже если это рабочее решение, оно может быть не лучшим решением, чем чередование двух человек, чтобы каждый учитель занимался по одной неделе каждый. О, ты не думал об этом? Помните, вы имеете дело с людьми, а не только с проблемой распределения ресурсов.

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

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

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

Простой Regex:

\w +

Соответствует строке символов "word". Это почти то, что вы хотите.

Это несколько точнее:

\w (? < !\d) [\w '-] *

Он соответствует любому количеству символов слова, гарантируя, что первый символ не является цифрой.

Вот мои совпадения:

1 ЛОЛОЛОЛ
2 ВЫ ИМЕЕТЕ
3
4 PWN3D
5 einszwei
6 drei

Это больше похоже на это.

EDIT:
Причина негативного взгляда в том, что некоторые цвета regex поддерживают символы Юникода. При использовании [a-zA-Z] будет пропущено несколько желательных символов "слова". Разрешение \w и запрет \d включает в себя все символы Юникода, которые могли бы начать слово в любом блоке текста.

EDIT 2:
Я нашел более сжатый способ получить эффект отрицательного lookbehind: Double negative character class с единственным отрицательным исключением.

[^\W\d] [\w '-] * (? < =\w)

Это то же самое, что и выше, за исключением того, что это также гарантирует, что слово заканчивается символом слова. И, наконец, есть:

[^\W\d] (\w | [- '] {1,2} (? =\w)) *

Обеспечение наличия не более двух несловосочетаний в строке. Она совпадает со словами, но не со словами, что имеет смысл. Если вы хотите, чтобы он соответствовал "word--up", но не "word---up", вы можете изменить 2 на 3 .

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

В любом случае, команда sed (Stream Editor) - это то, что вы ищете:

sed s/search/replace oldfilename > newfilename

Если вам нужна нечувствительность к регистру:

sed -i s/search/replace oldfilename > newfilename

Если это необходимо для динамического выполнения в PHP, вы можете использовать passthru () :

$output = passthru("sed s/$search/$replace $oldfilename > $newfilename");

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

Удачи!

Эта статья довольно хорошо описывает проблему школьного расписания и их подход к алгоритму: "Разработка SYLLABUS-An Interactive, Constraint-Based Scheduler for Schools and Colleges. "[PDF]

Автор сообщает мне, что программное обеспечение SYLLABUS все еще используется/разрабатывается здесь: http://www.scientia.com/uk/