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

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

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

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

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

•      смешанный.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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