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

5.4.1 Итерационный алгоритм парных перестановок элементов

Итерационный алгоритм парных перестановок элементов используется, когда уже получен какой-то вариант компоновки (например, последовательным алгоритмом).

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

Пусть задано некоторое разбиение множества элементов схемы Х={х₁, х₂,…, х_n} на узлы T₁, T₂, …,T_γ .Схема описана с помощью матрицы R (матрицы соединений или смежности) R=||r_ij||_nxn.

Рассмотрим итерацию между двумя узлами (T₁, T₂). Строим перестановочную матрицу W для этой пары узлов. Строки матрицы – элементы одного узла. Столбцы матрицы – элементы второго узла. Элемент матрицы W (w_ij) отражает изменение количества межузловых соединений при обмене местами элементов x_iT₁, x_jT₂. w_ij находится по формуле

w_ij = α_i + α_j -2 r_ij , (5.4.1.1)

r_ij – элемент матрицы смежности R;

α_i и α_j - характеристические числа элементов х_i и х_j (количество внешних связей минус количество внутренних связей данного элемента с элементами того же узла).

T₁

T₂

r_j1

x₁

x_i

x_j

r_ij

r_j2

x₂

r_i1

r_i2

Рис.5.4.1.1

α_i = L_i2 - F_i1; α_j -= L_j1 - F_j2; (5.4.1.2)

L_i2 - число связей между x_i и элементами узла T₂ (внешние связи),

L_j1 - число связей между x_j и элементами узла T₁ (внешние связи):

L_i2 = ∑ r_i2 , L_j1 = ∑ r_j1, (5.4.1.3)

x₂T₂ x₁T₁

F_i1 - число связей между x_i и элементами узла T₁ (внутренние связи),

F_j2 - число связей между x_j и элементами узла T₂ (внутренние связи):

F_i1 = ∑ r_i1 , F_j2 = ∑ r_j2. (5.4.1.4)

x₁T₁ x₂T₂

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

Если была результативна одна малая итерация, то проводят новую большую итерацию. Для окончания итерационного процесса при исполнении алгоритма на ЭВМ применяют различные критерии (например, число итераций).

Пример Дана матрица смежности

	x1 x2 x3 x4 x5 x6 x7
x1	0 0 0 0 1 0 2
R = x2	0 0 2 0 3 0 0
x3	0 2 0 1 0 0 1
x4	0 0 1 0 0 2 1
x5	1 3 0 0 0 0 0
x6	0 0 0 2 0 0 1
x7	2 0 1 1 0 1 0

T₁

T₂

x₂

x₅

x₁

x₇

x₃

x₄

x₆

T₃

Рис. 5.4.1.2

Строим перестановочную матрицу W для узлов T₁ и T₂.

	x2 x3
x1	-2 -4
W1 = x5	-3 1
x7	0 -4

w₁₂ = (0-3)+(3-2)-2*0= -2 w₅₂ = (3-1)+(3-2)-2*3= -3

w₁₃ = (0-3)+(1-2)-2*0= -4 w₅₃ = (3-1)+(1-2)-2*3= 1

w₇₂ = (1-2)+(3-2)-2*0= 0 w₇₃ = (1-2)+(1-2)-2*1= -4

Меняем местами элементы x₅и x₃.