- ограничение доступа;
- модульность;
- иерархия.
Под абстрагированием понимают выделение существенных характеристик (атрибутов) объектов (определение абстрактного типа данных), которые отличают его от всех других видов объектов и, таким образом, четко определяют особенности данного объекта с точки зрения дальнейшего рассмотрения и анализа.
На данном этапе введем понятие инкапсуляции как объединения атрибутов объектов и функций управления объектами в единую описательную структуру - класс. Таким образом, понятие класс определяет множество объектов, связанных общностью структуры и поведения.
Следует разделять внутреннее и внешнее проявление класса. Интерфейсная часть описания класса соответствует его внешнему проявлению, подчеркивает его абстрактность, но скрывает его структуру и особенности поведения. Реализация класса составляет его внутреннее проявление и определяет особенности поведения, т.е. в данной части раскрывается реализация тех операций, которые перечислены в интерфейсной части описания.
Интерфейсная часть класса состоит из перечня действий, который допускает описание, других классов, констант, переменных и других особенностей, необходимых для полного определения данной абстракции. Интерфейсная часть описания класса разделена на три составные части:
- общедоступная;
- защищенная;
- обособленная (скрытая).
К = , (2.1)
где
А – атрибуты класса;
Ф – функции (методы) класса.
В свою очередь:
А =, (2.2),
а
Ф = , (2.3)
где
О[А,Ф]- общедоступные элементы класса;
З[А,Ф]- защищенные элементы класса;
С[А,Ф]- скрытые элементы класса.
В общедоступной части интерфейса класса декларируются определения, "видимые" для всех объектов-пользователей данного класса.
В защищенной части интерфейса класса даются определения, "видимые" только для объектов, относящихся к подклассам данного класса.
В обособленной части интерфейса класса декларируются определения, "скрытые" для объектов всех других классов.
Созданию абстракции объекта предшествуют решения о способе ее реализации. Выбранный способ реализации должен быть скрыт и защищен для большинства объектов, обращающихся к данной абстракции. Ограничение доступа определяет процесс защиты отдельных элементов объекта, не затрагивающий существенных характеристик объекта как целого.
Модульность является свойством системы, которое связано с возможностью декомпозиции ее на ряд тесно связанных модулей (областей).
Иерархия реализует механизм отношений между классами объектов. Отношения между классами могут быть комбинацией следующих типов иерархий;
- наследование;
- использование;
- метаклассы.
Наследование – отношение между классами, когда один класс повторяет (включает в себя) структуру и поведение другого (простое наследование) или других (множественное наследование) классов. Класс, структура и поведение которого наследуются, называются суперклассом (класс-предок), а производный от суперкласса класс навивается подклассом (класс-наследник). Очевидно, что лучшим способом сохранения единства подхода к проекту и решения проблемы избыточности описания, является создание для каждого вида данных отдельного класса, что позволит защитить данные в каждом классе и увязать их с выполняемыми операциями.
Отношение использования связано с объявлением общности (дружественности) классов, которая означает возможность доступа к защищенным элементам класса объектам других классов.
Метакласс (абстрактный класс) является классом, объекты которого сами являются классами.
2.1.2. Блочная альтернативная сеть
2.1.2.1. Элементарный блок альтернатив
Постановку задачи выбора альтернативных результатов для задач синтеза технических решений осуществим следующим образом.
Пусть существует объект R (R~SО), который будем называть решением. При этом существует несколько показателей (атрибутов), характеризующих объект:
Пd= (Пd1,...,Пdn,... ,ПdN) (2.4)
Каждый атрибут может принимать качественные и количественные значения, которые определяются как параметры (значения атрибута). Эти параметры могут быть постоянными и переменными во времени:
Пdn=(pnd1, …,pndj, …,pndI),
или (2.5)
Аdn=(and1, …,andj, …,andI)
Схема атрибутивного представления решения сложной задачи приведена на рис. 2.1.
Решение сложной задачи в соответствии о таким представлением будет определяться как прямое произведение его атрибутов:
Rd <=> (А1*...*Аn*...*АN). (2.6)
С учетом того, что каждый атрибут определяется множеством его значений, решение будет задаваться матрицей атрибутов:
А1= (a11, …,a1j, …,a1m1)
…………………………..
Аn= (an1, …,anj, …,anmn) (2.7)
……………………………
AN= (aN1, …,aNj, …,aNmN)
Естественно, что значения атрибутов, а в ряде случаев и сами атрибуты могут выступать в качестве альтернативных характеристик или величин-параметров. В рассмотрение можно включить некоторый
атрибут Аnи набор его альтернативных значенийanj, если сам атрибут и его значения заданы. Следует отметить, что значенияanjатрибута Аnмогут иметь непрерывный или дискретный характер. Это могут быть числовые величины или некоторые понятия. Отношение атрибут-значение можно представить в виде первичного дерева иерархии (рис. 2.2).
Здесь атрибут Аnвыступает в качестве корневой вершины, а значенияanj(j=l,... ,N) определяются как альтернативные, так как предполагается, что в любой момент времени атрибут Аnможет принимать одно и только одно значениеanj.
Элементарный блок альтернатив (БА) можно представить как поименованную .структуру организации данных, т.е. класс, определяющий множество объектов-альтернатив (рис. 2.3).
В подобной структуре должна быть реализована функция выбора альтернативы (ФВА) при условии существования значения (кода) альтернативы. Обычно подобная функция содержит в своем теле две составляющие: рекурсивный (R) и транзитный (Т) блоки. Рекурсивный блок используется тогда, когда необходимо решить задачу поиска альтернативного значения на массиве альтернатив, т. е. Организовать циклический процесс. Транзитный блок используется в тех случаях, когда ни одна из альтернатив в общем решении не участвует, а в частном случае может выступать как ограничитель для рекурсивного перебора альтернатив.
Рис. 2.1 Атрибутивное представление решения сложной задачи
Рис. 2.2 Отношение атрибут-значение в виде первичного дерева иерархии
Рис. 2.3. Элементарный блок альтернатив
Инкапсулируя БА с ФБА, получим замкнутую систему работы с данными по поиску и выборке альтернатив (рис. 2.4).
Тогда входной массив данных Аnхможно интерпретировать как набор входных аргументов для ФВА, а выходной массив Аnусопоставить с конкретным объектом-альтернативой, атрибутивным описанием которого является Аnу.
Альтернативы могут формироваться в соответствии с теми или иными дисциплинами упорядочения в ФВА, в зависимости от которых определяются стратегии поиска альтернативы (эвристический поиск), т. е. ФВА может быть связана с базой знаний, содержащей правила для выбора альтернатив.
Формально реализацию механизма эвристического поиска представим в виде следующей последовательности:
Этап 1. Выбор из множества возможных действий некоторого действия:
1) с учетом соответствия цели:
- уменьшение некоторого нежелательного различия,
- непосредственное решение той или иной подзадачи;
2) с учетом опыта:
- повторение прошлого,
- обнаружение ключевого действия;
3) с учетом необходимых условий:
- решение, обусловленное анализом ситуации,
- исключение неосуществимого варианта;
4) с учетом фактора случайности:
- предпочтение отдается разнообразию.
Этап2.Осуществление выбранного действия и изменение текущей ситуации.
Этап 3. Оценка ситуации:
1) по аналогии:
- известна сама задача,
- известна подзадача;
2) по величине расстояния до цели:
-расстояние между двумя ситуациями,
-количество усилий, затрачиваемое на поиск;
3) по математическому критерию:
- составление перечня необходимых и/или достаточных для получения данного решения характеристик,
- численная оценочная функция,
- верхние и нижние границы,
- сумма стоимостей, выбранных подходящим способом;
4) по ожидаемому выигрышу (критерий, связанный с прошлым опытом):
- простота ситуации,
- коэффициент расширения поиска,
- любой другой критерий (сложность задачи, затрачиваемое на
ее решение время и т.д.).
Этап 4. Исключение бесполезных ситуации.
Этап 5. Если достигнута конечная цель - конец, иначе выбор новой исходной ситуации и повторить поиск:
1) движение только вперед:
- систематическое развитие последней порожденной ситуации;
2) выполнение действий параллельно:
- поочередное выполнение всех действий;
3) выбор в качестве исходной самой многообещающей ситуации:
- в отношении оценочной функции,
- в отношении незначительного числа входящих в нее действий;
4) компромисс между:
- глубиной поиска,
- оценкой ситуации.
2.1.2.2. Структуры БАС
Блок, представленный на рис. 2.4., является базовым для построения сетей, называемых блочными альтернативными сетями (БАС). Возможные структуры БАС определяются иерархией отношений между классами объектов-альтернатив.
Одной из возможных конфигураций может быть последовательная БАС. Пусть задан кортеж атрибутов {Аn:n=1, N}, на основе которого формируется БАС с последовательной стратегией, вид которой представлен на рис. 2.5.
Замкнутый аналог последовательной БАС представлен на рис. 2.6.
Вход Выход
Рис. 2.4. Инкапсуляция БА и ФВА в класс объектов-альтернатив
Рис. 2.5. Последовательная разомкнутая БАС
Рис.2.6. Последовательная замкнутая БАС
2.2. Методы формирования решения
2.2.1. Алгоритмы навигации на БАС
При работе с БАС возможны следующие варианты навигации:
- последовательная;
- параллельная;
- смешанная.
Для последовательной сети последовательный алгоритм навигации может быть реализован двумя базовыми способами.
1. Прохождение сети реализуется последовательно, начиная с первогоA1и кончая последним аNблоками. Алгоритм обращается к блокуA1, просматривает его содержимое и через транзитные вершины передает результат. Далее переходит к следующему блоку. В итоге образуется некоторый вершинный маршрут Rd1=(a1j,... ,anj,.. ,aNj), который и представляет данные о результате решения. Если частные решения совместны, то они оцениваются по критериямg-адекватности. Если какое-то решение несовместно, то выявляется причина несовместимости и ищется новое решение.
2. Алгоритм обращается последовательно к каждому блоку и результат из каждого блока передается обратно в алгоритм. Массив частных решений преобразуется в маршрут, далее процедура продолжается.
2.2.2. Маршруты на БАС
В БАС используется вершинный тип маршрутов. С точки зрения сети маршруты подразделяются на внутриблоковые и сетевые. Последние, в свою очередь, формируются из внутриблоковых и межблоковых.
Внутриблоковый маршрут формируется как последовательность вершин, связанных определенным отношением г.
Следует отметить, что в элементарном блоке имеет место три вида вершин:
а) вершины первого ранга: вход и выход;
б) вершины второго ранга: значения атрибутов;
в) вспомогательные вершины: рекурсия и транзит.
В зависимости от содержания маршрута и метода его формирования будем различать ациклические и циклические маршруты.
Ациклический маршрут (АМ1) формируется как последовательность
вершин совместно с отношением между вершинами:
AMi: (Airijuij), (2.8)
где
Аi- атрибут;
rij- определяет отношение между атрибутом и вершиной-значениемaij;
aij- значение атрибута Аi.
Полное представление внутриблокового маршрута по схеме исток-сток будет представлять собой объединение:
AMi: (Аirijaij) U (aijrjiA*i), (2.9)
или в общем виде для вершин-альтернатив получим вершинный ациклический маршрут:
AM1: (Аi,aij, A*i). (2.10)
Аналогично для маршрута, проходящего через транзитную вершину:
АMiT: (Ai, rT, A*i), (2.11)
что эквивалентно записи
AMiT: (Ai, T, A*i). (2.12)
В циклическом маршруте (ЦМi) использует вершина с индексом R:
ЦМi*: (Ai,aij, A*I)oRq, q = 1,2, …, Q (2.13)
гдеo- определяет повтор маршрутов.
Для циклических маршрутов возможно несколько вариантов реализации:
- поиск одной единственной альтернативы;
- использование двух альтернатив вместе;
- поиск с множеством альтернатив.
В первом случае может реализоваться q-кратное прохождение по внутриблоковому маршруту, причем значение q определяется количеством циклов, при котором находится требуемое значение оси,
Во втором случае используются две .альтернативы, и подобно двухместному предикату формируется маршрут. Реализация такого маршрута может быть как последовательной, так и совмещенной, когда имеются сразу два описания альтернатив и в процессе поиска определяется сначала одна, а затем недостающая альтернатива. В этом случае формируется маршрут:
ЦМi**: (Ai, (aij,aq1), A*I)oRq, q = 1,2, …, Q (2.14)
При дальнейшем увеличении количества описании альтернатив gjлучим циклический маршрут с множеством альтернатив:
ЦМi**: (Ai, {aij}, A*I)oRq, q = 1,2, …, Q (2.15)
Межблоковые и сетевые маршруты формируются на основе склеивания внутриблоковых. Для этих целей используются специальные алгоритмы, которые осуществляют как формирование самого маршрута, так и склеивание внутриблоковых в единый сетевой (рис.2.7):
МN~ MNa, = U MБi, (2.16)
где
MNa- сетевой маршрут;
MБi - внутриблоковый маршрут.
При таком алгоритме навигации путем склеивания будет получен маршрут:
MNa= R <=> (R1,, …, Ri, …, RN), (2.17)
таким образом получается последовательный алгоритм навигации с одной стороны и последовательная стратегия склеивания с другой.
В другом случае имеет место следущая картина, представленная на рис. 2.8.
Для каждого блока альтернатив определяется свой алгоритм выбора альтернативы. Алгоритм параллельной навигации, в свою очередь, реализует функции координации, которые взаимодействуют с каждым блоковым алгоритмом. Работа осуществляется параллельно. Алгоритм координации передает исходные данные (IO) в локальные алгоритмы и запускает их в работу. Каждый ив локальных алгоритмов формирует внутриблоковый маршрут и соответствующий результат (R). Далее формируется последовательность (R11, ..., Ri1, ..., RN1)=Rlнесвязанных между собой решений. После этого решается задача склеивания частных решений в общее. Данная процедура может протекать по двум направлениям:
1)формирование общего решения на уровне координирующего алгоритма; анализ, оценка, принятие решения для дальнейших действий;
2) координирующий алгоритм решает задачу общего решения, одновременно выдав задание блоковым алгоритмам на формиование частных решений. При получении общих решений возможна параллельная стратегия для многоальтернативных решений.
Получив парадигму общих решений, в соответствии с определенными критериями выбирается наилучшее из них.
2.2.3. Оценка результатов решения задачи на БАС
Если на основе локальных решений сформировать новую сеть более высокого уровня абстракции, то на ее основе можно выделить сеть вторичных решений. На этой сети с учетом локальных решений формируется новая парадигма решений:
NR= (m x n) => П{R} (2.18)
Ввиду того, что не все решения удовлетворяют исходной задаче, необходимо выбрать те, которые удовлетворяют целям и условиям задачи. Для анализа, оценки и отбора решений используются соответствующие критерии и эвристики (gАД).
R1 Ri RN
Рис. 2.7. Формирование сетевого маршрута с помощью последовательного алгоритма навигации на сети
IO1R11IOiRi1IONRN1
Рис. 2.8. Формирование сетевого маршрута с помощью параллельного алгоритма навигации на сети
Если этот показатель задан, то он непосредственно используется при анализе и оценке решения, если нет, то для каждого конкретного случая оформляется своя задача определения показателя.
В частном случае в качестве критерия выбора того или иного локального решения из множества альтернатив может выступать эвристика, представляющая собой набор правил, определяющих порядок выбора из множества решений наилучшего.
3. Реализация БАС на 00 системе в проекте "Учебное расписание"
3.1. Структура класса
Учитывая специфику решаемой задачи и методы, используемые для достижения результатов, определим класс для проекта "Учебное расписание" как поименованную структуру, которая включает в себя:
К = ,
и соответственно
А = и Ф = .
Общедоступная интерфейсная часть описания атрибутов класса включает в себя декларацию признаков объекта, универсально и однозначно характеризующих данную абстракцию:
ОА= { аоI}, (3.1)
где АОi– атрибут объекта-экземпляра класса.
Скрытая интерфейсная часть описания атрибутов класса содержит ссылку на бинарный файл, который включает в себя набор декларативных и/или продукционных правил, предназначенных для генерации и ограничения области значении объектов-экземпляров ( альтернатив)
класса:
са= , (3.2)
где
асI, - скрытый элемент данных класса;
ФБП - файл базы правил генерации объектов-альтернатив.
Общедоступная интерфейсная часть декларации функций (методов) управления объектами класса представляется следующим образом:
ОФ= , (3.3)
где
ФК - функция-конструктор класса, определяющая механизм выделения оперативной памяти для хранения объекта-альтернативы (результата);
ФД – функция-деструктор класса, определяющая механизм освобождения оперативной памяти, выделенной конструктором;
Фоi - общедоступный метод управления объектом класса;
ФОБП - набор функций, предназначенных для обработки базы
