4 (743480), страница 4

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

Текст из файла (страница 4)

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

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

АБ₁

АБ_i

АБ_N

БА₁

БА_i

БА_N

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.

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

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

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

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

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

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

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

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

KЧH1 = КЧН2, КЧБ1 = КЧБ2 и КЗД1 <= КСД2 (КЗД2 <= КСД1), (3.19)

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

ПРАВИЛО 1.

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

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

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

И блок(&А).КЗД <= блок (&Б).КОД ТО блок(&С) = блок(&А) U блок(&Б).

ПРАВИЛО 2.

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

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

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

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

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

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

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

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

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

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

Ptr=1

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

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

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

ДА

Ptr+1

НЕТ

ДА

НЕТ

ДА

НЕТ

Ptr+1

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

ДА

ДА

НЕТ

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

Характеристики

Список файлов реферата