23652

Экспертная система по составлению учебных расписаний

Лабораторная работа

Информатика, кибернетика и программирование

При составлении расписаний лучше исходить не из заданной цели к тому же трудно сформулировать какое расписание €œлучше€ а из возможностей комбинирования учебных дисциплин. Далее можно попытаться оценить относительную ценность полученных расписаний их уже будет не так много с точки зрения быстрейшего и полного освоения дисциплин специализации в необходимой пропорции с факультативными и общеобразовательными курсами. Представим что студенту желающему специализироваться в конкретной области предоставлена возможность самостоятельного...

Русский

2013-08-05

59 KB

5 чел.

Лабораторная работа № 4

«Экспертная система по составлению учебных расписаний»

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

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

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

                                                                 

                           

                                                               

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

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

         1.Каждый студент должен пройти за семестр 4 курса.

         2.Известен перечень обязательных курсов для данной специальности и необходимые для их изучения предшествующие курсы.

         3.Имеется перечень факультативных курсов и их обязательных предшественников, из которых студенту разрешен выбор.

         4.В каждое расписание должно быть включено не менее одной  общественной дисциплины по выбору студента.

        База данных, касающихся данной специальности, должна включать в себя 4 типа фактов:

Обязательные курсы:

req («Введение в вычисление»).

req («Структуры данных»).

req («Ассемблер»).

req («Операционные системы»).     и т.д.

Факультативные курсы:

elec («Информатика»).

elec («Трансляторы»).    и т.д.

        Факты, устанавливающие обязательность предшествования:

impreq(«Структуры данных», «Введение в вычисления»).     

impreq («Мат. анализ 2», «Мат. анализ 1»).

impreq («Операционные системы», «Ассемблер»).

и т.д.

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

       Факты, утверждающие, что курс читается в данном семестре:

givennow("введение в вычисление").

givennow("Мат.анализ 2").   и т.д.

        База данных, касающихся конкретного студента, должна включать факты о пройденных им (passed) курсах, или курсах, которые студент желает  пропустить (waived ), как изученные им ранее, например, самостоятельно.

passed («Ассемблер»).

passed («Структуры данных»).

...............................

waived(«Введение в вычисления»).

waived («Мат. анализ 1»).        и т.д.

        Введем правило среднего уровня для определения обязательных курсов, доступных студенту:

reqcourse(Х): -  req(X), not(donewith(X), givennow(X), havepreq(Х).

      Смысл правила: X будет одним из возможных обязательных курсов в расписании, если:

является обязательным для данной специальности;

студент его еще не изучил  в вузе или самостоятельно;

курс читается в данном семестре;

студент сдал зачёты по всем необходимым предшествующим курсам.

        Обязательные курсы req(X) и читаемые в данном семестре givennow(X) содержатся в фактах БД. Правило определения пройденного курса:

donewith(Х):-passed(X).

donewith(X):-waived(X).

Список всех пройденных курсов (Q) определяется правилом:

а1ldonewith(Q): - findall(Х, donevith(Х), Q).

Далее нужно создать список Z всех необходимых предшествующих курсов для данного курса Х с помощью правила allpreq:

allpreq(Х, Z): - findall(Y, preq(X, Y), Z).

preq(X, Y): - impreq(X, Y).

preq(X, Y): - impreq(X, Z), preq(Z, Y).

 Как видно, правило findall заставляет работать подчинённое правило preq всеми возможными способами и собирает в список Z  не только непосредственных (прямых) предшественников с помощью фактов impreq, записанных в БД, но и путем рекурсии выявляет всех непрямых предшественников. Подобное правило встречалось нам в работе № 2.

          Последнее ограничение, налагаемое на комбинирование, касается необходимости иметь зачёты по всем курсам, являющимся обязательными предшественниками данного курса X. Это ограничение описывает правило havepreq:

havepreq(Х):- allpreq(Х, Z), alldonewith(Q), subset(Z, Q).

        Смысл правила: студент имеет зачеты по всем обязательным  курсам, предваряющим курс Х, если все эти предваряющие курсы  находятся в списке Z, сформированном правилом allpreq, и если все  пройденные или  пропущенные вследствие изученности студентом курсы находятся в списке Q, и если  при этом список Z является подмножеством списка Q.

        Правило subset определяет вхождение элементов списка Z в список Q, используя обычное правило member:

subset([ ], Q).

subset([Х|Xs], Q): - member(Х, Q), subset(Xs, Q).

Правило member в данном случае устанавливает членство элемента Х из списка Z в списке Q, и оно приведено в предыдущих работах. Структура другого правила высокого уровня для оценки возможности включения в расписание факультативного курса Х, сходно с рассмотренным правилом:

eleccourse(Х): - еlес(Х), not(donewith(Х)), givennow(Х), havepreqfor(Х).

  На этом формирование ограничений, которые призваны значительно уменьшить пространство поиска, окончено. Остаётся сформировать правило комбинирования курсов в расписаниях. Но при этом предстоит решить главную задачу – оценки качества расписаний. Ведь следует помнить, что нас интересуют не любые, а лучшие в некотором смысле расписания. Поэтому программа должна уметь ранжировать генерируемые расписания по каким-то эмпирическим признакам.  Для решения этой задачи можно использовать другую эвристическую стратегию ограничения поискового пространства – составления ограниченного набора правил комбинирования курсов, ранжированных в порядке уменьшения ценности получаемых расписаний. Например, наиболее ценными условимся считать те расписания, в которых комбинируются три обязательных и одна общественная дисциплина. Это может позволить студенту быстрее овладеть специальными знаниями. Тогда правило  1-го ранга schedule в системе правил наивысшего уровня для поиска допустимых расписаний будет таким:

schedule(A, B, C, "gen.elec"): - regcourse(A), regcourse(B),

regcourse(C), ordered3(A, B, C).

ordered3(A, B, C): - A < > B,  A < > C, B < > C, not(dbschedule(A,B,C)),

asserta (dbschedule(A, B, C)),

asserta (dbschedule(A, C ,B)),

asserta (dbschedule(B, A, C)),

asserta (dbschedule(B, C, A)),

asserta (dbschedule(C, A, B)),

asserta (dbschedule(C, B, A)).

Если поставить цель schedule (A, B, C, "gen.elec"), то программа должна осуществлять поиск неповторяющихся комбинаций из 3-х различных обязательных курсов, проверяя возможность включения каждого курса в расписание с помощью правила reqcourse. Правило ordered3(A, B, C ) следит за различием курсов, проверяет условие отсутствия данной комбинации в БД и пополняет рабочую память всеми возможными комбинациями.

        Следующим по ценности, т.е. правилом schedule 2-го ранга, условимся считать то, в котором комбинируются 2 обязательных, 1 факультативный и один общественный курс.

schedule(A, B, C,  gen.elec»): - reccourse(A),  reccourse(B),  eleccourse(С),

ordered2(A, B, C).

ordered2(A, B, C): - A <> B,  not(dbschedule(A, B, C)),

                           asserta(dbschedule(A, B, C)),

                           asserta(dbschedule(B, A, C)).

        Здесь правилу ordered2 достаточно проверить условие несовпадения 2-х обязательных курсов и отсутствие сочетания из A,B,C в БД. Предикат asserta заносит в рабочую память два возможных варианта перестановок  из 2-х обязательных курсов.

          После рассмотренного правила 2-го ранга поставим правило комбинирования  из одного  обязательного, 2-х факультативных и  одной общественной дисциплины и т.д., пока не дойдем до расписания из  4-х общественных  дисциплин. Всего таких правил поиска комбинаций, ранжированных в порядке убывания ценности расписаний, будет 10. Последним будет расписание, состоящее из 4-х общественных дисциплин.

    Студент может обратиться к правилу 1-го ранга. Программа будет по очереди  использовать правила в порядке их ранжирования и выдаст список всех возможных при данных ограничениях расписаний в порядке убывающей, по мнению составителя программы (эксперта), ценности. Такой подход облегчает выбор одного наиболее подходящего расписания. Полный текст программы lab4_1.pro приведен на дискете. В этой программе предусмотрена запись формируемых расписаний в файл с последующим выводом на печать для удобства просмотра. Для этого в каждое из правил schedule вставлен вызов правила record с различными значениями аргументов в зависимости от ранга правила. Само правило record - общее для всех:

record(A,B,C):-openappend(f, «result.txt»), writedevice(f),

write(A, «   »,  B, «   », C,  «   »,  «gen.elec»), nl,  closefile(f).

        Процедуры, находящиеся в теле данного правила, можно вставить в каждое правило schedule, добавив при печати  перед каждым выводимым расписанием   сведения о применённом правиле. Именно так сделано в предлагаемой базовой программе lab4_1.pro.

Самостоятельная часть работы

Программа lab4_1.pro содержит в себе полезные функции вывода заголовка перед каждым типом сгенерированных расписаний. Но эта программа работает с условно-номерными курсами и требует, чтобы все предшествующие данному курсу дисциплины были пройдены (по схеме “И”).  Другая программа lab4_1m.pro работает с символьными именами и позволяет включить курс в расписание, если выполнена хотя бы одна из двух альтернативных цепочек необходимого предшествования (по схем “ИЛИ”).   Пример альтернативных фактов impreq:

impreq(«Диалоговые средства», «Объектный Паскаль»).

           impreq(«Диалоговые средства», «С++»).

       Объясните работу программы и исследуйте, как влияет  ограничение “ИЛИ” на число получаемых расписаний.

  •  Для решения этой задачи объедините достоинства обеих программ в одной с возможностью выбора пользователем одной из схем поиска предшественников.
  •   С увеличением числа комбинируемых курсов «k» число  N правил комбинирования schedule возрастает, хотя и не так быстро, как можно было бы ожидать. Так, при k=4 (в данной программе) N=10. При k=5 —> N=15 и т.д. Попытайтесь найти и  обосновать общую формулу для вычисления N через k.


 

А также другие работы, которые могут Вас заинтересовать

8940. Система стандартов приспособлений для металлорежущих станков 467 KB
  Система стандартов приспособлений для металлорежущих станков Являются дополнением к учебной литературе при изучении лекционного курса Технологическая оснастка. Рекомендуются для самостоятельной работы студентов, обучающихся по направлению 151000 Кон...
8941. Система смазки двигателя автомобиля ВАЗ 2110 124 KB
  Система смазки двигателя автомобиля ВАЗ 2110 Содержание: История создания автомобиля Общее устройство автомобиля Система смазки двигателя автомобиля ВАЗ 2110 Самый первый автомобиль. 26 января 1886 года... Дата, навсегда вошедшая в...
8942. Принципи організації документообігу та його особливості 129.13 KB
  Принципи організації документообігу та його особливості Порядок руху документів в організаціях не завжди продуманий - багато документів проходять довгий і заплутаний шлях від створення чи отримання до до виконання, ряд операцій з ними дублюєтьс...
8943. Психология и педагогика. Учебное пособие 2.51 MB
  Психология и педагогика Учебное пособие подготовлено в соответствии с Государственными образовательными требованиями (федеральный компонент) к обязательному минимуму содержания и уровню подготовки выпускников высшей школы по циклу Общие гуманитарные...
8944. Административно-территориальное устройство и экономическое районирование России. Исторический аспект и настоящее время 406.5 KB
  Тема:Административно-территориальное устройство и экономическое районирование России. Исторический аспект и настоящее время. Введение. Экономическое районирование является основой территориального управления народным хозяйством России. В насто...
8945. Розрахунок конвеєр стрічковий пересувний КЛП-20 340.59 KB
  Розрахунок конвеєр стрічковий пересувний КЛП-20 Содержание Введение. Вихідні дані для конвеєра, що транспортує – гравій. Розрахунок ширини стрічки конвеєра. Визначення навантажень...
8946. Понятие парадигмы и принцип пролиферации 39 KB
  Понятие парадигмы и принцип пролиферации. Понятие парадигмы Понятие парадигмы (в современной интерпретации) было введено в научный оборот Томасом Куном в его труде Структура научных революций. Кунн исходит из представления о науке как о социал...
8947. Неокантианство. Представители неокантианства 36 KB
  Неокантианство. Главным объектом критики неокантианства стало учение И. Канта об объективно существующей, но непознавемой вещи в себе. Неокантианство трактовало вещь в себе как нредельное понятие опыта по мысли представителей данного направления, п...
8948. Позитивизм. Общенаучные методы познания 35 KB
  Позитивизм. Общенаучные методы познания. Позитивизм (франц. positivisme, от лат. positivus - положительный), философское направление, исходящее из тезиса о том, что все подлинное, положительное (позитивное) знание может быть получено лишь как резуль...