Xreferat.com » Рефераты по экономико-математическому моделированию » Решение творческих задач методом блочных альтернативных сетей: объектно-ориентированные представления

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

loading="lazy" src="http://xreferat.ru/image/114/1307199735_145.gif" alt="" width="76" height="2" align="LEFT" hspace="13" />


Вход Выход


Рис. 2.4. Инкапсуляция БА и ФВА в класс объектов-альтернатив









БА1

БАN

БА



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









БА1

БАN

БА




Блок обратной связи




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


2.2. Методы формирования решения


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


При работе с БАС возможны следующие варианты навигации:

- последовательная;

- параллельная;

- смешанная.

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

1. Прохождение сети реализуется последовательно, начиная с первого a1 и кончая последним аN блоками. Алгоритм обращается к блоку a1, просматривает его содержимое и через транзитные вершины передает результат. Далее переходит к следующему блоку. В итоге образуется некоторый вершинный маршрут R1=(1j,... ,j,.. ,Nj), который и представляет данные о результате решения. Если частные решения совместны, то они оцениваются по критериям -адекватнос­ти. Если какое-то решение несовместно, то выявляется причина не­совместимости и ищется новое решение.


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


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


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

Внутриблоковый маршрут формируется как последовательность вершин, связанных определенным отношением г.

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

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

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

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

В зависимости от содержания маршрута и метода его формирова­ния будем различать ациклические и циклические маршруты.

Ациклический маршрут (АМ1) формируется как последовательность

вершин совместно с отношением между вершинами:


AMi : (Ai rij uij), (2.8)

где

Аi - атрибут;

rij - определяет отношение между атрибутом и вершиной-значе­нием ij;

ij - значение атрибута Аi.

Полное представление внутриблокового маршрута по схеме ис­ток-сток будет представлять собой объединение:


AMi : (Аi rij ij) U (ij rji A*i), (2.9)


или в общем виде для вершин-альтернатив получим вершинный ацикли­ческий маршрут:

AM1: (Аi, ij, A*i). (2.10)


Аналогично для маршрута, проходящего через транзитную верши­ну:


АMiT: (Ai, rT, A*i), (2.11)


что эквивалентно записи

AMiT: (Ai, T, A*i). (2.12)


В циклическом маршруте (ЦМi) использует вершина с индексом R:


ЦМi*: (Ai, ij, A*I) Rq, q = 1,2, …, Q (2.13)


где - определяет повтор маршрутов.

Для циклических маршрутов возможно несколько вариантов реали­зации:

- поиск одной единственной альтернативы;

- использование двух альтернатив вместе;

- поиск с множеством альтернатив.

В первом случае может реализоваться q-кратное прохождение по внутриблоковому маршруту, причем значение q определяется коли­чеством циклов, при котором находится требуемое значение оси,

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


ЦМi**: (Ai, (ij, q1), A*I) Rq, q = 1,2, …, Q (2.14)

При дальнейшем увеличении количества описании альтернатив gjлучим циклический маршрут с множеством альтернатив:

ЦМi**: (Ai, {ij}, A*I) Rq, q = 1,2, …, Q (2.15)


Межблоковые и сетевые маршруты формируются на основе склеива­ния внутриблоковых. Для этих целей используются специальные алго­ритмы, которые осуществляют как формирование самого маршрута, так и склеивание внутриблоковых в единый сетевой (рис. 2.7):

МN ~ MN, = U MБi, (2.16)

где

MN - сетевой маршрут;

MБi - внутриблоковый маршрут.


При таком алгоритме навигации путем склеивания будет получен маршрут:


MN = R <=> (R1,, …, Ri, …, RN), (2.17)


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

В другом случае имеет место следущая картина, представленная на рис. 2.8.

Для каждого блока альтернатив определяется свой алгоритм вы­бора альтернативы. Алгоритм параллельной навигации, в свою оче­редь, реализует функции координации, которые взаимодействуют с каждым блоковым алгоритмом. Работа осуществляется параллельно. Алгоритм координации передает исходные данные (IO) в локальные алгоритмы и запускает их в работу. Каждый ив локальных алгоритмов формирует внутриблоковый маршрут и соответствующий результат (R). Далее формируется последовательность (R11, ..., Ri1, ..., RN1)=Rl несвязанных между собой решений. После этого решается задача склеивания частных решений в общее. Данная процедура может проте­кать по двум направлениям:

1)формирование общего решения на уровне координирующего ал­горитма; анализ, оценка, принятие решения для дальнейших дейс­твий;

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

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


2.2.3. Оценка результатов решения задачи на БАС


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

NR = (m x n) => П{R} (2.18)

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

АНПС




R1 Ri RN

БА1

БАi

БАN



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


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

АБ1

АБi

АБN

БА1

БАi

БАN

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: