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

1) с учетом соответствия цели:

- уменьшение некоторого нежелательного различия,

- непосредственное решение той или иной подзадачи;

2) с учетом опыта:

- повторение прошлого,

- обнаружение ключевого действия;

3) с учетом необходимых условий:

- решение, обусловленное анализом ситуации,

- исключение неосуществимого варианта;

4) с учетом фактора случайности:

• предпочтение отдается разнообразию.

Этап 2. Осуществление выбранного действия и изменение текущей ситуации.

Этап 3. Оценка ситуации:

1) по аналогии:

- известна сама задача,

- известна подзадача;

2) по величине расстояния до цели:

-расстояние между двумя ситуациями,

-количество усилий, затрачиваемое на поиск;

3) по математическому критерию:

- составление перечня необходимых и/или достаточных для полу­чения данного решения характеристик,

- численная оценочная функция,

- верхние и нижние границы,

- сумма стоимостей, выбранных подходящим способом;

4) по ожидаемому выигрышу (критерий, связанный с прошлым опытом):

- простота ситуации,

- коэффициент расширения поиска,

- любой другой критерий (сложность задачи, затрачиваемое на

ее решение время и т.д.).

Этап 4. Исключение бесполезных ситуации.

Этап 5. Если достигнута конечная цель - конец, иначе выбор новой исходной ситуации и повторить поиск:

1) движение только вперед:

- систематическое развитие последней порожденной ситуации;

2) выполнение действий параллельно:

- поочередное выполнение всех действий;

3) выбор в качестве исходной самой многообещающей ситуации:

- в отношении оценочной функции,

- в отношении незначительного числа входящих в нее действий;

4) компромисс между:

- глубиной поиска,

- оценкой ситуации.

2.1.2.2. Структуры БАС

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

Одной из возможных конфигураций может быть последовательная БАС. Пусть задан кортеж атрибутов {А_: =1, N}, на основе которого формируется БАС с последовательной стратегией, вид которой предс­тавлен на рис. 2.5.

Замкнутый аналог последовательной БАС представлен на рис. 2.6.

ФБА

Вход Выход

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

^БА₁

^БА_N

^БА_

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

^БА₁

^БА_N

^БА_

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

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

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

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

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

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

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

- смешанная.

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

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

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

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

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

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

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

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

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

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

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

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

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

AMⁱ : (Aⁱ r_ij u_ij), (2.8)

где

Аⁱ - атрибут;

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

_ij - значение атрибута Аⁱ.

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

AMⁱ : (Аⁱ r_ij _ij) U (_ij r_ji A*_i), (2.9)

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

AM¹: (Аⁱ, _ij, A*_i). (2.10)

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

АMⁱ_T: (Aⁱ, r_T, A*_i), (2.11)

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

AMⁱ_T: (Aⁱ, T, A*_i). (2.12)

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

ЦМⁱ_*: (Aⁱ, _ij, A*_I)  R_q, q = 1,2, …, Q (2.13)

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

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

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

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

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

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

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

ЦМⁱ_**: (Aⁱ, (_ij, _q1), A*_I)  R_q, q = 1,2, …, Q (2.14)

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

ЦМⁱ_**: (Aⁱ, {_ij}, A*_I)  R_q, q = 1,2, …, Q (2.15)

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

М_N ~ MN_, = U MБi, (2.16)

где

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

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

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

MN_ = R (R_1,, …, R_i, …, R_N), (2.17)

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

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

Для каждого блока альтернатив определяется свой алгоритм вы­бора альтернативы. Алгоритм параллельной навигации, в свою оче­редь, реализует функции координации, которые взаимодействуют с каждым блоковым алгоритмом. Работа осуществляется параллельно. Алгоритм координации передает исходные данные (I^O) в локальные алгоритмы и запускает их в работу. Каждый ив локальных алгоритмов формирует внутриблоковый маршрут и соответствующий результат (R). Далее формируется последовательность (R¹₁, ..., Rⁱ₁, ..., R^N₁)=R_l несвязанных между собой решений. После этого решается задача склеивания частных решений в общее. Данная процедура может проте­кать по двум направлениям:

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

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

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

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

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

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

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

АНПС

R₁ R_i R_N

БА₁

БА_i

БА_N