23652

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

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

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

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

Русский

2013-08-05

59 KB

6 чел.

Лабораторная работа № 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.


 

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

35399. Тема: Програмування арифметичних дій множення і розподіл. 53.5 KB
  Індивідуальне завдання Скласти програму яка знайде приватне чисел 99 і 9. Множення двійкових чисел без знаку. Для множення чисел без знаку призначена команда mul сомножитель_1 Розташування операндів і результату при множенні. Перший співмножник Другий співмножник Результат Байт L 16 бітів в АХ: L молодша частина результату; АН старша частина результату Слово АХ 32 біти в парі DX:X: АХ молодша частина результату; DX старша частина результату Подвійне слово ЕАХ 64 біти в парі EDX:EX: ЕАХ молодша частина результату; EDX ...
35401. Тема: Програмування арифметичних виразів. 443 KB
  Розташування операндів і результату при множенні. Перший співмножник Другий співмножник Результат Байт L 16 бітів в АХ: L молодша частина результату; АН старша частина результату Слово АХ 32 біти в парі DX:X: АХ молодша частина результату; DX старша частина результату Подвійне слово ЕАХ 64 біти в парі EDX:EX: ЕАХ молодша частина результату; EDX старша частина результату Розподіл чисел із знаком і помилки що виникають в результаті розподіли Для розподілу чисел із знаком призначена команда idiv дільник Для цієї команди...
35403. СОЦИАЛЬНЫЕ И ЛИЧНОСТНЫЕ ОСОБЕННОСТИ ЖЕНЩИН, ПЛАНИРУЮЩИХ ПРЕРЫВАНИЕ БЕРЕМЕННОСТИ 519.5 KB
  Проблема абортов стоит на особом месте в нашей стране, в связи с социально-демографическими условиями. Эффективность мер принимаемых государством по охране репродуктивного здоровья женщин и здоровья населения в целом оценивается с учетом динамики, количества проведенных абортов.
35404. Теоретическая механика, краткий курс 8.07 MB
  В теоретической механике изучается одна из форм движения материи – механическое движение, состоящее в том, что тело с течением времени изменяет свое положение в пространстве по отношению к другим телам. Механическим называют тот вид взаимодействия тел, в результате которого происходит изменение их движения или изменение их формы (деформация).
35406. Тема: Управління процесом завантаження ОС. 85.5 KB
  Мета: Навчитися створювати завантажувальну дискету різними способами; навчитися використовувати її у разі аварійної ситуації в роботі ПК. Використовуючи можливості Windows створіть системну дискету для аварійного завантаження ПК у разі неполадок в її роботі. Які файли при цьому скопіюються на дискету Створіть завантажувальну системну дискету командою formt з командного рядка MS DOS. Які файли при цьому скопіюються на дискету formt[ :] [ q] [ fs файловая_система] Тип файловой системы которая будет создана на диске: FT...
35407. ПРЕОБРАЗОВАТЕЛЬ ПОСЛЕДОВАТЕЛЬНОГО КОДА В ПАРАЛЛЕЛЬНЫЙ С КОНТРОЛЕМ ПО КОДУ ХЭММИНГА И С ИСПРАВЛЕНИЕМ ОДИНОЧНЫХ ОШИБОК 1.02 MB
  Разработать преобразователь последовательного кода в параллельный с контролем по коду Хэмминга и с исправлением одиночных ошибок. Скорость приема по кадру - 10МБод. Количество стартовых бит – 1, количество стоповых бит – 1, количество байт в кадре – 32, преобразованные данные передаются далее по 16 разрядной шине со скоростью 100 Мбайт/сек. Если кадр принят с ошибкой, вырабатывается сигнал ошибки. Информация поступает в устройство по одному проводу