3.1 (Автоматизированная система управления санаторным комплексом. Подсистема Диетпитание)

91

ГЛАВА 3

ИНФОРМАЦИОННОЕ ПРЕДСТАВЛЕНИЕ ПОДСИСТЕМЫ

«ДИЕТПИТАНИЕ» НА ОСНОВЕ МЕТОДА

БЛОЧНЫХ АЛЬТЕРНАТИВНЫХ СЕТЕЙ

3.1. Метод блочных альтернативных сетей

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

Пусть задан объект или группа объектов { }. Предполо­жим, что такая совокупность объектов отражается в информацион­ном аспекте в виде некоторого информационного портрета пред­метной области, представленная множеством атрибутов Аi, где i = 1, 2, ..., n. Будем исходить из того, что Аi покрывают полную сово­купность свойств объекта .

Каждый атрибут Аi может принимать множество альтерна­тивных значений . Аi: ( ) (логическое отношение «ИЛИ»). Количество значений атри­бута определяется самим атрибутом.

Альтернатива – это необходимость выбора между взаимоисключающими возможностями, каждая из исключающих друг друга возможностей. Набор альтернативных значений, которые может принимать атрибут, имеет непрерывный дискретный характер. Значения являются альтернативными, т. к. предполагается, что в каждый момент времени атрибут может принимать одно и только одно значение. Сложные задачи всегда формируют решения на основе различных сочетаний исходных данных, в силу чего образуются совокупности альтернативных (исключающих друг друга) решений. Для сложного объекта: А = (А₁,..., А_i,…, А_n) (логическое отношение «И»).

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

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

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

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

……………………………

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

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

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

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

Рис.3.1. Первичное дерево альтернатив

А_i - имя блока;

_{i1, …,} _{ij , …,}_im – значения атрибутов (совокупность альтернатив).

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

Рис.3.2. Первичное дерево альтернатив

с замыкающей вершиной «якорем»

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

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

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

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

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

Транзитный блок используется в тех случаях, когда ни одна из альтернатив в общем решении не участвует, а в частном случае может выступать как ограничитель для рекурсивного перебора альтернатив. То есть когда ни одно значение атрибута не используется, то можно пройти с входа на выход через транзитную вершину Т_i. Если поиск по альтернативным атрибутам А_i продолжается, то путь лежит через рекурсивный блок R_i. Другими словами, рекурсивный блок используется, когда необходимо решить задачу поиска альтернативного значения на массиве альтернатив, т. е. организовать циклический процесс.

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

Рис.3.3. Структурная схема элементарного блока альтер­натив (ЭБА)

А_i - имя блока;

R_i - рекурсивная вершина;

T_i - транзитная вершина;

A^*_i - замыкание альтернатив.

Для упрощения совокупность альтернатив назовем блоком альтернатив (БА); упрощенный вид ЭБА представлен на рис.

Рис. 3.4. Упрощенный вид ЭБА

БA_i = {_{i1, …,} _{ij , …,}_im }

Совокупность таких последовательно соединенных элемен­тарных блоков образует простую БАС. ЭБА — это базовый блок для формирования сетей. Его использование дает возможность порождать любые конфигурации сетей или структур.

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

Для работы с БАС необходимо создать алгоритмы на­вигации на сети. Существует три метода навигации на сети:

• последовательный;

• параллельный;

• смешанный.

Результатом работы алгоритма навигации является формирование вершинного маршрута. Формируется маршрут М=( ). Основная цель таких алгоритмов заключается в определении каждого элемента , в оценке согласованности с другими.

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

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

Последовательная БАС

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

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

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

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

Пусть задан кортеж атрибутов (множество альтернатив):

А = {_: ( = 1, 2, …, n)}. Осуществим последова­тельную генерацию исходов А^* = {_^*: ( = 1, 2, …, n)} для каждой из альтернатив с помощью последовательной БАС.

БАС с последовательной стратегией предс­тавлена на рис. 3.7.

БА₁

БА₂

БА₃

Рис. 3.7. Пример последовательной разомкнутой трехблочной БАС

БА₂

БА₁

БА₃

Рис.3.8. Пример последовательной замкнутой трехблочной БАС

В последовательных БАС генерируемые альтернативные решения соединяются в одну связку с генерирующими следующего ЭБА попарно. В результате вершины А^*_ и А_+1 сливаются в одну А_+1.

Параллельная БАС

При алгоритме с параллельной организацией навигации воз­можны как минимум две схемы:

• одноуровневый алгоритм;

• двухуровневый алгоритм.

Одноуровневый алгоритм

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

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

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

Можно замкнуть параллельную БАС через:

• вершины транзита и рекурсии;

• включить в качестве дополнительной некоторую вер­шину агрегирования.

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

Двухуровневый алгоритм

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

Выход

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

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

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

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

Внутриблоковый – это такой маршрут Мⁱ_N М_N (i = 1, …, n), который тем или иным образом связывает две соседние вершины ( ) первого ранга, принадлежащие i-му блоку. Другими словами, внутриблоковый маршрут формируется как последовательность вершин, связанных определенным отношением.

Межблоковые – маршруты М^il_N , которые связывают некоторые пары вершин первого ранга {( ), i = 1, …, n; k = 1, 2, …, n; }. Межблоковые маршруты используются при формировании циклов, и, следовательно, связываемые вершины ( ) для таких маршрутов отождествляются.