Итерационные алгоритмы улучшения компоновки

Для фиксации момента окончания итерационного процесса при реализации алгоритма на ЭВМ применяются различные правила. Например, может задаваться число итераций m либо параметр д, определяющий число итераций неявным образом:

. (4.8)

Далее рассмотрим процесс расчета приращений.

Пусть задано некоторое разбиение множества Е= {e1, e2,…, еп} на узлы T1 Т2,…, Tг.

Рассмотрим сначала случай, когда схема описана матрицей соединений R=||rij||nЧn. Оценим изменение в количестве межузловых соединений при обмене местами элементов ехTi, и еуТj. Поскольку при обмене перераспределяются лишь соединения элементов ех и еу, рассмотрим более детально структуру их соединений (рисунок 6).

Рисунок 6 - Межузловые соединения: а) - до обмена, б) - после обмена.

Обозначим через Uij, множество элементов {еk: еkТi и еkТi}. Тогда в соответствии с рисунком 4, а количество межузловых соединений до обмена равно

, (4.9)

где С - число межузловых соединений не участвующих в обмене элементов.

В соответствии с рисунком 4, б после обмена количество межузловых соединений станет равным

(4.10)

Вычитая (4.10) из (4.9), получим

(4.11)

Пусть Lxj - число соединений ex с элементами узла Tj, Lyi - число соединений ey c элементами узла Ti:

, (4.12)

а Fxi - число соединений ex с элементами узла Ti и Fyj - число соединений ey с элементами узла Tj

(4.13)

Тогда (4.11) принимает вид:

(4.14)

Lxi (Lyi) и Fxi (Fyj) соответственно внешние и внутренние соединения элементов ex и ey.

Для произвольного элемента exTi удобно ввести характеристику Dx=Lxj-Fxi, представляющую собой разность числа внешних и внутренних соединений. Аналогично вводится характеристика Dу для eyTj.

С учётом принятых обозначений формула (4.14) приобретает вид

(4.15)

При обмене местами элементов exTi и eyTj наряду с изменением количества межузловых соединений L происходит перераспределение внешних соединений для узлов Ti и Tj.

При задании схемы матрицей R суммарное число выводов на узлах V=2L, поэтому

, (4.16)

где ДV (x, y) - изменение суммарного числа выводов на узлах, а Дvi(x, y) и Дvj(x, y) - изменение числа выводов на узлах Ti и Tj.

Получим теперь выражения для Дvi(x, y) и Дvj(x, y). Обратимся к рисунку 4. Число внешних выводов на узле равно числу соединений между элементами узла и элементами, не входящими в узел. В связи с этим для расчета Дvi(x, y) можно использовать (4.15), если придать входящим в нее характеристикам Dx и Dy другой содержательный смысл.

Можно считать, что имеются два узла Ti и Tj*=UijTj=E\Ti. Введем характеристики D*x и Dy:

(4.17)

Читайте также

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

Обучающая подсистема для лабораторного исследования характеристик замкнутых САУ в среде интернет
В последние десятилетия в зарубежных системах образования произошли существенные изменения, обусловленные бурным развитием научно-технического прогресса и его воздейст ...

Проектирование цифрового устройства для реализации типовых микроопераций
Разработать функциональную и принципиальную схему операционного устройства исходя из основных параметров по вариантам. Также требуется предоставить блок схемы алгоритмов выполнения опе ...