23652

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

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

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

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

Русский

2013-08-05

59 KB

9 чел.

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


 

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

78766. Правове регулювання електронної комерції в Україні. Національне законодавство та міжнародні стандарти 134.5 KB
  Матеріали дослідження можуть бути використані для розширення методологічної бази правових галузевих досліджень. Одержані результати можуть бути використані: у практиці правозастосування з метою подолання існуючих проблем та методичних рекомендацій; для проведення подальших теоретичних...
78767. Технологія перевезення вугілля морським транспортом 110.4 KB
  Метою даного дипломного проекту полягає у висвітленні наступних завдань: Ознайомитись з транспортною характеристикою вугілля; Встановити особливості перевезення вугілля морським транспортом; З’ясувати характеристику ринку вугілля.
78768. Створення форонтиспісу у програмі Photshop 2.36 MB
  З усіх видів криття брошур основним є криття врозпуск при якому на обкладинці роблять чотири рубчики і приклеюють її не тільки до корінця а й до першої сторінки блока. Комбіноване фальцювання Формат видання це розмір сторінки видання після обрізки блока по ширині і довжині.
78769. Вышивка атласными ленточками 3.28 MB
  Для вышивки лентами используются длинные иглы поэтому когда на игле остается очень короткий конец ленты завершить узор бывает проблематично. Для того чтобы вывести на изнаночную сторону ткани короткий конец ленты выньте его из иглы затем иглу без ленты вколите до самого ушка в...
78770. Роль Русской Православной Церкви в кризисные моменты истории России 316.5 KB
  Сюда можно отнести несколько факторов: Существование мощных течений которые свидетельствуют о крупной роли Русской Православной Церкви в деле формирования и поддержания русской государственности: Первым актом национального самосознания русского народа было крещение в Православие.
78771. Эксплуатация судовых вспомогательных и утилизационных котлов 480.17 KB
  Специфика морского транспорта как сферы экономики заключается в том, что он сам не производит продукцию, а только участвует в ее создании, обеспечивая производство сырьем, материалами, оборудованием и доставляя готовую продукцию потребителю.
78772. Изучение форм бухгалтерской отчетности ЗАО «Восход» 666.5 KB
  Цель работы состояла в изучении форм бухгалтерской отчетности конкретного сельскохозяйственного предприятия, выявление возможных направлений улучшения организации ее составления и использования для совершенствования управленческой деятельности в соответствующем хозяйстве.
78773. Облік процесу запасів процесу виробництва 244 KB
  Підприємницька діяльність можлива різних видів: виробнича, комерційна або грошово-кредитна. Згідно з цим запаси діяльності такі: у першому випадку – різні речовини та сили природи: сировина, матеріали (основні, допоміжні паливні, мастильний тощо), у другому – готова продукція виробничої сфери...
78774. Элементы окна меню Mozilla Firefox 2.94 MB
  Браузер — это программное обеспечение для просмотра Web-страниц. В настоящее время существует богатый выбор различных браузеров. Наиболее популярными являются Internet Explorer, Mozilla Firefox, Apple Safari, Netscape, Opera. Web-страница — электронный документ, в котором кроме текста содержатся специальные...