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

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

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

Пусть задано некоторое разбиение множества элементов схемы Х={х₁, х₂,…, х_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 (количество внешних связей минус количество внутренних связей данного элемента с элементами того же узла).

Рис.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

Рис. 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₃.