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.


 

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

22221. Дощатые и клеефанерные настилы покрытий 2.93 MB
  Клеефанерные панели выполняют функции настила прогонов водо и пароизоляции. По форме поперечного сечения клеефанерные панели могут быть следующих видов: 1 коробчатые; 2 ребристые обшивкой вверх; 3 ребристые обшивкой вниз Коробчатую клеефанерную панель применяют в утепленных покрытиях с рулонной кровлей и гладким потолком Она имеет двухсторонние обшивки образующие вместе с ребрами ряд полостей в которые по слою пароизоляции укладывают утеплитель. Наиболее распространенными являются коробчатые клеефанерные панели которые используют не...
22222. Балки и прогоны цельного сечения. Составные балки на податливых связях 3.02 MB
  Балки и прогоны цельного сечения Основное функциональное назначение балок и прогонов в том что они служат несущими конструкциями покрытий. Балки и прогоны цельного сечения выполняются из досок на ребро брусьев и бревен чаще окантованных с двух сторон. Ввиду ограниченности размеров сечений и длины лесоматериалов такие балки применяют при пролетах до 6 м.
22223. Государство и право в период нэпа 22.6 KB
  Еще в годы гражданской войны Зиновьев Каменев Бухарин говорили о диктатуре уже не пролетариата а о диктатуре партии. Троцкий – диктатура партии при содействии красной армии национализация средств производства монополия внешней торговли. С одной стороны речь идет о диктатуре партии. Большинство соратников Ленина придерживались позиции диктатуры партии.
22224. Право в периода новой экономической политики 21.33 KB
  Как поднять доходы – налоги. Налоги. Мы говорили что государство может существовать без каких то отношений но сказать то мы можем не собирать налоги невозможно Первым декретов в 1918 г. Эти налоги падали на в прошлом господствующие классы.
22225. Гражданское право. Семейное право 20.13 KB
  Государство ограничивает субъекта правоотношений какими-то рамками. С самого начала был поставлен первый принцип что у нас не должно быть ничего частного государство может вмешаться в любые имущественные отношения. Первый советский гражданский кодекс – первый момент – государство может вмешаться в любые правоотношения. Государство вводило нэп чтобы поднять экономику.
22226. Советская государственная система в 30х годах ХХ столетия 21.98 KB
  МИЛИЦИЯ УЖЕ ОФИЦИАЛЬНО ВХОДИТ в состав угпу до этого было секретное постановление. Постановление ЦИК СССР. 17 ноября снк СССР принимает постановление где констатируется что при упрошенном ведение дела в 1937 1938г. Этим постановление осуждалась практика массовых арестов.
22227. Государство диктатуры пролетариата 22.61 KB
  советские нпа б. дооктябрьские нпа в. Нпа советского государства основной источник Нормы дооктябрьского права Правосознание Именно нпа советского госва будет постоянно расширяться. Советы всех уровней принимали нпа.
22229. Создание советского государственного аппарата 20.28 KB
  В связи с этим большевики стали проводить национализацию. Но что теперь делать Большевики думали что учредительное собрание передаст власть Советам. Большевики знали. Большевики обещали демократизацию.