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

hspace="13" />

I^O₁ R¹₁ I^O_i Rⁱ₁ I^O_N R^N₁

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

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

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

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

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

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

К = <А, Ф>,

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

А = <О_А, З_А, С_А> и Ф = <Оф, Зф, Сф>.

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

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

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

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

класса:

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

где

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

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

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

О_Ф = <ФК, ФД, Ф₀₁, ..., Фoi, ...., Фоn, ФОБП>, (3.3)

где

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

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

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

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

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

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

ФОБП = <ФВА, ФДП, ФУП, ФРП>, (3.4)

где:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

FOR = <В, Е, S, F(С, Ao₁, …, 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.