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

Для фиксации момента окончания итерационного процесса при реализации алгоритма на ЭВМ применяются различные правила. Например, может задаваться число итераций 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)

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

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

Организация связи по оптическому кабелю магистрали Коченево-Мамонтово
Телекоммуникации являются основой развития общества. Постоянно растущий спрос, как на обычные телефонные, так и на новые виды услуг связи, включая услуги Интернет, предъявляет новые тре ...

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