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

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) координирующий алгоритм решает задачу общего решения, од­новременно выдав задание блоковым алгоритмам на формиование частных решений. При получении общих решений возможна параллель­ная стратегия для многоальтернативных решений.

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

Похожие работы

Администрирование локальных сетей

Скачать

374863

43

0

... интерфеса и интерфейса локольной сети ·     Предложение о выборе вариантов загрузки При этом возможен вариант запгрузки как с SCSI устройства (диск, CDROM, лента, …) так и через локальную сеть. Загрузочный диск должен быть предварительно сконфигурирован. Так как обьем Boot ROM не может быть большим, в его задачи входит загрузка вторичного загрузчика ...

Предмет и объект прикладной информатики

Скачать

308601

37

3

... производительных сил, тем быстрее повышается Б. населения. В еще большей степени Б. связано с эффективностью социально-экономической политики в данном обществе. Информатика как наука. Предмет и объект прикладной информатики. Системы счисления Инфоpматика — это основанная на использовании компьютерной техники дисциплина, изучающая структуру и общие свойства информации, а также закономерности и ...

Дистанционные технологии в образовании

Скачать

277842

1

5

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

Экономическая теория

Скачать

826315

4

1

... равенства и неравенства. При полном равенстве в распределении доходов "кривая Лоренца" представляла бы собой прямую и, наоборот, кривизна усиливается по мере роста неравенства. В соответствии с современной экономической теорией нежелательно как абсолютное равенство в распределении доходов, так и резкий разрыв в уровне жизни различных групп населения. Абсолютное равенство в доходах не стимулирует ...