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

Алгоритм включает такую последовательность действий [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).

Конец.

Алгоритм обратного размещения без парных перестановок.

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

Рисунок 6.1

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

                                   1 2 3 4 5 6 S n_ij

                               1 0 1 1 0 1 0 3

                               2 1 0 1 1 0 1 4

                               3 1 1 0 3 2 2 9

                        R = 4 0 1 3 0 1 2 7

                               5 1 0 2 1 0 1 5

                               6 0 1 2 2 1 0 6

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

                                                                                7

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

                                                                              J=1

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

                                   1 2 3 4 5 6 S d_ij

                               1 0 5 4 9 3 7 28

                               2 5 0 3 4 6 4 22

                                  3 4 3 0 5 3 3 18

                       D = 4 9 4 5 0 6 4 28

                               5 3 6 3 6 0 4 22

                               6 7 4 3 4 4 0 22

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

                            6

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

                       J=1

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

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

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

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

Рисунок 6.2

Суммарная длина соединений получилась равной 72 условным единицам.

ВЫВОД

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

      - при последовательном размещение суммарная длина соединений 68 условных единиц;

- при предварительном размещение суммарная длина соединений 82 условных единиц;

    - при обратном размещение суммарная длина соединений 72 условных единиц;

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