Решение творческих задач методом блочных альтернативных сетей: объектно-ориентированные представления

МОСКОВСКИЙИНСТИТУТРАДИОТЕХНИКИ,ЭЛЕКТРОНИКИИ АВТОМАТИКИ

(ТЕХНИЧЕСКИЙУНИВЕРСИТЕТ)

ФакультетКибернетики

КафедраИнтеллектуальныхтехнологийи систем (ИТС)

Курсоваяработа

Тема: Решениетворческихзадач методомблочных альтернативныхсетей: объектно-ориентированныепредставления.

Студенты:

Группа: АИ-1-91

Руководитель: Нечаев В. В.

Москва 1996 г.

Заданиена курсовоепроектированиепо дисциплине«Основы теориитворческойдеятельности»студентамгруппы АИ-1-91.

1. Темаисследования: решение творческихзадач методомблочных альтернативныхсетей дляобъектно-ориентированныхсистем.

2. Исходныеданные:

   1. Теорияконцептуальногометамоделирования.

   2. Методырешения системныхзадач.

   3. Списоклитературы.

   4. Методическиеуказания ккурсовомупроектированию.

   5. Конспектлекций.

   6. Темадипломногопроекта.

3. Переченьвопросов, подлежащихразработке:

   1. Описаниепроблемнойобласти задач,выносимой надипломныйпроект.

   2. Проведениеанализа конкретнойзадачи, выносимойна курсовуюработу.

   3. Выбори обоснованиеметода решениязадачи.

   4. Анализи описаниеметода решениязадачи.

   5. Описаниерешения задачина основевыбранногометода.

4. Календарныйплан-графикработы:

1. Получениезадания 21.04.96.

2. Анализзадания, подбори изучениелитературы25.04.96.

3. Разработкаконцептуальнойметамоделиобъекта моделирования09.05.96.

4. Оформлениепояснительнойзаписки и сдачапроекта напроверку 21.05.96.

5. Защитакурсовогопроекта 24.05.96.

Руководитель…………..(НечаевВ. В.)

^(подп.)

Исполнители

^(подп.)

Содержание

Введение

1. Постановказадачи

   1. Концептуальноеметамодельноепредставлениезадачи

   2. Формаорганизацииучебного процессаи базовыекомпоненты предметнойобласти

      1. Аудиторныйфонд

      2. Контингентучащихся

      3. Профессорско-преподавательскийсостав

      4. Комбинированныйучебный план

      5. Расписаниезанятий

2. Методологиярешения задачи

2.1. Модельпредставлениязнаний дляпроекта «Учебноерасписание»

2.1.1.Объектно-ориентированнаямодель представлениязнаний

2.1.2 Блочнаяальтернативнаясеть

2.1.2.1. Элементарныйблок альтернатив

2.1.2.2Структура БАС

2.2. Методыформированиярешения

2.2.1Алгоритмынавигации наБАС

2.2.2. Маршрутына БАС

2.2.3 Оценкарезультатоврешения задачина БАС

3. РеализацияБАС на ОО системев проекте «Учебноерасписание»

3.1.Структуракласса

3.2.Правила представлениязнаний

3.3. Фрагментрешения задачи«Формированиеучебного расписания»

3.3.1.Класс«Учебный блок»

3.3.2.Класс «Блокзанятия»

3.3.3.Класс «Блокизанятий»

Списоклитературы

4

5

8

8

8

9

10

11

13

13

14

16

16

21

22

22

23

26

27

27

29

31

31

35

38

40

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

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

Для этогонеобходимоее формализовать,т.е. разбить наподзадачии выделитьосновные целирешения:

1) выборметодологиирешения задачина основеискусственного

интеллекта;

2) определениеалгоритмареализацииметода;

3) разработкапакета программ,реализующихалгоритм.

Целью работы являетсяописание моделипредставлениязнаний и методоврешения творческихзадач на примерезадачи формированиярасписанияна основе анализаучебного плана,дополненногопланом нагрузкипреподавателей(форма 101).

В первомразделе рассматриваетсяпостановкасистемнойзадачи на основеконцептуальногометамодельногопредставления.

Во второмразделе представленаметодологиярешения творческихзадач на блочныхальтернативныхсетях дляобъектно-ориентированныхсистем,

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

Экономическаяэффективностьрешения задачибудет оценена на основе методовфункционально-стоимостногоанализа

1. Постановказадачи

1.1. Концептуальноеметамодельноепредставлениезадачи

Концептуальноеметамодельное(КММ) представлениезадачи определимв виде кортежа:

Р= ,С,1>, (1.1)

где;

 - проблемнаяситуация, являющаясяисходным посыломдля построенияКММ задачнойсистемы;

Z- определяетцели "неудовлетвореннойпотребности",в результатекоторой порождаетсяпроблемнаяситуация;

С -определяетусловия достиженияцели;

I - определяетисходную информацию,в зависимостиот которойцель порождаетразличныерешения (R).

В качествеусловий определимследующийнеобходимыйи достаточныйнабор компонент:

- метод решения(М);

- алгоритм (А);

- программу(Р);

- оценку адекватности,релевантности(_ад).

Кортеж целейтогда запишетсяв следующемвиде:

Z= , А,Р, _ад>. (1.2)

Исходная информациявключает всебя данные(D),необходимыедля решениязадачи, и знания(К) опредметнойобласти задачи:

I= ,K> (1.3)

С другой стороныиспользуемуюинформациюможно рассматриватькак совокупностьинформациио целях и условияхзадачи:

I^*= Z,I^M,I^A,I^P,I^>. (1.4)

Адекватностьрешения задачипредставимкак совокупностьпоказателейкачества иэффективности:

_ад = Г (Qw,Ef). (1.5)

Развитие задачи(Тр) связано сзаполнениемзадачной оболочкив форме КММконкретнымисведениями,определяемымирешением задачи.

Как известно,возможны следующиепостановкизадач:

1) Рутинная задача,когда кортеж(1.1) и (1.2) заданыполностью(Т_P-Р_R).

2) Творческаязадача уровняпрограммы(Тр-Рр), когдазадано все,кроме программнойреализации(Р) , и требуетсяопределитьР, осуществляятем самым переходк рутиннойзадаче, и результат(R).

3) Творческаязадача уровняалгоритма(Т_Р-Р_А), т.е.неизвестеналгоритм (А) иего программнаяреализация.

4) Творческаязадача уровняметода решения(Тр-Рм), когданеизвестныметод, алгоритми программа.

Схему решениязадачи в общемвиде представленана рис. 1.1, а логическая схема решения задачи в виде схемы алгоритмана рис. 1.2.

В качестве базовых процедуррешения выделимследующиетехнологическиепроцедуры:

- генерациирешений;

- анализ полученныхрешений;

- формированиепарадигмырешений;

- упорядочениеальтернативныхрешений ;

- выбор удовлетворительногорезультата;

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

R = F:{(Z_R/C(R/I_R)}, (1.6)

т. е. решениеопределяется,исходя из заданныхцелей и условийдостиженияцелей.

Системнаязадача Р

P_M

P_A

P_P

P_R

Р

Исходнаязадача

Задачаметода

Задачаалгоритма

Задачапрограммы

Задачарезультата

нет

нет

нет

нет

нет

нет

нет

нет

да

да

да

да

да

да

да

да

ис. 1.1 Схемарешения системнойзадачи

Рис.1.2 Логическаясхема (алгоритм)решения системнойзадачи

1.2. Форма организацииучебного процессаи базовые компонентыпредметнойобласти

В соответствиис принятойсистемой правилорганизацииучебногопроцесса каждыйфакультет(кафедра) ВУЗасамостоятельноформируетсебе расписаниезанятий, согласовываяс другимифакультетами(кафедрами)вопросы совместногоиспользованияаудиторногофонда и трудапрофессорско-преподавательскогосостава.

Ниже рассмотреныбазовые объекты,входящие всистему организацииучебного процесса.

1.2.1. Аудиторныйфонд

Аудиторныйфонд (АФ) - каталогпомещенийВУЗа, в которыхпланируетсяпроведениезанятий.

Каждое помещение (аудитория)характеризуетсядвумя основнымипараметрами:

АФ = , (1.7)

где ;

ФНА - определяетфункциональное(занятийное)назначение аудитории;

ЕВ - характеризуетединовременнуювместимость, определяющуюнабор требованийэкологическогои эргономическогохарактера.

По своемуфункциональномуназначениюразличают тритипа помещений:

- аудиториидля проведениялекций;

- аудиториидля проведенияпрактическихзанятий (семинаров);

- аудиториидля проведениялабораторныхзанятий.

1.2.2. Контингентучащихся

Контингентучащихся (КУ)- иерархическаядревовиднаяструктураорганизацииучебных формирований(УФ) (рис. 1.3). В целяхминимизироватьвозможностьпотери общностиданных о КУ определимследующиебазовые единицы:

- курс;

- поток;

- временныйпоток;

- учебная группа.

Курс - условноеобозначениевершины дерева,в котороевключаютсявсё учебныегруппы, сформированныев определенныйгод.

Поток - объединениеодной или несколькихучебных групподного годаформирования.

Временныйпоток - поток,сформированныйна период, равныйодному семестру, или сформированныйдля проведения специальныхучебных занятий.

Учебная группа- самостоятельнаянеделимаяучебная формация.

К

урс

Поток 1

Поток 1.1

Учебная группаI.I.I

Поток 1.2

Учебная группа1.2.1

Учебная группа1.2.2

…………………………………

Рис. 1.3. ОрганизацияКУ

1.2.3 Профессорско-преподавательскийсостав и дисциплины

Профессорско-преподавательскийсостав (ППС)объединяетлюдей (преподавателей),ответственныхза проведениезанятий.

Преподавателяхарактеризуютдве составляющие:

ППС = , (1.8)

где

З - определяетзвание (должность)преподавателя;

ТНД - определяеттематическуюнаправленностьдисциплины(Д), которую"читает"преподаватель:

Д , (1.9)

Должностьпреподавателяопределяетформальнуюсистему приоритетов:

- профессор;

- старшийпреподаватель;

- преподаватель;

- совместитель;

- аспирант.

ТНД может иметьтакже и сложнуюструктуру,объединяя всебе набордисциплин сразными тематиками:

ТНД*= {ТНД₁, ... ,ТНД_N}. (1.10)

1.2.4. Комбинированныйучебный план

Комбинированныйучебный план(КУП) - таблица,в которой каждомуучебномуформированиюпоставленыв соответствиеопределенныедисциплиныс указаниемучебной нагрузки,выраженнойв академическихчасах в неделюдля каждоговида занятия,и преподавателя,ответственногоза проведениезанятия.

КУП формируетсяиз двух составляющих:

КУП = (1.11)

где

УП – учебныйплан кафедры;

ПН – план нагрузкипреподавателейкафедры,

или

КУП = , (1.12)

где

УФ - учебноеформирование;

С - семестр;

Д - дисциплина;

КЧЛК - количественныйпоказатель,определяющийакадемические

часыв неделю длялекций;

КЧЛР - количественныйпоказатель,определяющийакадемические

часы в неделюдля лабораторныхзанятий;

КЧПР - количественныйпоказатель,определяющийакадемические

часыв неделю дляпрактическихзанятий.

Семестрхарактеризуетсяколичествомнедель:

С=. (1.13)

По значениюТНД дисциплинывыбираетсяпреподаватель.ПараметрыКЧЛК, КЧЛР, КЧПРформируютабстрактноепонятие количествочасов нагрузки(КЧН).

1.2.5. Расписаниезанятий

Расписаниезанятий (РЭ) -таблица, в которойуказаны местои время проведениязанятий.

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

Формальнаяпостановказадачи составлениярасписанияпредставленана рис. 1.4.

На рис. 1.5. отображенасистема отношениймежду объектамипроекта "Учебноерасписание".

Учебные формирования

Кафедра

П

Р

Е

П

О

Д

А

В

А

Т

Е

Л

И

Д

И

С

Ц

И

П

Л

И

Н

Ы

Комбинированныйучебный план

Планнагрузки

Учебныйплан

Расписание

Рис 1.4 Постановкаисходной задачисоставлениярасписания

Рис. 1.4 Ключевыеабстракции,характеризующиесловарь предметнойобласти

2. Методологиярешения задачи

2.1 Модель представлениязнаний дляпроекта «Учебноерасписание»

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

Наданном этапевведем понятиеархитектуры для обработкии представлениязнаний (АОЗ). АОЗ имеет двесоставляющих:внутреннююи внешнюю. Внешняясоставляющаянапрямую связана с модельюпредставления знаний, а внутренняяотождествляетсяс конкретнойаппаратной(,или программной,)архитектуройэлектроннойвычислительноймашины (ЭВМ),на платформекоторой создаетсяпрограммныйпродукт. Естественно,что указанныесоставляющиедолжны иметькак можно болеепростые связи,т.е. каждомусемантическомуэлементу моделипредставлениязнаний должнабыть сопоставленаестественнаяаппаратная(программная)реализация.

В ЭВМ "неймановскоготипа" для того,чтобы выполнитьнекоторуюобработкуданных, необходимонаписать алгоритмобработки ввиде программыи ввести ее вкомпьютер. Еслипопытатьсяподобным методомразработатьсистему обработкизнаний, то неизбежновозникаютдве проблемы.Первая связанасо слияниемзнаний с механизмомлогическоговывода. Онасостоит в том,что знания обобъекте и механизмлогическоговывода, использующийэти знания, недолжны отличатьсядруг от друга,т.е. их следуетпредставлятьв виде цельнойпроцедуры.Вторая проблемаобуславливаетсясложностьюобновлениязнаний, когдапополнение,уничтожениеили изменениезнаний, ломающихсяобъекта, означаетизменениепрограммы, итрудно точно определить, до какой частипрограммыраспространяетсяэто влияние.Эти проблемыможно разрешить,если разработатьсистему с модульнымпредставлениемзнаний.

Наиболее частоиспользуемыемодели представления знаний длярешения задач искусственного интеллекта (ИИ) приведены в табл. 1.1.

Таблица 1.1

Описательные формализмы	Иерархия	Наследование	Модульность
Семантическиесети	+	-	-
Фреймоваямодель	+	+	-
Продукционнаямодель	+	-	+
ООмодель	+	+	+

Для проекта"Учебное расписание"был выбранобъектно-ориентированный(ОО) формализмпредставлениязнаний, которыйможно трактоватькак уточнениеформализмафреймов (в формализмефреймов неделается различиямежду видомотношенийкласс/подкласси видом отношенийкласс/конкретныйэкземпляр, вто время какв ОО формализмеэти два видаотношенийявляютсяортогональными).

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

1. Идентификацияклассов и объектовданного уровняабстракции;

2. Идентификациясемантикиклассов и объектов;

3. Идентификациясвязей междуклассами иобъектами;

4. Идентификацияклассов и объектов(программнаяреализация).

2.1.1.Объектно-ориентированнаямодель представлениязнаний

Концептуальнойосновойобъектно-ориентированногостиля представлениясистем являетсяподход, которомусоответствуютчетыре главныхэлемента:

- абстрагирование;

- ограничениедоступа;

- модульность;

- иерархия.

Под абстрагированиемпонимают выделениесущественныххарактеристик(атрибутов)объектов (определениеабстрактноготипа данных),которые отличаютего от всехдругих видовобъектов и,таким образом,четко определяютособенностиданного объектас точки зрениядальнейшегорассмотренияи анализа.

Наданном этапевведем понятиеинкапсуляциикак объединенияатрибутовобъектов ифункций управленияобъектами вединую описательнуюструктуру -класс. Такимобразом, понятиекласс определяетмножествообъектов, связанныхобщностьюструктуры иповедения.

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

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

- общедоступная;

- защищенная;

- обособленная(скрытая).

К = , (2.1)

где

А – атрибутыкласса;

Ф – функции(методы) класса.

Всвою очередь:

А=А,З_А,С_А>, (2.2),

а

Ф = Ф, З_Ф,О_Ф>, (2.3)

где

О_[А,Ф] - общедоступныеэлементы класса;

З_[А,Ф] - защищенныеэлементы класса;

С_[А,Ф] - скрытыеэлементы класса.

В общедоступнойчасти интерфейсакласса декларируютсяопределения,"видимые" длявсех объектов-пользователейданного класса.

В защищеннойчасти интерфейсакласса даютсяопределения,"видимые"только дляобъектов,относящихсяк подклассамданного класса.

В обособленнойчасти интерфейсакласса декларируютсяопределения,"скрытые" дляобъектов всехдругих классов.

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

Модульностьявляется свойствомсистемы, котороесвязано свозможностьюдекомпозицииее на ряд тесносвязанныхмодулей (областей).

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

- наследование;

- использование;

- метаклассы.

Наследование– отношениемежду классами,когда одинкласс повторяет(включает всебя) структуруи поведениедругого (простоенаследование)или других(множественноенаследование)классов. Класс,структура иповедениекоторогонаследуются,называютсясуперклассом(класс-предок),а производныйот суперклассакласс навиваетсяподклассом(класс-наследник).Очевидно, чтолучшим способом сохранения единства подходак проекту ирешения проблемыизбыточностиописания, являетсясоздание длякаждого видаданных отдельногокласса, чтопозволит защититьданные в каждомклассе и увязатьих с выполняемымиоперациями.

Отношениеиспользования связано собъявлениемобщности(дружественности)классов, котораяозначает возможностьдоступа кзащищеннымэлементамкласса объектамдругих классов.

Метакласс(абстрактныйкласс) являетсяклассом, объектыкоторого самиявляются классами.

2.1.2. Блочнаяальтернативнаясеть

2.1.2.1. Элементарныйблок альтернатив

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

Пусть существуетобъект R(R~^О),который будемназывать решением.При этом существуетнесколькопоказателей(атрибутов),характеризующихобъект:

П = (П₁,...,П_,...,П_N) (2.4)

Каждый атрибутможет приниматькачественныеи количественныезначения, которыеопределяютсякак параметры(значения атрибута).Эти параметрымогут бытьпостояннымии переменнымиво времени:

П=(^₁,…, ^_j,…, ^_I),

или (2.5)

А=(^₁,…, ^_j,…, ^_I)

Схема атрибутивногопредставлениярешения сложнойзадачи приведенана рис. 2.1.

Решение сложнойзадачи в соответствиио таким представлениембудет определятьсякак прямоепроизведениеего атрибутов:

R (А₁... А... А_N). (2.6)

С учетом того,что каждыйатрибут определяетсямножествомего значений,решение будетзадаватьсяматрицей атрибутов:

А

₁= (₁₁, …,_1j,…, _1m1)

…………………………..

А = (_1,…, _j,…, _m) (2.7)

……………………………

A_N= (_N1,…, _Nj,…, _NmN)

Естественно,что значенияатрибутов, ав ряде случаеви сами атрибутымогут выступатьв качествеальтернативныххарактеристикили величин-параметров.В рассмотрениеможно включитьнекоторый

атрибут Аи набор егоальтернативныхзначений _j,если сам атрибути его значениязаданы. Следуетотметить, чтозначения _jатрибута А_могут иметьнепрерывныйили дискретныйхарактер. Этомогут бытьчисловые величиныили некоторыепонятия. Отношениеатрибут-значениеможно представитьв виде первичногодерева иерархии(рис. 2.2).

Здесь атрибутА_выступает вкачестве корневойвершины, а значения_j(j=l,... ,N)определяютсякак альтернативные,так как предполагается,что в любоймомент времениатрибут А_может приниматьодно и толькоодно значение_j.

Элементарныйблок альтернатив(БА) можно представитькак поименованную.структуруорганизацииданных, т.е. класс,определяющиймножествообъектов-альтернатив(рис. 2.3).

В подобнойструктуредолжна бытьреализованафункция выбораальтернативы(ФВА) при условиисуществованиязначения (кода)альтернативы.Обычно подобнаяфункция содержитв своем теледве составляющие:рекурсивный(R) и транзитный(Т) блоки. Рекурсивныйблок используетсятогда, когданеобходиморешить задачупоиска альтернативногозначения намассиве альтернатив,т. е. Организоватьциклическийпроцесс. Транзитныйблок используетсяв тех случаях,когда ни однаиз альтернативв общем решениине участвует,а в частномслучае можетвыступать какограничительдля рекурсивногоперебораальтернатив.

Решение- R

_1

_о

_m

Рис. 2.1 Атрибутивноепредставлениерешения сложнойзадачи

А_

Рис. 2.2 Отношениеатрибут-значениев виде первичногодерева иерархии

вход

А_

R

T

якорь

выход

Рис. 2.3. Элементарныйблок альтернатив

ИнкапсулируяБА с ФБА, получимзамкнутуюсистему работыс данными попоиску и выборкеальтернатив(рис. 2.4).

Тогда входноймассив данныхА_^хможно интерпретироватькак набор входныхаргументовдля ФВА, а выходноймассив А_^усопоставитьс конкретнымобъектом-альтернативой,атрибутивнымописаниемкоторого являетсяА_^у.

Альтернативымогут формироватьсяв соответствиис теми или инымидисциплинамиупорядоченияв ФВА, в зависимостиот которыхопределяютсястратегиипоиска альтернативы(эвристическийпоиск), т. е. ФВАможет бытьсвязана с базойзнаний, содержащейправила длявыбора альтернатив.

Формальнореализациюмеханизмаэвристическогопоиска представимв виде следующейпоследовательности:

Этап1. Выбор из множествавозможныхдействий некоторогодействия:

1)с учетом соответствияцели:

- уменьшениенекоторогонежелательногоразличия,

- непосредственноерешение тойили иной подзадачи;

2) сучетом опыта:

- повторениепрошлого,

-обнаружениеключевогодействия;

3) сучетом необходимыхусловий:

-решение, обусловленноеанализом ситуации,

-исключениенеосуществимоговарианта;

4) сучетом фактораслучайности:

• предпочтениеотдаетсяразнообразию.

Этап 2. Осуществлениевыбранногодействия иизменениетекущей ситуации.

Этап3. Оценка ситуации:

1) поаналогии:

-известна самазадача,

-известна подзадача;

2) повеличине расстояниядо цели:

-расстояниемежду двумяситуациями,

-количествоусилий, затрачиваемоена поиск;

3) поматематическомукритерию:

- составлениеперечня необходимыхи/или достаточныхдля полученияданного решенияхарактеристик,

-численнаяоценочнаяфункция,

- верхние и нижниеграницы,

- суммастоимостей,выбранныхподходящимспособом;

4) по ожидаемомувыигрышу (критерий,связанный спрошлым опытом):

- простота ситуации,

-коэффициентрасширенияпоиска,

- любойдругой критерий(сложностьзадачи, затрачиваемоена

ее решениевремя и т.д.).

Этап4. Исключениебесполезныхситуации.

Этап 5. Еслидостигнутаконечная цель- конец, иначевыбор новойисходной ситуациии повторитьпоиск:

1)движение тольковперед:

- систематическоеразвитие последнейпорожденнойситуации;

2)выполнениедействий параллельно:

- поочередноевыполнениевсех действий;

3) выбор в качествеисходной самоймногообещающейситуации:

- вотношенииоценочнойфункции,

- в отношениинезначительногочисла входящихв нее действий;

4)компромиссмежду:

-глубиной поиска,

- оценкойситуации.

2.1.2.2. СтруктурыБАС

Блок, представленныйна рис. 2.4., являетсябазовым дляпостроениясетей, называемыхблочнымиальтернативнымисетями (БАС).Возможныеструктуры БАСопределяютсяиерархиейотношений междуклассамиобъектов-альтернатив.

Одной из возможныхконфигурацийможет бытьпоследовательнаяБАС. Пусть заданкортеж атрибутов{А_: =1,N}, на основекоторого формируетсяБАС с последовательнойстратегией,вид которойпредставленна рис. 2.5.

Замкнутыйаналог последовательнойБАС представленна рис. 2.6.

ФБА

ВходВыход

Рис. 2.4. ИнкапсуляцияБА и ФВА в классобъектов-альтернатив

^БА₁

^БА_N

^БА_

Рис. 2.5. ПоследовательнаяразомкнутаяБАС

^БА₁

^БА_N

^БА_

Блокобратной связи

Рис.2.6. Последовательнаязамкнутая БАС

2.2. Методыформированиярешения

2.2.1. Алгоритмынавигации наБАС

Приработе с БАСвозможны следующиеварианты навигации:

- последовательная;

- параллельная;

- смешанная.

Для последовательнойсети последовательныйалгоритм навигацииможет бытьреализовандвумя базовымиспособами.

1. Прохождениесети реализуется последовательно, начиная с первого a₁ и кончаяпоследним а_Nблоками. Алгоритмобращаетсяк блоку a₁,просматриваетего содержимоеи через транзитныевершины передаетрезультат. Далее переходитк следующемублоку. В итогеобразуетсянекоторыйвершинныймаршрут R₁=(₁j,...,_j,..,_Nj),который ипредставляетданные о результатерешения. Есличастные решениясовместны, тоони оцениваютсяпо критериям-адекватности. Если какое-торешение несовместно,то выявляетсяпричина несовместимостии ищется новоерешение.

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

2.2.2. Маршруты наБАС

В БАС используетсявершинный типмаршрутов. Сточки зрениясети маршрутыподразделяютсяна внутриблоковыеи сетевые.Последние,в свою очередь,формируютсяиз внутриблоковыхи межблоковых.

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

Следует отметить,что в элементарномблоке имеетместо три видавершин:

а) вершины первогоранга: вход ивыход;

б) вершины второгоранга: значенияатрибутов;

в) вспомогательныевершины: рекурсияи транзит.

В зависимостиот содержаниямаршрута иметода егоформированиябудем различатьациклическиеи циклическиемаршруты.

Ациклическиймаршрут (АМ¹)формируетсякак последовательность

вершин совместнос отношениеммежду вершинами:

AMⁱ: (Aⁱ r_ij u_ij), (2.8)

где

Аⁱ - атрибут;

r_ij -определяетотношение междуатрибутом ивершиной-значениемij;

_ij - значениеатрибута Аⁱ.

Полноепредставлениевнутриблоковогомаршрута посхеме исток-стокбудет представлятьсобой объединение:

AMⁱ: (Аⁱ r_ij_ij)U (_ijr_ji A*_i), (2.9)

или в общемвиде для вершин-альтернативполучим вершинныйациклическиймаршрут:

AM¹:(Аⁱ,_ij,A*_i). (2.10)

Аналогичнодля маршрута,проходящегочерез транзитнуювершину:

АMⁱ_T:(Aⁱ,r_T,A*_i), (2.11)

что эквивалентнозаписи

AMⁱ_T:(Aⁱ,T,A*_i). (2.12)

В циклическоммаршруте (ЦМⁱ)используетвершина с индексомR:

ЦМⁱ_*:(Aⁱ,_ij,A*_I) R_q, q = 1,2, …, Q (2.13)

где - определяетповтор маршрутов.

Для циклическихмаршрутоввозможно нескольковариантовреализации:

- поиск однойединственнойальтернативы;

- использованиедвух альтернативвместе;

- поиск с множествомальтернатив.

В первом случаеможет реализоватьсяq-кратноепрохождениепо внутриблоковомумаршруту, причемзначение qопределяетсяколичествомциклов, прикотором находитсятребуемоезначение оси,

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

ЦМⁱ_**:(Aⁱ,(_ij,_q1),A*_I)R_q, q = 1,2, …, Q (2.14)

Придальнейшемувеличенииколичестваописании альтернативgjлучим циклическиймаршрут с множествомальтернатив:

ЦМⁱ_**:(Aⁱ,{_ij},A*_I) R_q, q = 1,2, …, Q (2.15)

Межблоковыеи сетевые маршрутыформируютсяна основе склеиваниявнутриблоковых.Для этих целейиспользуютсяспециальныеалгоритмы,которые осуществляюткак формированиесамого маршрута,так и склеиваниевнутриблоковыхв единый сетевой(рис. 2.7):

М_N~ MN_,= U MБi, (2.16)

где

MN_- сетевой маршрут;

MБi -внутриблоковыймаршрут.

При таком алгоритменавигации путемсклеиваниябудет полученмаршрут:

MN_ = R (R_1,,…, R_i,…, R_N), (2.17)

таким образомполучаетсяпоследовательныйалгоритм навигациис одной стороныи последовательнаястратегиясклеиванияс другой.

В другомслучае имеетместо следущаякартина, представленнаяна рис. 2.8.

Для каждогоблока альтернативопределяетсясвой алгоритмвыбора альтернативы.Алгоритм параллельнойнавигации, всвою очередь,реализуетфункции координации,которые взаимодействуютс каждым блоковымалгоритмом.Работа осуществляетсяпараллельно.Алгоритм координациипередает исходныеданные (I^O)в локальныеалгоритмы изапускает ихв работу. Каждыйив локальныхалгоритмовформируетвнутриблоковыймаршрут исоответствующийрезультат (R).Далее формируетсяпоследовательность(R¹₁, ..., Rⁱ₁,..., R^N₁)=R_l несвязанныхмежду собойрешений. Послеэтого решаетсязадача склеиваниячастных решенийв общее. Даннаяпроцедура можетпротекатьпо двум направлениям:

1)формированиеобщего решенияна уровнекоординирующегоалгоритма;анализ, оценка,принятие решениядля дальнейшихдействий;

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

Получив парадигмуобщих решений,в соответствиис определеннымикритериямивыбираетсянаилучшее изних.

2.2.3. Оценка результатоврешения задачина БАС

Если на основелокальныхрешений сформироватьновую сетьболее высокогоуровня абстракции,то на ее основеможно выделитьсеть вторичныхрешений. Наэтой сети сучетом локальныхрешений формируетсяновая парадигмарешений:

N_R= (m x n) => П{R} (2.18)

Ввиду того, чтоне все решенияудовлетворяютисходной задаче,необходимовыбрать те,которые удовлетворяютцелям и условиямзадачи. Дляанализа, оценкии отбора решенийиспользуютсясоответствующиекритерии иэвристики(_АД).

АНПС

R₁R_iR_N

БА₁

БА_i

БА_N

Рис. 2.7. Формированиесетевого маршрутас помощьюпоследовательногоалгоритманавигации насети

Алгоритмпараллельнойнавигации

АБ₁

АБ_i

АБ_N

БА₁

БА_i

БА_N

I^O₁R¹₁I^O_iRⁱ₁I^O_NR^N₁

Рис. 2.8. Формированиесетевого маршрутас помощьюпараллельногоалгоритманавигации насети

Если этот показательзадан, то оннепосредственноиспользуетсяпри анализеи оценке решения,если нет, тодля каждогоконкретногослучая оформляетсясвоя задачаопределенияпоказателя.

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

3. РеализацияБАС на 00 системев проекте "Учебноерасписание"

3.1. Структуракласса

Учитывая спецификурешаемой задачии методы, используемыедля достижениярезультатов,определим классдля проекта"Учебное расписание"как поименованнуюструктуру,которая включаетв себя:

К = ,

и соответственно

А = А, З_А,С_А> и Ф = .

Общедоступнаяинтерфейснаячасть описанияатрибутовкласса включаетв себя декларациюпризнаковобъекта, универсальнои однозначнохарактеризующихданную абстракцию:

О_А = { а_оi}, (3.1)

где А_Оi– атрибутобъекта-экземпляракласса.

Скрытая интерфейснаячасть описанияатрибутовкласса содержитссылку на бинарныйфайл, которыйвключает в себянабор декларативныхи/или продукционныхправил, предназначенныхдля генерациии ограниченияобласти значенииобъектов-экземпляров( альтернатив)

класса:

с_а = С1, ... ,а_сi, ...А_Cn, ФБП>, (3.2)

где

а_сi, -скрытый элементданных класса;

ФБП - файл базыправил генерацииобъектов-альтернатив.

Общедоступнаяинтерфейснаячасть декларациифункций (методов)управленияобъектамикласса представляетсяследующимобразом:

О_Ф = 01,..., Фoi, ...., Фоn,ФОБП>, (3.3)

где

ФК - функция-конструкторкласса, определяющаямеханизм выделенияоперативнойпамяти дляхраненияобъекта-альтернативы(результата);

ФД – функция-деструкторкласса, определяющаямеханизм освобожденияоперативнойпамяти, выделеннойконструктором;

Фоi - общедоступныйметод управленияобъектом класса;

ФОБП - наборфункций, предназначенныхдля обработкибазы

правил (знаний).

Как минимумкортеж ФОБПвключает всебя:

ФОБП = , (3.4)

где:

ФВА - функциявыбора альтернативы;

ФДП - метод длядобавленияправила в базузнаний;

ФУП - метод дляудаления правилаиз базы знаний;

ФРП – метод дляредактированияправила в базезнаний.

Функция выбораальтернативыопределяетмеханизмыпостроениясинтаксисаправила, выборкииз множестваи оценки результатовна основе критериев-адекватности.

Функциидобавления/удаления/редактированияправил содержатв своем теледва основныхблока: блокдобавления/удаления/редактированияправила и блокдобавления/удаления/редактированияальтернативы.

3.2.Правила представлениязнаний

Правила, представленныев ФБП делятсяна две основныегруппы:

декларативныеи продукционные.

Декларативныеправила (ДП)определяютв базе знаниймножествофактов. Фактв данном случаеоднозначноотождествляетсяс конкретнымобъектом-альтернативойабстрактноготипа данных.Факт в зависимостиот количестваатрибутовобъекта классаможет иметьпростую илисложную (составную)структуру.

Продукционныеправила (правилаЕСЛИ-ТО) позволяютявным образомзадавать критериинеобходимостии достаточностиколичествавходных параметровдля идентификацииобъекта-альтернативы.Также в телеправил данноготипа могутсодержатьсязаписи математическихзаконов описаниямножестваобъектов.

Вне зависимостиот типа, правилаимеют два видапредставления:текстовый идвоичный. Возможныесвязи междутекстовым идвоичнымпредставлениемправил в базезнаний представлены на рис. 3.1.

Одинарнойлинией на рис.3.1. показана связьтипа «один кодному», а двойной– связь типа«один к многим».

Связь типа«один к многим»реализуетсяправилом, имеющимв своем телеследующийфункциональныйэлемент:

FOR = 1,…, Ao_i,…, Ao_n),O>, (3.5)

где

В - определяетначальноезначение счетчика;

Е - определяетконечное значениесчетчика;

S - определяетшаг приращениязначения счетчика;

F(С, Ao₁,…, Ao_i,…, Ao_n)- определяетматематическуюбазу для генерированияобъекта-альтернативы;

С - текущее значениесчетчика;

Ao_i - атрибут объекта;

О – определяетрежим отображенияобъекта класса:О=base – отображениев файл БД, О=memory– отображениев оперативнуюпамять.

Текстовоепредставление

ИМЯ_КЛАССА.КВА

Двоичноепредставление

ИМЯ_КЛАССА.DBF

Декларативноеправило 1

Объект-альтернатива1

Продукционноеправило 2

Продукционноеправило 3

………………………

Объект-альтернатива2

Объект-альтернатива3.1

Объект-альтернатива3.2

………………………………

Объект-альтернатива3.i

……………………………..

Объект-альтернатива3.n

Рис. 3.1. Связи междутекстовым идвоичнымпредставлениемправил

При 0=baseобъемы-альтернативысобираютсяв файл базыданных (DBF-файл),где хранитсяв упакованнойвиде. Для файловподобного типаопределяютсястандартныеоперациииндексированияи фильтрациизаписей, чтоупрощает иубыстряетмеханизм поискаи выборки информациииз БД.

3.3. Фрагмент решениязадачи "Формированиеучебного расписания"

Формальноепредставлениеалгоритмарешения задачиформированиярасписанияотображенона рио.З.2.

Из рисункавидно, что базовымэлементом всистеме составлениярасписанияявляется учебныйблок занятий(класс "Учебныйблок" на рис.1.4.).

3.3.1. Класс "Учебныйблок"

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

Структура блоказанятий представленав виде матрицына рис. 3.3.

Учебный блоксоставляютдве компоненты:

- количествочасов в блоке(КЧБ) определяетколичествочасов, котороеблок занимаетв сетке расписанияодного учебногодня (одна строкаматрицы соответствуетдвум часамзанятий);

• деление блока(Д) распределяетзанятие понеделям семестра.

Значения КЧБи Д рассчитываютсяна основанииданных, изкомбинированногоучебного плана. Связующимзвеном здесьявляемся абстракция"Количествочасов нагрузки"(КЧН), котораяобъединяеттри класса:

• количествочасов лекционныхзанятий в неделю(КЧЛК);

• количествочасов лабораторныхзанятий в неделю(КЧЛР);

• количествочасов практическихзанятий в неделю(КЧПР).

БАС формированияблоков

Механизмыопределениямаксимальногоколичествагрупп средипотоков ипреподавателей

БАСсопоставленияблоков количествугрупп

Сочетания:количествогрупп –

блоки

Сочетания:поток - блоки

Сопоставлениекаждому преподавателюнаборов-альтернативсочетанийблоков занятийв зависимостиот количествагрупп, обучаемыхпреподавателем

Сопоставлениекаждому потокунаборов-альтернативсочетанийблоков занятийв зависимостиот количествагрупп, входящихв поток

Сочетания:преподаватель - блоки

Расписаниена учебнойчасти

Преобразованиев блочноепредставление

Правилакомпоновкиблоков в расписание

Расписаниезанятий

Рис. 3.2 Общаясхема решениязадачи сопоставлениярасписаниязанятий методамиБАС на ООС наоснованиипродукционноймодели

*

* * *

*

КЧБ

Д

Рис. 3.3. Структура блока занятий

Обозначимколичествонедель в семестрекак КНС. Тогда, суммарноеколичествочасов занятийэа семестр (ч)определяетсяпроизведениемКНС и КЧН:

ч = КНС*КЧН, (3.6)

или

ч = (КНС/Д)*КЧБ. (3.7)

Из чего следует:

КЧН = КЧБ/Д. (3.8)

Декларативныеправила, входящие в классы КЧЛК, КЧЛР и КЧПР

описываютследующиенаборы фактов:

КЧЛК = {0, 1.0, 1.5, 2.0}, (3.9)

КЧЛР = {0, 1.0, 2.0}, (3.10)

КЧПР = {О, 1.0, 2.0}, (3.11)

Объединяямножества вмета-класс,получим:

КЧН = {0, 1.0, 1.5, 2.03}. (3.12)

Используяформулу 3.8, определим область значений объектов-экземпляровкласса КЧБ икласса Д:

КЧБ = {2, 4, 6}, (3.13)

Д = {2, 3, 4}, (3.14)

Класс «Учебныйблок» являетсянаследникомкласса «Блокзанятия».

3.3.2. Класс «Блокзанятия»

Столбец матрицы,представленнойна рис.3.3., определяетчасть семестра,которую назовёмдолей. Доляможет бытьзанята (занятиепроводится– столбец матрицызакрашен) илисвободна.

Свободные долиописываютсвободные часызанятий в неделю(КЧС).

Декларативноеправило генерациипараметра КЧСимеет вид:

ПРАВИЛО1.

блок.КЧС= FOR (1, блок.Д-1,RETURN(C), base).

Объединяя КЧСс данными класса"Учебный блок",сформируемкласс "Блокзанятия".. Количествосвободных (КСД)и занятых (КЗД)долей в блокезанятия определимчерез его параметры:

КСД = КЧС/КЧН. (3.15)

Используяформулу 3.8, получим;

КСД = Д * (КЧС / КЧБ). (3.16)

Очевидно, что:

КСД + КЗД = Д. (3.17)

Следовательно:

КЗД = Д * (1 - КЧС/КЧБ). (3.18)

На рис. 3.4. приведенаструктура БАСс алгоритмаминавигации длякласса "Блокзанятий". Врезультатеработы алгоритма,ФВА класса"Блок занятий"был полученнабор решений,образующихблок альтернатив,представленныйна рис. 3.5.

ФВА (учебныйкурс)

ФВА (блокзанятий)

Рис.3.4. Схема БАСформированияобъекта «Блокзанятий»

ФВА (выборкаблоков)

Рис. 3.5. ВАС формированияобъекта класса«Блоки занятий»

3.3.3. Класс «Блокизанятий».

Уравнения 3.16и 3.18 необходимыдля понятиясовместимостиблоков занятий.

Два блока Бiи Б2 совместимы,если:

KЧH1= КЧН2, КЧБ1= КЧБ2 и КЗД1

Понятие совместимостиблоков используетсяв правилахслияния несколькихблоков в одинобъект класса"Блоки занятий":

ПРАВИЛО 1.

ЕСЛИ стратегия.тип= общая

И блок(&А).КЧН= блок(&Б).КЧН

И блок (&A).КЧБ= блок (&Б).КЧБ

И блок(&А).КЗД

ПРАВИЛО 2.

ЕСЛИ стратегия.тип= общая

B блок(&А).КЧН== блок(&Б) .КЧН

И блок (&A).КЧБ = блок(&Б).КЧБ

И блок(&А). КCД>= блок(&Б). КЗДТО блок(&C) = блок(&A)U блоков(&Б).

Класс "Блокизанятий" объединяетабстрактныепотоки, которыехарактеризуютсяпараметром"Количествогрупп в потоке"(КГ), и оптимальнуюсовокупностьблоков.

Схема алгоритмагенерацииобъектов класса"Блоки занятий"отображенана рис. 3.6.

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

Ptr - указательна текущийобъект в опискеальтернативныхблоков занятий;

AltList - списокблоков занятий,определяющихв совокупности одну альтернативудля текущегоколичествагрупп;

Len(AltList)- длина спискаAltList.

Ptr=1

Взятьблок по указателю;сохранитьстарое значениесписка блоковв альтернативеРассчитатьКЧН_Б,КЗД; СохранитьКГ, КЧН_Б

Поместитьблок в списокблоков в альтернативе;КГ=КГ-КЗД

Включитьальтернативув список альтернативдля текущегоКГ

ДА

Ptr+1

НЕТ

ДА

НЕТ

ДА

НЕТ

Ptr+1

Восстановитьальтернативу

ДА

ДА

НЕТ

Рис3.6. Схема алгоритмагенерацииобъектов класса"Блоки занятий"

Список использованнойлитературы

Буч Г., Объектно-ориентированноепроектирована.С примерамиприменения.М., Конкорт, 1992.

Анамия М., ТанакаЮ., АрхитектураЭВМ и искусственныйинтеллект.М., Мир, 1993.

Лорьер Ж. Л., Системы искусственногоинтеллекта. М., Мир,

1991.

Искусственныйинтеллект.Применениев интегрированныхпроизводственныхсистемах. М.,Машиностроение,1991.

Малпас Дж.,Реляционныйязык Прологи его применение.М., Наука, 1990.

Рассохин Д., ОтС к C++. М., Эдель,1993.

Нечаев В.В.,Лекционныематериалы потеории творческойдеятельности.1996.