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

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

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

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

Организация системы контроля доступа и видеонаблюдения в учреждении образования
Система контроля доступа - это совокупность программно-технических средств и чётко сформированной системы управления движением персонала и временем его нахождения на объекте. Основными ...

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