23652

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

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

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

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

Русский

2013-08-05

59 KB

8 чел.

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


 

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

28444. Массивы. Описание одномерного массива. Ввод – вывод одномерного массива. Обработка одномерных числовых массивов. Описание двумерного массива. Ввод – вывод двумерного массива. Обработка двумерных числовых массивов 30 KB
  Описание одномерного массива. Ввод вывод одномерного массива. Описание двумерного массива. Ввод вывод двумерного массива.
28445. Особенности договорных отношений и оформление договорной документации между юридическими лицами и участниками туристской деятельности 29.5 KB
  Договоры с авиа компаниями могут быть трех видов: договор на квоту мест на регулярных авиа рейсах; агентское соглашение; чартер аренда самолета. Договор на квоту мест на регулярных авиа рейсах. Квота мест может быть жесткой или мягкой. При жесткой квоте мест вся ответственность за не реализацию мест падает на туристскую фирму независимо от причины не реализации.
28446. Технология составления и основное содержание туристской документации 43.5 KB
  В набор технологической документации для каждого тура обязательно включаются: технологическая карта туристского путешествия по маршруту; график загрузки туристского предприятия группами туристов на определенное время; информационный листок к путевке туристского путешествия; бланки путевок типовой формы ТУР1 Туристская путевка утвержденной Минфином России; лист бронирования см. Технологическая карта туристского путешествия это документ наглядно и лаконично дающий все необходимые для работы сведения и данные по туру...
28447. Порядок движения документов в организациях социально 32 KB
  Порядок движения документов в организациях социальнокультурного сервиса и туризма. Документооборот д о это движение документов в организации с момента создания или получения до отправки или передачи их на хранение. Основой структуры любого документооборота является документ комплекс документов связанный процессов управления разных уровней и автоматической обработкой. Единый маршрут для одного вида документов или совокупности документов образует документопоток.
28448. Особенности договорных отношений и оформление договор 33.5 KB
  Турфирмы же туроператоры и турагенты это организации занимающиеся деятельностью по формированию продвижению и реализации или только по продвижению и реализации туристского продукта. В соответствии со статьей 9 Закона о туризме туроператор при формировании и продвижении туристского продукта приобретает право на услуги входящие в тур на основании договоров с лицами предоставляющими отдельные услуги или с туроператором по приему туристов обеспечивающим предоставление всех видов услуг входящих в тур. Порядок реализации туристского...
28450. Связь цен с различными экономическими показателями: спрос, затраты, деятельность конкурирующих предприятий, качество 120.5 KB
  К факторам влияющим на цену относятся: существующий или создаваемый спрос размер понесенных затрат деятельность конкурирующих предприятий ситуация на финансовом рынке установленный стандарт услуг. Это ограничивает прибыль от повышения цены поскольку может оказаться что в результате повышения цен определенное число клиентов откажется от услуг в результате чего продажи упадут Сильное повышение цены может ограничить или ликвидировать спрос. Нельзя рассматривать проблему спроса на гостиничные услуги вне зависимости от ее цены. Повышение...
28451. Гостиничная услуга, ее специфика и составные элементы. Особенности работы гостиничного предприятия 74.5 KB
  Зависимость гостиничных услуг от целей путешествия объясняется тем что решения гостя посетить определенное место основывается как правило не на факторе наличия в этом месте конкретной гостиницы. Колебания спроса непосредственным образом связаны с социальноэкономической и политической обстановкой месторасположения гостиницы. работа персонала гостиницы особенно тех кто непосредственно контактирует с клиентами требует умения и желания находить общий язык с самыми разными людьми поскольку среди постояльцев гостиницы бывают богатые и...
28452. Понятие и содержание инновационных процессов. Сущность и виды инноваций. Модель инновационной деятельности 63.5 KB
  В мировой практике и экономической литературе инновации интерпретируются как превращение потенциального научно технического прогресса в реальный воплощающийся в новых продуктах технологиях и услугах. Инновационная деятельность это деятельность направленная на практическое использование научнотехнических результатов с целью получения нового продукта для удовлетворения потребностей общества. Инновации нововведение это конечный результат инновационной деятельности получивший применение в виде нового или усовершенствованного продукта...