Материал: Лабораторная работа№ 3, 4 Исследование алгоритмов размещения конструктивных элементов и итерационных алгоритмов
7. Подсчитать суммарную длину соединения L по формуле (3.1). Конец.
ПРИМЕР 3.2
Необходимо по критерию минимума суммарной длины соединений разместить 7 ячеек в 7 позиций (рис.3.4).
Матрица смежности графа имеет вид |
|
|
|
|||||||||
|
1 |
|
2 |
|
3 |
|
4 |
5 |
6 |
7 |
|
i=17nij |
|
|
|
|
|
||||||||
|
|
|
|
|||||||||
1 |
0 |
4 |
12 |
3 |
6 |
9 |
10 |
|
44 |
|||
2 |
4 |
0 |
7 |
5 |
4 |
11 14 |
|
45 |
||||
3 |
12 |
7 |
0 |
9 |
8 |
13 |
5 |
|
54 |
|||
R1 = 4 |
3 |
5 |
9 |
0 3 7 1 |
|
28 |
||||||
5 |
6 |
4 |
8 |
3 |
0 |
2 |
11 |
|
34 |
|||
6 |
9 |
11 13 |
7 |
12 |
0 |
2 |
|
44 |
||||
7 |
10 14 |
5 |
1 |
11 |
2 |
0 |
|
43 |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
Решение
Определим суммарное число связей каждой ячейки с остальными.
7
Минимальное значение nij = 28. Это означает, что четвертая ячейка
J=1
должна быть закреплена на первом установочном месте, находящемся с краю. Преобразуем исходную матрицу следующим образом. Исключим из
матрицы четвертую строку (ячейка закреплена, и на оставшиеся места претендовать не может), элементы четвертого столбца матрицы запишем со знаком « – » и, имитируя установку четвертой ячейки на 1-е место, переставим 4-й столбец на 1-е место в матрице. Преобразованная матрица имеет вид:
|
4 |
1 |
2 |
3 |
5 |
6 |
7 |
|
nij |
|
|
||||||||
1 |
-3 |
0 |
4 |
12 |
6 |
9 |
10 |
|
38 |
2 |
-5 |
4 |
0 |
7 |
4 |
11 14 |
|
35 |
|
3 |
-9 12 |
7 |
0 |
8 |
13 |
5 |
|
36 |
|
R2 = 5 |
-3 6 4 8 0 2 11 |
|
28 |
||||||
6 |
-7 |
9 |
11 13 |
12 |
0 |
2 |
|
40 |
|
7 |
-1 10 14 |
5 |
11 |
2 |
0 |
|
41 |
||
|
|
|
|
|
|
|
|
|
|
51
Минимальную сумму связей имеет 5-й элемент матрицы. Это означает, что 5-я ячейка закрепляется на втором месте.
Матрица преобразовывается так же, как и в предыдущем случае; определяется минимальное суммарное количество связей, закрепляется следующий элемент. Процесс длится до тех пор, пока все элементы не будут размещены.
Окончательное распределение элементов на позициях дано на рис.3.4. Если считать, что расстояние между рядом расположенными ячейками
рав-но условной единице длины, то для полученного размещения суммарная длина равна 345 единицам условной длины.
5. АЛГОРИТМ ОБРАТНОГО РАЗМЕЩЕНИЯ
Алгоритм включает такую последовательность действий [1, 3].
1. Вычислить матрицу расстояний D между позициями на плате. Элементы матрицы dij определяются по формуле:
dij = |xi - xj| + |yi - yj|.
2.Для каждой строки матрицы D определить суммарное значение элементов dij, стоящих в этой строке.
3.Для каждой строки матрицы R определить суммарное значение элементов
rij, стоящих в этой строке. Полученные значения – локальные степени элементов.
4.Упорядочить элементы t1 по возрастанию характеристики ri: tz1, tz2, …, t2n.
5.Упорядочить позиции lj по убыванию характеристики dj : ld1, ld2, …, ldn.
6.Выполнить размещение элементов в позиции p(tk) = lk, где 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 |
nij |
|
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 . |
|
|
|
|
|
|
|
|
|
|
52
Рис.3.4
Решение
По матрице связей R определим суммарную величину связей каждого
7
элемента с остальными: ri = rij (значения записаны справа от матрицы R).
J=1
Для данных позиций вычислим по (3.1) матрицу расстояний:
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
dij |
|
|
||||||||
|
|||||||||
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 определим суммарное расстояние каждой позиции до всех
7
остальных: di = dij (значение di записаны справа от матрицы D).
J=1
Упорядочим элементы ti по возрастанию ri: элементы 5-й (r5=3), 7-й (r7=4),
2-й (r2=5), 3-й (r4=5), 1-й ( r1=6), 3-й ( r3=6), 6-й ( r6=7).
Последовательность номеров позиции li запишем по убыванию di: позиции
1-я (d1=84), 7-я (d7=84), 2-я (d2=64) и 6-я, 3-я (d3=52), 5-я (d5=52), 4-я (d4=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).
53
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
8 |
9 |
|
|
10 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
1 |
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
13 |
|
|
|
16 |
|
|
|
|
|
|
|
|
|
|||
|
t5 |
|
t2 |
|
|
|
|
|
|
t1 |
|
|
|
|
t6 |
|
t3 |
|
t4 |
|
|
|
t7 |
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
6 |
|
|
|
|
|
|
|
14 |
|
|
|
17 |
|
6 |
|
8 |
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
7 |
|
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
18 |
|
|
|
|
12 |
|
|
|
9 |
|
|
|
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
55 |
|
|
|
11 |
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
10 |
|
|
|||||||
|
|
|
|
4 |
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
15 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Рис.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 |
|
aij |
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||
|
|
|
|
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) а ij = 156.
j=1 j=1
Для оценки эффективности алгоритма перемножим поэлементно матрицу связности R на матрицу расстояний D. Получим
54
|
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 |
|
A1 = 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) а ij = 220.
j=1 j=1
Следовательно, применение алгоритма обратного размещения позволило сократить в данном примере длину соединения на 64 условные единицы.
6.ДОМАШНЕЕ ЗАДАНИЕ
6.1.Ознакомиться с методами решения задачи размещения конструктивных элементов.
6.2.Изучить алгоритмы последовательного, предварительного и обратного размещений.
6.3.Подготовить данные к эксперименту.
6.4.Провести «ручное» размещение одного из узлов последовательным, предварительным и обратным методами.
7.ПОРЯДОК РАБОТЫ С ПРОГРАММОЙ «РАЗМЕЩЕНИЕ»
Алгоритмы размещения конструктивных элементов реализованы в пакете учебной САПР PSAPR на ПЭВМ программой “Размещение”. Программа позволяет определять:
-местоположение конструктивных элементов в монтажном пространстве по критерию минимальной суммарной длины соединений;
-суммарную длину соединений элементов, размещённых в заданные позиции поля.
Для запуска программы «Размещение» установить курсор на окно «Размещение элементов на плате» (оно будет в зелёной рамке) и нажать Enter. Появится рабочее поле графического редактора «Размещение» (рис.3.6).
Вверхней части экрана выводится информация, связанная с вводом элементов и цепей схемы, которая будет размещаться на плате.
55