АЛГОРИТМ ОБРАТНОГО РАЗМЕЩЕНИЯ

 

Алгоритм включает такую последовательность действий [1, 3].

1. Вычислить матрицу расстояний D между позициями на плате. Элементы матрицы d_ij определяются по формуле:

d_ij = |x_i - x_j| + |y_i - y_j|.

2. Для каждой строки матрицы D определить суммарное значение элементов d_ij, стоящих в этой строке.

3. Для каждой строки матрицы R определить суммарное значение элементов r_ij, стоящих в этой строке. Полученные значения – локальные степени элементов.

4. Упорядочить элементы t₁ по возрастанию характеристики r_i: t_z1, t_z2, …, t_2n.

5. Упорядочить позиции l_j по убыванию характеристики d_j : l_d1, l_d2, …, l_dn.

6. Выполнить размещение элементов в позиции p(t_k) = l_k, где k = 1, …, n.

7. Подсчитать суммарную длину по формуле (2.1).

Конец.

 

ПРИМЕР 3.3

По критерию минимума суммарной длины соединений необходимо разместить семь элементов в семь позиций. Позиции на коммутационном поле расположены в линейку с координатами соответственно 1-я (3, 0); 2-я (7, 0); 3-я (11, 0); 4-я (15, 0); 5-я (19, 0); 6-я (23, 0); 7-я (27, 0).

Граф электрической схемы описывается матрицей связности R:

1 2 3 4 5 6 7 S n_ij

1 0 0 1 1 0 1 3 6

2 0 0 0 1 2 2 0 5

3 1 0 0 3 0 2 0 6

R = 4 1 1 3 0 0 0 0 5

5 0 2 0 0 0 1 0 3

6 1 2 2 0 1 0 1 7

7 3 0 0 0 0 1 0 4 .

Рис.3.4

 

 

Решение

По матрице связей R определим суммарную величину связей каждого

элемента с остальными: r_i = S r_ij (значения записаны справа от матрицы R).

J=1

Для данных позиций вычислим по (3.1) матрицу расстояний:

 

1 2 3 4 5 6 7 S d_ij

1 0 4 8 12 16 20 24 84

2 4 0 4 8 12 16 20 64

3 8 4 0 4 8 12 16 52

D = 4 12 8 4 0 4 8 12 48

5 16 12 8 4 0 4 8 52

6 20 16 12 8 4 0 4 64

7 24 20 16 12 8 4 0 84 .

 

По матрице D определим суммарное расстояние каждой позиции до всех

остальных: d_i = S d_ij (значение d_i записаны справа от матрицы D).

J=1

Упорядочим элементы t_i по возрастанию r_i: элементы 5-й (r₅=3), 7-й (r₇=4), 2-й (r₂=5), 3-й (r₄=5), 1-й ( r₁=6), 3-й ( r₃=6), 6-й ( r₆=7).

Последовательность номеров позиции l_i запишем по убыванию d_i: позиции 1-я (d₁=84), 7-я (d₇=84), 2-я (d₂=64) и 6-я, 3-я (d₃=52), 5-я (d₅=52), 4-я (d₄=48).

Выполним размещение элементов в позиции: 5-го элемента в 1-ю позицию, 7-го в 7-ю, 2-го во 2-ю, 4-го в 6-ю, 1-го в 3-ю, 3-го в 5-ю, 6-го в 4-ю.

Результаты размещения показаны на рис.3.5.

Составим матрицу размещения Р для установленных в позиции элементов. Установлены они в позиции со следующими координатами: 1-й элемент в позицию с координатами (11, 0), 2-й (7, 0), 3-й (19, 0), 4-й (23, 0), 5-й (3, 0), 6-й (15, 0) и 7-й элемент в позицию с координатами (27, 0).

 

Рис.3.5

 

Тогда матрица Р будет:

1 2 3 4 5 6 7

1 0 4 8 12 8 4 16

2 4 0 12 16 4 8 20

3 8 12 0 4 16 4 8

Р = 4 12 16 4 0 20 8 4

5 8 4 16 20 0 12 24

6 4 8 4 8 12 0 12

7 16 20 8 4 24 12 0 .

 

Для определения матрицы геометрии А каждый элемент матрицы Р умножаем на соответствующий элемент матрицы связности R.

В результате имеем:

 

1 2 3 4 5 6 7 S a_ij

1 0 0 8 12 0 4 48 72

2 0 0 0 16 8 16 0 40

3 8 0 0 12 0 8 0 28

A = 4 12 16 12 0 0 0 0 40

5 0 8 0 0 0 12 0 20

6 4 16 8 0 12 0 12 52

7 48 0 0 0 0 12 0 60 .

 

Поскольку сумма элементов матрицы А определяет удвоенную суммарную длину соединений полученного размещения, длина соединений будет:

7 7

L = (1/2) S S а_ij = 156.

_{j=1 j=1}

Для оценки эффективности алгоритма перемножим поэлементно матрицу связности R на матрицу расстояний D. Получим

 

1 2 3 4 5 6 7

1 0 0 8 12 0 20 72

2 0 0 0 8 24 32 0

3 8 0 0 12 0 24 0

A¹ = 4 12 8 12 0 0 0 0

5 24 24 0 0 0 4 0

6 20 32 24 0 4 0 4

7 72 0 0 0 0 4 0 .

 

Суммарная длина соединений в этом случае была бы

7 7

L = (1/2) S S а_ij = 220.

_{j=1 j=1}

Следовательно, применение алгоритма обратного размещения позволило сократить в данном примере длину соединения на 64 условные единицы.

 

ДОМАШНЕЕ ЗАДАНИЕ

6.1. Ознакомиться с методами решения задачи размещения конструктивных элементов.

6.2. Изучить алгоритмы последовательного, предварительного и обратного размещений.

6.3. Подготовить данные к эксперименту.

6.4. Провести «ручное» размещение одного из узлов последовательным, предварительным и обратным методами.