Алгоритмы последовательного размещения элементов по связности

Исходной информацией для размещения элементов является:

  • • схема соединений;
  • • параметры конструкции элементов и коммутационного поля.

Прежде всего, рассмотрим наиболее представительные алгоритмы, использующие последовательный процесс установки элементов в позиции.

Пусть Е = { ei , е2,... , еп } — множество элементов, подлежащих размещению, а Р = { pi , р2, ... , Рп } — множество позиций для их установки.

Вводится n-шаговый процесс принятия решений, на каждом шаге которого выбирается один из неразмещенных элементов и помещается в одну из незанятых позиций.

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

Пусть Ек — элементы, размещенные до k-го шага, а Рк — позиции, занятые этими элементами; Ек и Рк — соответственно, неразмещенные элементы и незанятые позиции.

Перед началом размещения могут быть две ситуации:

  • • нет размещенных ранее элементов, внешние выводы узла (контакты, разъемы и т. п.) не закреплены (в этом случае в алгоритме должен быть особо определен способ установки первого элемента);
  • • имеется группа заранее размещенных элементов или закрепленных внешних выводов.

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

Поскольку критерий минимума суммарной длины соединений наиболее распространен, он и будет рассмотрен при описании алгоритмов данной группы.

Рассмотрим последовательный алгоритм по связности. В алгоритмах размещения по связности элемент и позиция выбираются независимо.

Выбор элемента

Любое правило выбора элемента для размещения основано на вычислении «меры связности» еще не размещенных элементов с уже размещенными.

Мерой связности двух элементов е; и ej является количество соединений между ними, заданное в матрице соединений R= || г j j || n х п • Существуют различные способы расчета значений г j j.

Так, в алгоритмах «попарных связей» для каждого неразмещенного элемента подсчитывается характеристика

причем pj рассчитывается по формуле

в которой г j j — множество цепей, связывающих элементы е и ej;

ps — размер цепи;

ws — весовой коэффициент;

X — целочисленный параметр.

Параметр позволяет дифференцировать вклад цепей различного размера. Чем больше значение X, тем больше влияние цепей с малым значением ps.

Очередным размещенным элементом является элемент, имеющий максимальную характеристику (20.6), т. е. выбор элемента осуществляется по наибольшему числу связей с уже размещенными элементами.

Существует и другое правило выбора очередного размещаемого элемента, основанное на оценке числа связей размещаемого элемента ej е Ек как с размещенными, так и с неразмещенными элементами (характеристика абсолютной связности):

В этом случае выбирается элемент с максимальным значением Q (20.8) (данный выбор аналогичен принципу максимальной конъюнкции/мини- мальной дизъюнкции, применяемому в алгоритмах компоновки).

К этому же типу относится характеристика относительной связности:

На очередном шаге алгоритма размещается элемент, имеющий максимальный коэффициент относительной связности.

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

Рассмотрим исходную матрицу смежности с элементом х0, который в нашем случае содержит клеммы К1, К2, КЗ, К4 (рис. 20.2). Он является уже фиксированным элементом, поэтому размещать остальные элементы будем по отношении к нему.

Первый шаг.

Максимальную характеристику имеет элемент xi, следовательно, его размещаем вторым. Имеем: хо; х.

Второй шаг. Расчет проводим с учетом этих двух размещенных элементов:

Размещение элементов электрической схемы

Лекция 20

Макимальную характеристику имеет элемент х7, поэтому его размещаем третьим. Имеем: хо; xi; Х7.

Третий шаг. Произведем расчет с учетом уже трех размещенных элементов:

Максимальную характеристику имеет элемент Хб, поэтому шестой элемент размещаем четвертым. Имеем: хо; xi; Х7; Хб.

Четвертый шаг. Производим расчет с учетом четырех размещенных элементов:

Максимальную характеристику имеет элемент xs, его размещаем пятым. Имеем: хо; хь х7; хв', X5.

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

Максимальную характеристику имеет элемент хз, следовательно, третий элемент размещаем шестым. Имеем: хо; Хь х7 хв, х5; хз.

Шестой шаг. Производим расчет с учетом уже шести размещенных элементов.

Максимальную характеристику имеет элемент ха, следовательно, его размещаем седьмым.

Окончательная последовательность размещения будет такой:

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ   След >