Каждый элемент
Возможные структуры БАС определяются иерархией отношений между классамиобъектов-альтернатив.
Последовательная БАС
Дляпоследовательной сети последовательный алгоритм навигации может быть реализовандвумя базовыми способами.
1. Прохождениесети реализуется последовательно, начиная с первого a1 и заканчивая последним аN блоками. Алгоритм обращается к блоку a1,просматривает его содержимое и через транзитные вершины передаетрезультат. Далее переходит к следующему блоку. В итоге образуется некоторыйвершинный маршрут Мj =(a1j, ..., anj,..., aNj),который и представляет данные о результате решения. Если какое-то решениенесовместно, то выявляется причина несовместимости и ищется новое решение.
2. Алгоритм обращаетсяпоследовательно к каждому блоку и результат из каждого блока передаетсяобратно в алгоритм. Массив частных решений преобразуется в маршрут, далеепроцедура продолжается.
Припоследовательной навигации определяется логика прохождения сети, т.е. порядок входа в каждый из блоков, порядокпоиска частного решения внутри блока,порядок выхода из блока, входа в следующийблок и «склеивания» частных решений.
Пусть задан кортеж атрибутов (множествоальтернатив):
А= {an: (n= 1, 2, …, n)}. Осуществим последовательную генерацию исходов А* = {an*:(n = 1, 2, …, n)} для каждой из альтернатив с помощью последовательной БАС.
БАС с последовательной стратегией представлена на рис. 3.7.
Рис. 3.7.Пример последовательной разомкнутой трехблочной БАС
Рис.3.8.Пример последовательной замкнутой трехблочной БАС
В последовательных БАС генерируемые альтернативные решения соединяются в одну связку с генерирующими следующего ЭБА попарно. В результате вершины А*n и Аn+1 сливаются в одну Аn+1.
ПараллельнаяБАС
При алгоритмес параллельной организацией навигации возможныкак минимум две схемы:
• одноуровневый алгоритм;
• двухуровневый алгоритм.
Одноуровневый алгоритм
По схеме одноуровневого алгоритма все элементы сети связаны друг с другом и включают координирующую и исполнительную функции. Одноуровневый алгоритм являетсядецентрализованной схемой навигации.
Рис. 3.9. Параллельнаяодноуровневая структура БАС
На рисунке 3.9 связь реализуется через общую транзитивную вершину (раздельный вход и выход).
Можно замкнуть параллельную БАС через:
- вершины транзита и рекурсии;
- включить вкачестве дополнительной некоторую вершину агрегирования.
При параллельной генерации решений в каждом блоке БАi работает свой алгоритм формирования исходов. Алгоритмы работают одновременно, и матрица альтернативных решений заполняется построчно.
Двухуровневый алгоритм
На верхнем уровне двухуровневого алгоритма (рис.3.10) находится координирующий алгоритм, а на нижнем -исполняющий. По командекоординирующего алгоритма каждый исполняющий алгоритм входит в свой блок, определяетчастное решение внутри блока и передаетрезультат в координирующий алгоритм. Последний осуществляет функцию сопряжения частных решений в единое общее решение.Этот процесс может быть итеративным, формализующим соответственные парадигмы решений. Данныйдвухуровневый алгоритм является централизованной схемой навигации.
Рис. 3.10. Параллельная двухуровневая структура БАС
3.1.3. Маршруты наБАС
Применение блочно-альтернативныхсетей
В БАСиспользуется вершинный тип маршрутов. С точки зрения сети маршрутыподразделяются на внутриблоковые и сетевые. Последние, в свою очередь,формируются из внутриблоковых и межблоковых.
Внутриблоковый –это такой маршрут МiN
Межблоковые –маршруты МilN , которые связывают некоторые пары вершин первогоранга {(
Прииспользовании БАС для решения конкретных задач могут возникать ситуации, когдатот или иной внутриблоковый маршрут МiN формируется неоднозначным образом. При этомвозможны три случая:
1) внутриблоковый маршрут МiN проходится один раз слева направо;
2) внутриблоковый маршрут МiN для маршрута МN является запрещенным;
3) внутриблоковый маршрут МiN должен быть пройден неоднократно.
Всоответствии с названными случаями, определим три типа маршрутов: ациклические AMiN, транзитные ТMiN и циклические СMiN.
Ациклические маршруты
Наиболеепростыми маршрутами МN
Ациклическиймаршрут (АМi) формируется какпоследовательность
вершинсовместно с отношением между вершинами:
AMi : (Ai, rij , aij),
где Аi - атрибут;
rij - определяет отношение между атрибутом ивершиной-значением aij;
aij- значение атрибута Аi.
Полноепредставление внутриблокового маршрута по схеме исток-сток будет представлятьсобой объединение:
AMi : (Аi , rij ,aij) U(aij ,rji ,A*i),
или в общем видедля вершин-альтернатив получим вершинный ациклический маршрут:
AMi: (Аi, aij, A*i).
Аналогичнодля маршрута, проходящего через транзитивную вершину:
АMiT: (Ai, rT, A*i),
чтоэквивалентно записи
AMiT:(Ai, T,A*i).
Ациклическиемаршруты имеют место в тех случаях, когда осуществляется однократноепрохождение слева направо через блок