АЛГОРИТМ ПРЕДВАРИТЕЛЬНОГО РАЗМЕЩЕНИЯ

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

Необходимо по критерию минимума суммарной длины соединений разместить 6 ячеек в 6 позиций (рис.5.1).

Рисунок 5.1

Матрица смежности графа имеет вид

                                   1 2 3 4 5 6 

                               1 0 5 4 9 3 7 28 

                               2 5 0 3 4 6 4 22  

                               3 4 3 0 5 3 3 [18]

                      R₁ = 4 9 4 5 0 6 4 28   

                               5 3 6 3 6 0 4 22  

                               6 7 4 3 4 4 0 22

Определим суммарное число связей каждой ячейки с остальными.

                                                       7

Минимальное значение S n_ij = 18. Это означает, что третья ячейка

                                                      J=1

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

Преобразуем исходную матрицу следующим образом. Исключим из матрицы третью строку (ячейка закреплена, и на оставшиеся места претендовать не может), элементы третьего столбца матрицы запишем со знаком « – » и, имитируя установку третьей ячейки на 1-е место, переставим 3-й столбец на 1-е место в матрице. Преобразованная матрица имеет вид:

                                   1 2 3 4 5 6 

                               1 0 5 -4 9 3 7 24 

                               2 5 0 -3 4 6 4    19  

                               4 9 4 -5 0 6 4 23   

                      R₂ = 5 3 6 -3 6 0 4 19  

                               6 7 4 -3 4 4 0 19

Минимальную сумму связей имеет 2-й, 5-й и 6-й элементы матрицы. Берем 1-ю по порядку ячейку №2. Это означает, что 2-я ячейка закрепляется на втором месте.

Матрица преобразовывается так же, как и в предыдущем случае; опреде-ляется минимальное суммарное количество связей, закрепляется следующий элемент.

                                   1 2 3 4 5 6 

                               1 0 -5 -4 9 3 7 19 

                      R₃ = 4 9 -4 -5 0 6 4 19   

                               5 3 -6 -3 6 0 4 13  

                               6 7 -4 -3 4 4 0 15

Минимальную сумму связей имеет 5-й элемент матрицы. Это означает, что 5-я ячейка закрепляется на третьем месте.

Матрица преобразовывается так же, как и в предыдущем случае; опреде-ляется минимальное суммарное количество связей, закрепляется следующий элемент.

                                   1 2 3 4 5 6 

                               1 0 -5 -4 9 -3 7 16 

                      R₄ = 4 9 -4 -5 0 -6 4 13   

                               6 7 -4 -3 4 -4 0 11

Минимальную сумму связей имеет 6-й элемент матрицы. Это означает, что 6-я ячейка закрепляется на четвертом месте.

Матрица преобразовывается так же, как и в предыдущем случае; опреде-ляется минимальное суммарное количество связей, закрепляется следующий элемент.

                                   1 2 3 4 5 6 

                               1 0 -5 -4 9 -3 -7 9 

                      R₅ = 4 9 -4 -5 0 -6 -4 9  

Минимальную сумму связей имеет 1-й и 6-й элементы матрицы. Берем 1-ю по порядку ячейку №1. Это означает, что 1-я ячейка закрепляется на пятом месте.

Матрица преобразовывается так же, как и в предыдущем случае; опреде-ляется минимальное суммарное количество связей, закрепляется следующий элемент.

                                    1 2 3 4 5 6 

                      R₅ = 4 -9 -4 -5 0 -6 -4 0  

    Оставшейся последний 4-й элемент матрицы, закрепляется на шестом месте.

 Процесс длится до тех пор, пока все элементы не будут размещены.

Окончательное распределение элементов на позициях дано на рис.5.2.

Если считать, что расстояние между рядом расположенными ячейками равно условной единице длины, то для полученного размещения суммарная длина равна 82 единицам условной длины.

Рисунок 5.2