Пишу программу составления школьных расписаний на Лисп, уже на первом этапе возникли трудности

Здравствуйте, пишу в качестве выпускного проекта программу составления расписаний на Лиспе, при этом испытываю большие сложности с самого начала, в голове практически пусто.
Начать решил с функции проверки расписания на корректность, при этом само расписание представил так:
В корневом списке содержатся классы. Каждый класс - это тоже список. Первым в нем идет номер класса, за ним буква. дальше подряд идут дни.
Каждый день - тоже список. И содержит он ряд описаний уроков. Описание урока (какая неожиданность) - и на этот раз список. Первым в нем идет строка с названием предмета, дальше имя учителя и в конце номер аудитории.
В каждом классе дни начинаются с одного и того-же, и уроки каждый день с одного и того-же. Вся эта мишура списков - суть есть таблица, и для проверки нужно проверить, не ведут ли учителя уроки у разных классов или не занят ли один кабинет сразу несколькими классами.
С чего мне начать? Если бы у всех классов каждый день было одно и тоже количество уроков, было бы проще (тут напрашивается мысль про выравнивание).

0

Сообщение от helter К счастью, я не знаю, что такое методические дни.

Это дни, выделяемые учителям, когда они не ведут уроков, а заняты бумажной работой и подготовкой к занятиям.

0

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

0

Сообщение от helter Пусть, например, 20 классов - это 30!^20 комбинаций.

Это теоретическая сложность. На практике все будет проще.
Учитывая, что с 1 по 3 класс все предметы ведет классный руководитель.
В 4-5 классе не физики и химии.
Так же нужно учитывать приоритет следования предметов от сложных до не очень.
Сначала математика, в конце физкультура.
Все это можно реализовать в правилах на списках.

Топикастер не указал минимальный набор входных данных:
- список учителей - предметников
- количество часов по каждому предмету за определенный срок
- список доступных аудиторий
- ограничения по количеству уроков в день

Сложность задачи даже на курсовую работу не тянет, ИМХО.

0

Сообщение от chessman2 Сложность задачи даже на курсовую работу не тянет, ИМХО.

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

Лично я вижу сразу проблемы от которых бросает в дрожь)
Первая - это множественность критериев проверки, при условии, что если какой-то критерий не удовлетворяет необходимым условиям, то всё расписание придётся переделывать.
Втрое - это сложность самого мероприятия. Допустим, вы проверили 7 уроков и у вас всё сходиться, но на восьмом возникает ошибка, что ломает всё расписание. Вам нужно переделать расписание, а для этого вам нужно опять начать проверку с нуля, при этом нужно как-то хранить данные о тех событиях, которые привели к ошибке и учитывать их в последующем процессе изменении расписания.
Если для вас это так просто, то опишите, пожалуйста, хотя бы приблизительный алгоритм решения. Мне будет интересно почитать.

1

Сообщение от sodda Первая - это множественность критериев проверки, при условии, что если какой-то критерий не удовлетворяет необходимым условиям, то всё расписание придётся переделывать.

Что в этом сложного? Соедините их and-ом, будет один критерий.

Сообщение от sodda а для этого вам нужно опять начать проверку с нуля

Необязательно с нуля. Это же поиск в графе. Но мне кажется, граф всё равно необъятный. Нужны хитрые алгоритмы.

0

Сообщение от sodda хотя бы приблизительный алгоритм решения.

Обсуждалось.
Не уверен что, то нужно, где-то близко. Надо подумать.
Задача о рюкзаке

Это интересно
https://habr.com/ru/post/222577/

0

Сообщение от helter Что в этом сложного? Соедините их and-ом, будет один критерий

Только в этом нет никакого смысла. Каждая проверка должна к чему-то приводить, к каким-то перестановкам в расписании.

Сообщение от helter Необязательно с нуля. Это же поиск в графе. Но мне кажется, граф всё равно необъятный. Нужны хитрые алгоритмы.

Поэтому результат каждой неудачной проверки где-то нужно хранить и как-то учитывать.

Ну вот смотрите. Мария Ивановна ведёт литературу во Вторник в 302 аудитории третьей парой, а Николай Петрович ведёт в это же время там физику. Нужно переместить куда-то один урок, при этом всём расписание может сдвигаться и то, что было правильно и верно ранее, теперь может сломаться.

0

Сообщение от sodda Ну вот смотрите. Мария Ивановна ведёт литературу во Вторник в 302 аудитории третьей парой, а Николай Петрович ведёт в это же время там физику. Нужно переместить куда-то один урок, при этом всём расписание может сдвигаться и то, что было правильно и верно ранее, теперь может сломаться.

В моём представлении расписание заполняется последовательно.

Пусть для 1 "А" расписание составлено, и во вторник в 302 аудитории третьей парой у него стоит литература. В процессе - составление расписания для 1 "Б". Очередная незаполненная клетка - как раз вторник. Очередной неиспользованный урок 1 "Б" - физика, аудитория 302. Заполняем клетку. Проверка расписания: универсальный валидатор говорит "не пойдёт", потому что ему валидатор аудиторий сказал "не пойдёт". Откатываем физику, следующий неиспользованный урок - химия, аудитория 303. Проходит валидацию, заполняем клетку, двигаемся дальше.

Если же физика была последним неиспользованным уроком, мы в тупике. Тогда надо откатить предыдущий урок 1 "Б" и попробовать заменить его на очередной неиспользованный, т. е. на физику. И т. п. Я не знаю, зачем расписываю поиск в глубину, алгоритм стандартный. Вершинами графа являются корректные частичные расписания, стрелка из вершины А в вершину Б означает, что Б получено из А заполнением очередной клетки. Очевидно, не каждое корректное частичное расписание можно продолжить до корректного полного расписания.

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

А что вы говорите, похоже как раз на изобретение хитрого алгоритма, как я его называю. Точнее сказать - умного. Исследовательская задача, голова начинает болеть ещё до того, как это себе представишь. Тут я, конечно, пас.

Вторая надежда - что в рамках учебной задачи расписание может быть игрушечным. Но это надо с "заказчиком" всё обговаривать.

1

Сообщение от helter Очевидно, не каждое корректное частичное расписание можно продолжить до корректного полного расписания.

Поэтому у меня была мысль о создании нескольких таблиц с расписанием и потом наложение их друг на друга и сравнение. На основе этого сравнения формирование итого расписания.

Сообщение от helter Пусть для 1 "А" расписание составлено, и во вторник в 302 аудитории третьей парой у него стоит литература. В процессе - составление расписания для 1 "Б". Очередная незаполненная клетка - как раз вторник. Очередной неиспользованный урок 1 "Б" - физика, аудитория 302. Заполняем клетку. Проверка расписания: универсальный валидатор говорит "не пойдёт", потому что ему валидатор аудиторий сказал "не пойдёт". Сообщение от helter Откатываем физику, следующий неиспользованный урок - химия, аудитория 303 Откатываем физику, следующий неиспользованный урок - химия, аудитория 303. Проходит валидацию, заполняем клетку, двигаемся дальше.

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

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

На самом деле это всё топорно очень и не соответствует критериям реального расписания. Допустим у вас есть три урока химии в неделю, но ваше автоматизированное расписание составляется так, что три эти урока получаются подряд, друг за другом, на неделе. Совпало так, что туда подходят по вашему валидатору именно эти уроки, ошибки не было. Но это с точки зрения реального расписания это неверно, так как для усвоения пройденного материала и подготовки к следующему уроку требуется время. То есть должны учитываться реальные критерии. В этом и сложность.

1

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

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

Сообщение от sodda Допустим у вас есть три урока химии в неделю, но ваше автоматизированное расписание составляется так, что три эти урока получаются подряд, друг за другом, на неделе. Совпало так, что туда подходят по вашему валидатору именно эти уроки, ошибки не было. Но это с точки зрения реального расписания это неверно, так как для усвоения пройденного материала и подготовки к следующему уроку требуется время. То есть должны учитываться реальные критерии.

Реальные критерии должны быть формализованы. Они формализуются валидаторами. Если нельзя иметь три одинаковых урока подряд, есть валидатор, который говорит: "три и более уроков подряд" - не проходит. Общая валидация имеет вид

расписание валидно, если:
- в одновременно несколько уроков не проходят в одном кабинете
- одновременно учитель не ведёт несколько уроков
- в один день (или не в один день) три одинаковых урока не могут идти подряд
и ещё что угодно.

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

Для тупых алгоритмов типа поиска в глубину, которые ничего не знают о валидаторах, число валидаторов несущественно. Хардкодить их не надо. Грубо говоря, собрать любые нужные валидаторы в один список и проверять (loop for validator in *validators* always (valid-partial-timetable-p partial-timetable validator). Я это называю не "топорно", а "гибко".

0

Сообщение от helter Теоретически, поиск в глубину позволяет обойти весь граф. Значит, при наличии безграничного времени, расписание составится, и даже гораздо быстрее, чем рандомом.

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

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

Делайте. Я буду только рад, если у вас получится)

0

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

Один урок не может не проходить. Не проходить, то есть быть невалидным, может быть только частичное расписание. Валидатор принимает частичное расписание целиком.

Конечно, может быть, что придётся откатиться назад, а потом ещё назад, и ещё, и до самого корня - пустого расписания, и неоднократно. И что? Вы пытаетесь меня убедить, что поиск в глубину отменили?

Сообщение от sodda Делайте. Я буду только рад, если у вас получится)

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

0

Сообщение от helter Конечно, может быть, что придётся откатиться назад, а потом ещё назад, и ещё, и до самого корня - пустого расписания, и неоднократно. И что? Вы пытаетесь меня убедить, что поиск в глубину отменили?

Ничего не пытаюсь. Просто говорю, что задача непростая, вот и всё.

0

Не могу не согласиться.

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

0

Сообщение от helter то и не наша задача. Это пускай в университетах голову ломают.

Сообщение от helter это и не наша задача.

Как раз задача наша.
Согласен - хороший алгоритм - победит.
Делал числа фибоначи - питон обоганал Си в несколько раз.
Си - рекурсися ---- питон - умножение матриц. Алгоритм.

0

Сообщение от chessman2 Это теоретическая сложность. На практике все будет проще.

вот как бы не так

Добавлено через 3 минуты

Сообщение от Regrin1 Первым в нем идет номер класса, за ним буква

а ты их складывать собрался? вычитать умножать извлекать логарифмы? какой стыд

0

Сообщение от vlisp а ты их складывать собрался? вычитать умножать извлекать логарифмы? какой стыд

Мне нужно контролировать номер класса для учета нагрузки!

0