Метод обратного размещения

В методе осуществляется предварительная оценка каждого из размещаемых элементов х₁, х₂,…, х_n и свободной позиции l₁, l₂,…, l_n. После все элементы размещаются одновременно.

Дана матрица соединений R=||r_ij||_nxn и матрица расстояний D=||d_ij||_nxn.

Для x_i по матрице R найдем суммарное число соединений этого элемента с остальными:

n

r_i = ∑ r_ij, i= 1, 2,…, n

j=1

Для l_i по матрице D найдем

n

d _i = ∑d _ij, i= 1, 2,…, n

j=1

d _i - определяет суммарное расстояние этой позиции до других позиций.

Позиции в центре коммутационного поля имеют меньшее значение d _i, чем крайние. Т.е. в центре коммутационного поля размещены элементы с большим значением r_i (сильно связанные элементы).

Алгоритм размещения по шагам:

1) Упорядочить элементы по возрастанию характаристики r_i: i₁, i₂,…, i_n (r_i1 £ r_i2 £…£ r_in).

2) Упорядочить позиции по убыванию характаристики d_j: j₁, j₂,…, j_n (d_j1 ³ d_j2 ³…³ d_jn).

3) Определим размещение p (i_k) = j_k, k = 1, 2, …, n.

Пример. Расположение позиций:

l₁ l₂ l₃ l₄ l₅ l₆

1ед. дл.

	x1 x2 x3 x4 x5 x6		d1 d2 d3 d4 d5 d6
x1	0 2 2 3 9 4	∑=r1 d1	0 1 2 3 4 5
x2	2 0 1 10 5 6	∑=r2 d2	1 0 1 2 3 4
R = x3	2 1 0 3 4 7	∑=r3 D = d3	2 1 0 1 2 3
x4	3 10 3 0 7 8	∑=r4 d4	3 2 1 0 1 2
x5	9 5 4 7 0 11	∑=r5 d5	4 3 2 1 0 1
x6	4 6 7 8 11 0	∑=r6 d6	5 4 3 2 1 0

1)Считаем суммарную связь первого элемента с остальными (вектор r₁)

r₁ =2+2+3+9+4=20, затем r₂ и т. д. Располагаем характеристики по возрастанию:

r3	r1	r2	r4	r5	r6

Получаем последовательность элементов: 3,1, 2, 4, 5, 6.

2)Считаем суммарную длину между первой позицией и остальными позициями (вектор d₁)

d₁ =1+2+3+4+5=15, затем d₂ и т. д. Располагаем характеристики по убыванию:

d1	d6	d2	d5	d3	d4

Получаем последовательность позиций:1,6, 2, 5, 3, 4.

3) Результат размещения:

l₁ l₂ l₃ l₄ l₅ l₆

Для полученного размещения суммарная длина соединений, равная скалярному произведению векторов r_i d_j,составляет 179. Есть лучший вариант размещения:

l₁ l₂ l₃ l₄ l₅ l₆

Суммарная длина соединений составляет 170.

Метод прост, но не всегда дает наилучший вариант размещения (используется, как начальный вариант размещения).