Программа составления расписания, подскажите алгоритм Опции

[Chester]

Решать задачу за меня никого не прошу, прошу помочь ;) и вообще пора переходить на обсуждени есложных программ
Программа не из легких, мне кажется.
Итак, есть список преподавателей (1 препод. ведет 1 предмет), классов. Условия: есть максимальное кол-во часов в которое учитель может работать с таким-то классом в неделю, ограничения по дням недели (может работать только во вторник, или ,например, все дни кроме среды), кол-во часов которое он может работать в одном классе в день (пусть например, 2).
ну там конечно еще условий дофига, но я хотел бы чтобы мне сначала посоветовали, как делать это. Жду идей

Сообщение отредактировано: Chester - 13.03.2004 21:25

[Dark]

Хм, програмно я это не делал ) но хочу попробовать... что получиться - дам
Это я делал тока на Аксесе )

[DI]

1организовать ввод данных с файла
2использовать массив записей
3для дней недели использовать множество,
4начиная с 1-го дня недели проверяешь всех преподов(если два препода могут работать в этот день выбираешь того который может только вэтот день) по каждому предмету
Млин определённо чё-то забыл....

[Chester]

Допустим, ввод данных можно опустить, пусть будет константа.
А как задавать сами условия?

[DI]

А сколько и какие у тебя условия ?
Думается, для каждого случая по-разному...
В основном при помощи циклов и процедур
У тебя ,наверно, процедура будет похожа на сортировку массива -
пока не будут выполняться все условия она не должна быть закончена..

[Chester]

Условия такие:

• по 1-2 урока в день в одном классе (в смысле в данном классе, а не всего 2 урока в день у учителя)
• по 2 урока в день в одном классе
• по 1-2 урока в день в одном классе с разрывом в 1 день (то есть чтобы предмет шел в данном не подряд два дня)

Я и хотел делать с помощью массива (array[days,subjects,1..6], число уроков 6) . Только как задавать сами условия, проверку и как сортировать? Мне бы алгоритм узнать.

Сообщение отредактировано: Chester - 16.03.2004 20:43

[Fire_Rage]

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

[Chester]

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

[Fire_Rage]

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

[trminator]

Возможно, пройдет метод на динамическом программировании. Будет рекурсивная процедура примерно такого плана:

Код

procedure make_shed;
   if возможно добавить предмет (есть время в учебном плане) then
       for i := 1 to n do
           if i-й учитель свободен в первый же незанятый день,
           begin
               добавить этого учителя (точнее, его предмет)
               make_shed;
               убрать этого учителя, чтобы попытаться сунуть другого
           end;
   else получено расписание -- выйти из всех этих процедур
end;

Фактически тут идет полный перебор всех вариантов =(

А массив с расписанием, может, сделать плоским? (то есть примерно как расписание, которое в школе висит -- двумерная матрица, а не трехмерная =) )

[Guest]

Fire_Rage
Если ты не заметил, то посмотри пару постингов выше, я писал (как раз над тем постом, где ты говоришь что не писал).
trminator
размерность идет так: по дням недели, по классам, по урокам (сверху я что-то не так написал), то есть 3х мерный получается; не я понимаю, что он на "2х мерной" бумаге как 2х мерный выглядит А ты можешь написать примерчик, с несколькими условиями? чтобы не по-русски после IF'ов

[trminator]

Хмм... на стенке в школе расписание вроде не трехмерное висит +) Вот мне и показалось, что двумерное удобнее (прообразом таблицы может служить как раз школьное расписание).

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

[Atos]

Да, действительно, трёхмерная получается... Так и создать трёхмерный массив [1..DayOfWeek, 1..Class,1..MaxLessons] of word. Потом заполнить его номерами учителей - это и будет расписание. В процедуру make_shed передавать его по значению - тогда не придётся "убирать этого учителя, чтобы сунуть другого".
Если расписание составлено - выводить его прямо из процедуры. Передавать в процедуру x, y, z, изначально равные 1 - это координаты текущей заполняемой ячейки. Перед рекурсивном вызовом make_shed делать inc(z) если z<MaxLessons else begin z:=1 ; inc(y); и т.д. Если x=DayOfWeek то расписание составлено.
Вообще, предложенный алгоритм make_shed мне понравился: прост и ясен, как всё гениальное. Сразу ясна становится структура проги, а оптимизировать детали можно по ходу написания.

[trminator]

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

[Fire_Rage]

Fire_Rage
Если ты не заметил, то посмотри пару постингов выше, я писал (как раз над тем постом, где ты говоришь что не писал).

Во-первых, ты написал не все условия(к примеру в тот-то день неможет данный учитель и т.д. и т.п.)
Во-вторых будет 3-хмерный массив-класс, дни недели, и сами уроки на этот денб.
в-третих, я собираюсь делать по генетическому алгоритму.

Сообщение отредактировано: Fire_Rage - 2.04.2004 10:40

[Atos]

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

Да, действительно, я как-то не подумал... Ну, тогда x,y,z передавать по значению. (x,y,z) - как бы граница между заполненной и незаполненной частью массива, причём нам неважно, что незаполненная может быть забита всяким мусором.{может быть, она уже считалась заполненной в процессе рекурсивных вызовов, но мы этого "не помним"}

Chester, напиши все конкретные условия по учителям. Надо будет составить массив записей Teacher, заполнить поля, и уже тогда конкретно прописать кодом условие if i-й учитель свободен в первый же незанятый день

[trminator]

Можно заводить трезмерный массив не [1..DayOfWeek, 1..Class,1..MaxLessons], а [0..DayOfWeek, 0..Class,0..MaxLessons]. В нулевых элементах можно хранить, сколько дней/классов/уроков уже распланировано. Тогда откат -- просто уменьшение на единицу одного из этих чисел +)

А вообще задача еще интересует автора?

[Chester]

интересует
руки только что-то не доходят. условия уже пишу, половину накромсал (их не то чтобы очень много), остальное скоро допишу
сюда можно html таблицу вставить? у меня в виде таблички просто

Сообщение отредактировано: Chester - 6.04.2004 19:08

[Atos]

Можно присоединить к ответу htm- файл, если меньше 50 K.

[imp]

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