Алгоритм для автоматического составления расписания занятий (пар, уроков) в институте

[iogun]

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

[RaZEr]

Какие входные параметры должны быть у такого алгоритма

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

[Kvarx]

Как нам сказали в универе, это достаточно сложно составить расписание идеально, потому что алгоритм не учитывает чисто человеческие факторы, поэтому у нас делают в ручную

Это задача линейного программирования.

[iogun]

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

[Decline]

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

[BorLase]

да не обязательно пролог тут нужен

сгодится любой язык - алгоритм рекурсивного перебора

1) ставим занятие в сетку
2) если поставить не получается, возвращаемся на шаг назад, сдвигаем занятие, идем на п. 1

ничего фантастического, тривиальная задача (не пугайте человека)

[iogun]

с прологом я знаком попробую, был когда то спецкурс.

[Drakosha]

По моему, "Это задача линейного программирования." - 100% правильно.

[helldomain]

Chto-to takoe nakidali za paru dnei kogda-to. Raspredelenie po auditoriyam (cel optimizacii: minimalnoe rasstoyanie odnogo zdaniya ot drugogo dlya prowedeniya lekcij chto-bi ne prihodilos begat). Rapsredelenie lekcij i.t.d. s uchetom prioritetow (prioriteti: obedennij chas po-wozmojnosti swoboden, lekcii doljni raspolagatsya s minimalno wozmojnim kol-wom probelow). Yazik goditsya liuboi, mi klepali kajetsya na jave. Samoi gimornoi chastju bilo dat sostawiteliu raspisaniya wruchnuju formirowat prioriteti. Wkliuchili dlya etogo wozmojnost napisaniya prawil na java script. Dlya interpretacii js wospolzowalis paketom ot netscape.

[Decline]

Сообщение от BorLase

да не обязательно пролог тут нужен

сгодится любой язык - алгоритм рекурсивного перебора

1) ставим занятие в сетку
2) если поставить не получается, возвращаемся на шаг назад, сдвигаем занятие, идем на п. 1

ничего фантастического, тривиальная задача (не пугайте человека)

Ну-ну а сложность такого алгоритма представляешь?
Сложность <n! где n-количество предметов в неделю.
А потом на Прологе задача будет решаться не более чем за строк 100 )
На C++ структуру данных дольше описывать будем.

[BorLase]

Decline, что ты подразумеваешь под "сложностью"? Рекурсивный алгоритм будет не намного длиннее прологовского

[Decline]

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

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

Я сторонник использования Пролога в задачах перебороного характера и работе с текстом(хотя на счет 2-го можно поспорить) - проще получается для программиста.

Под сложностью подразумевал максимальное количество ветвей перебора.

Расскидать преподователей по аудиториям. Только не забудьте, что у преподователя не должно быть перерыва больше одной пары, у студентов не должно быть разрывов в занятии вообще. Вот тогда это расписание будет идеальным. Как то работал я в школе, полгода бился над алгоритмом, но так до конца и не довел. Мой единственный бетатестер завуч с 20 летним стажем каждый раз рубил мою реализацию проблемы.

[Mad Max]

А можно ли конкретнее описать проблему? Какие данные ввода, параметры и т.д.?

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

http://im-coma.de/vv/stundenplan.php?sem=hws06

Вот оно. Правда на немецком, но разобраться можно: внизу neues fach auswählen это выбрать предмет (и далле подкатегории), вверху HWS06 это семестр (оссенне-зимний) и т.д.

Поэкспериментируй.

[melk]

Decline:
Я сторонник использования Пролога в задачах перебороного характера и работе с текстом(хотя на счет 2-го можно поспорить) - проще получается для программиста.

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