ТЕМА 6. Алгоритмы размещения элементов

Есть случаи, когда узлы содержат группы сильно связанных элементов и для улучшения компоновки необходимо осуществить групповые перемещения элементов.

Дано два узла T₁ и T₂ (рис.4.2.1). Рассмотрим один из способов групповых перестановок.

Рис.5.4.2.1 Рис.5.4.2.2

Формируем перестановочную матрицу W для узлов T₁ и T₂. Выбираем пару элементов x_iÎT₁, x_jÎT₂, для которых w_ij имеет максимальное значение. Осуществляем перестановку элементов и временно фиксируем элементы на новых местах. Вновь формируем перестановочную матрицу и выбираем следующую пару элементов, для которых w_ij имеет максимальное значение, осуществляем перестановку элементов.

Процесс парных обменов продолжается до тех пор, пока все элементы из узла T₁ не переместятся в узел T₂ и наоборот. Если k – число элементов в каждом узле, то будет k обменов и k максимальных значений w_ij, которые образуют последовательность w₁, w₂,…, w_s,…, w_k (s=1,2,…,k). w_ij могут быть положительными, отрицательными и равными нулю.

Вычислим накопленное приращение функции (g) после обмена пары (x_i, x_j):

i

g_i = ∑ w_s, i =1, 2,…, k (5.4.1.5)

S=1

wi; gi

i

	k

Рис.5.4.2.3. Приращения

g_i =0, когда обмен полный, т.е. (i=k). После k обменов получаем узлы T_{1 (k)} = T₂ и T_{2 (k)} = T₁.

Если gmax> 0, то произведем действительную перестановку группы элементов, участвовавших в первоначальной перестановке до i–го шага

Подсчитаем характеристические числа (α_i) элементов для нашего примера:

α₁ = 0-6 = -6, α₅ = 0-6 = -6

α₂ = 3-7 = -4, α₆ =3-7 = -4

α₃ = 3-7 = -4, α₇ =3-7 = -4

α₄ = 0-6 = -6, α₈ = 0-6 = -6

Подсчитаем w_i для всех возможных парных обменов и составим таблицу.

Таблица 5.4.2.1

обмен	w1 (1-ый шаг)	w2 (2-ый шаг)	w3 (3-ый шаг)	w4 (4-ый шаг)
x1 и x5	-12	12*
x1 и x6	-10
x1 и x7	-10	-2
x1 и x8	-12
x2 и x5	-10
x2 и x6	-8*
x2 и x7	-14
x2 и x8	-10
x3 и x5	-10	-2
x3 и x6	-14
x3 и x7	-8	-16	-16
x3 и x8	-10	-14	-14
x4 и x5	-12
x4 и x6	-10
x4 и x7	-10	-14	-14
x4 и x8	-12	-12	-12*

На первом шаге ни один парный обмен не приводит к уменьшению числа межузловых соединений. Допускаем временное возрастание числа соединений и переставляем x₂ и x₆ элементы с максимальным значением w_i. g₁ = w₁. =-8

На втором шаге максимальное значение w_i имеет пара элементов x₁ и x₅

Накопленное приращение g₂ = w₁ + w₂ =-8+12=4.

Третий шаг – обмен x₄ и x₈. g₃ = g₂ + w₃ =4+(-12)=-8.

На четвертом шаге обменивается оставшаяся пара элементов x₃ и x₇. g₄ = g₃ + w₄ =-8+8=0.

Имеем последовательность значений g_i: -8, +4, -8, 0. Максимальное значение соответствует обмену первых двух пар элементов x₂ и x₆, x₁ и x₅. Это оптимальное разбиение (рис.5.4.2.2).

ТЕМА 6. Алгоритмы размещения элементов