Алгоритм последовательного размещения

УЛЬЯНОВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Заочно-вечерний факультет

Кафедра «Проектирования и Технология Электронных Средств»

Лабораторная работа № 3

ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ АЛГОРИТМОВ

РАЗМЕЩЕНИЯ КОНСТРУКТИВНЫХ ЭЛЕМЕНТОВ РЭС

Работу выполнил:                                                        Работу принял:      

студент группы Рбв-31                                                преподаватель кафедры

Латыпова Е.Г.                                                               Мактас М.Я.

_____________                                                              _______________

Ульяновск

2017

1. Цель работы

Исследовать эффективность алгоритмов размещения элементов РЭС в коммутационном пространстве, освоить особенности алго-ритмизации и программирования задачи размещения на ПЭВМ, приобрести навыки построения математических моделей монтажного пространства и схем соединения модулей, реализации и исследования их при решении задачи размещения с применением САПР.

Общин сведения о задаче размещения

После распределения конструктивных элементов РЭС по коммутационным пространствам различного уровня иерархии, для каждой полученной в результате компоновки сборочной единицы производят размещение включенных в ее состав элементов предыдущего уровня, т.е. выбирают такое их взаимное расположение, при котором наилучшим образом учитываются предъявляемые к аппаратуре требования [1 – 3, 7 11].

Исходными данными для решения задачи размещения являются:

-  данные о конфигурации и размерах коммутационного пространства, определяемые требованиями установки и крепления соответствующей сбороч-ной единицы в аппаратуре;

-  количество и геометрические размеры конструктивных элементов, подле-жащих размещению;

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

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

В том случае, если в качестве критерия размещения используют минимум суммарной взвешенной длины соединений, необходимо сформировать матрицу расстояний размещённых элементов P = || p_ij ||_n*m.

Здесь P_ij = |x_i - x_j| + |y_i - y_j|, а x_i, x_j и y_i, y_j – координаты позиций, в которые размещены соответственно i–й и j–й модули.

 где r_ij – элемент матрицы связности R, а p_ij  – элемент матрицы размещения P.

Математически задача формулируется следующим образом [1 - 5]. Электри-ческая схема представляется в виде мультиграфа, а моделью монтажного про-странства служит графовая решётка. Требуется вершины мультиграфа размес-тить в узлы графовой решётки таким образом, чтобы суммарная длина ребер размещенного мультиграфа была минимальна.

Задача размещения является комбинаторной, т.е. может быть решена толь-ко полным перебором (для размещения n элементов на n позиций существует n! вариантов размещения). Для решения задач размещения разработано большое количество различных алгоритмов [1 – 4]. В данной работе рассмотрим эвристи-ческие алгоритмы

Алгоритм последовательного размещения

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

1. Сформировать матрицу расстояний D, элементы которой будем определять по формуле ортогональной метрики:

                     d_ij = |x_i - x_j| + |y_i - y_j| .                                              (3.2)

2. Для каждой строки матрицы D определить суммарное значение:

3. Ввести матрицу связности R и ее размерность n.

4.Для каждой строки матрицы связности R определить сумму элементов:

5. Найти минимальное значение d_i, если B=i, то пометить столбец j=B.

6. Найти максимальное значение r_i , если Е=i, то удалить столбец j=B.

7. Разместить элемент Е в позицию В.

8. Найти минимум d_i среди оставшихся (m – 1) элементов; просмотреть строку с минимальным d_i и найти минимальный d_ij среди помеченных элементов. Здесь j=B. Определить, какой элемент расположен в позиции j; вновь присвоить B=i, j=B и пометить столбец j.

9. Рассмотреть строку Е в матрице R и найти максимальный r: присвоить E=i, j=E и пометить столбец j.

10. Найти число помеченных столбцов k; если k<n, идти к 8, иначе – к 11.

11. Подсчитать суммарную длину соединений.

4. Экспериментальная часть

Решение

По модели печатной платы и по формуле:

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

вычислим матрицу расстояний D:

                                   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]

                       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

Определим сумму элементов S d_ij в каждой i-й строке матрицы и запи-

                                                                    J=1

шем ее справа от матрицы. Сумма показывает суммарную удаленность i-й позиции от всех остальных.

Рисунок 4.3

Схему соединения корпусов представим в виде мультиграфа (рис. 4.3), для которого построим матрицу связности R:

                                   1 2 3 4 5 6 

                               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_ij в строках матрицы дает локальную степень каждой вершины графа.

        7

Среди S d_ij находим минимальное число, оно равно 18 и соответствует

       J=1

позиции №3. Звездочками помечают все элементы третьего столбца матрицы

                     7

D. Среди S r_ij находим максимальное число, оно равно 9 у вершины №3.

            J=1

Поэтому 3-й модуль, имеющий наибольшее количество связей, размещаем в позицию №3, которая наиболее удалена от остальных позиций платы. После этого 3-й столбец матрицы R исключаем из дальнейшего рассмотрения. Имеем

                                   1 2 4 5 6 

                               1 0 1 0 1 0   

                               2 1 0  1 0 1   

                               3 1 1 [3] 2 2  

                        R = 4 0 1 0 1 2   

                               5 1 0 1 0 1   

                               6 0 1 2 1 0   

                                   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  

                       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

                                          6

Среди оставшихся S d_ij находим минимальное число. Оно равно 22 сразу

                                 J=1

у двух позиций: №2, № 5 и №6. Берем 1-ю по порядку позицию №2. Помечаем все элементы второго столбца матрицы D. Проходим третью строку матрицы  R и находим, что в ней максимальный элемент 3, который находится в 4-м столбце. Следовательно, модуль №4 размещаем в позицию №2, а 4-й столбец матрицы R из дальнейшего рассмотрения исключается. Получили

                                   1 2 5 6 

                               1 0 1 1 0   

                               2 1 0 0 1   

                               3 1 1 [2] 2  

                        R = 4 0 1 1 2   

                               5 1 0 0 1   

                               6 0 1 1 0   

                                   1 2* 3* 4 5 6 

                               1 0 5 4 9 3 7 28

                               2 5 0   3 4 6 4  

                               3 4 3 0 5 3 3  

                       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

                                                                  7

На следующем шаге отыскиваем min из S d_j =22 в строке №5 и №6.

                                                                 J=1

Берем 1-ю по порядку позицию №5.

Просматриваем пятую строку матрицы D и среди помеченных элементов 2-го и 3-го столбцов выбираем минимальный. Так определяем, к какой из уже занятых позиций, позиция №5 находится ближе всего: min[d₅₂, d₅₃] = d₅₃ = 3 – к 3-й. В третий позиции уже находится модуль №3. Поэтому просматриваем третью строку матрицы R и выбираем максимальный элемент r₃₅ = 1 и r₃₆ = 1. Берем 1-ю по порядку позицию №5. Он соответствует 5-му модулю, поэтому элемент №5 размещаем в позицию №5.

Исключаем из дальнейшего рассмотрения пятый столбец матрицы R.

Получили матрицы

                                   1 2  6 

                               1 0 1 0   

                               2 1 0 1   

                               3 1 1 2  

                        R = 4 0 1 2   

                               5 1 0  1   

                               6 0 1 0   

                                   1 2* 3* 4 5* 6 

                               1 0 5 4 9 3 7 28

                               2 5 0 3 4 6 4  

                              3 4 3 0 5 3 3  

                       D = 4 9 4 5 0 6 4 28

                               5 3 6 3 6 0 4  

                               6 7 4 [3] 4 4 0 [22]

                                      6

Далее выбираем min из S d_ij = 15 в 6-й строке. В шестой строке матрицы

                                                          J=1

D среди помеченных элементов d₆₂, d₆₃, d₆₅ минимальный d₆₃ = 3.Это говорит о том, что до позиции №6 ближе всех позиция №3, в которой уже размещен модуль №3. Поэтому просматриваем третью строку матрицы R и среди оставшихся в ней элементов находим максимальный: r₃₆ = 2 в шестом столбце. Тогда модуль №6 размещаем в позицию №6 и исключаем из дальнейшего рассмотрения столбец №6 матрицы R:

                                   1 2    

                               1 0 1      

                               2 1 0      

                               3 1 1    

                        R = 4 0 1     

                               5 1 0      

                               6 0 1      

                                   1 2* 3* 4 5* 6* 

                               1 0 5 4 9 [3] 7 [28]

                               2 5 0 3 4 6 4  

                               3 4 3 0 5 3 3  

                       D = 4 9 4 5 0 6 4 28

                               5 3 6 3 6 0 4  

                               6 7 4 3 4 4 0

                                                                                           6

Вновь выбираем минимальную из оставшихся сумм: S d_1j = 28 для пози-

                                                                                                                              J=1

ции №1. Просматриваем первую строку матрицы D и среди помеченных элементов {d₁₂, d₁₃, d₁₅, d₁₆} находим min: это d₁₅ = 3. Значит, от позиции №1 наименее удалена позиция №5, в которой находится модуль №5. Помечаем все элементы первого столбца матрицы D. Просматриваем пятую строку матрицы R и выбираем максимальный элемент r₅₁ = 1 для элемента №1. Его устанавливаем в 1-ю позицию, а 1-й столбец матрицы исключаем из дальнейшего рассмотрения:

                                   2  

                               1 1    

                               2 0      

                               3 1     

                        R = 4 1      

                               5 0      

                               6 1      

                                   1* 2* 3* 4 5* 6* 

                                  1 0 5 4 9 [3] 7 

                               2 5 0 3 4 6 4  

                               3 4 3 0 5 3 3  

                       D = 4 9 4 5 0 6 4 28

                               5 3 6 3 6 0 4  

                               6 7 4 3 4 4 0

Последний второй модуль, следовательно, попадает в оставшуюся свободной четвертую позицию. Результат размещения дан на рис. 4.4.

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

Рисунок 4.3