САПР в задачах конструкторского проектирования. Тюрин И.В. - 16 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

На втором этапе на каждой итерации выбирается элемент с максимальным значением средней длины связей; определя-
ется посадочное число, на которое его желательно разместить и выбирается наилучший вариант для перестановки. Следова-
тельно, идея итерационной части заключается в улучшении размещения, полученного на предыдущем шаге на основе пере-
становок элементов.
Рассмотрим решение задачи размещения последовательно-итерационным алгоритмом на примере. Необходимо размес-
тить элементы схемы, мультиграф которой
G (V, R) приведен на рис. 1, с числом вершин дn = 9 в заданное монтажное про-
странство коммутационной платы, показанное на рис. 2 с числом посадочных мест
m = n = 9.
Решение задачи начинается с представления исходного мультиграфа матрицей смежности:
Последовательный этап. В условии задачи не задано закрепление отдельных вершин за конкретными посадочными
местами, поэтому определяем вершину
v
1
в позицию t
1
, а далее последовательно размещаем остальные элементы. Для этого
вычисляем коэффициенты связности
K (v
1
) элементов v
2
, …, v
9
с размещенным элементом v
1
по формуле (4). Так, коэффициент
связности для элемента
v
2
равен K
1
(v
2
) = 2S
21
– ρ (v
2
) = 0 – 4 = –4, для элемента v
3
K
1
(v
3
) = 2S
31
– ρ (v
3
) = 0 – 3 = –3 и т.д. Значе-
ния
K
1
(v
i
) приведены дополнительным столбцом в матрице смежности. Так как максимальное значение коэффициента связ-
ности с
v
1
имеют элементы v
3
, v
4
и v
8
, то их целесообразно разместить в соседние с элементом v
1
ячейки. Остались неразме-
щенными элементы
v
2
, v
5
, v
6
, v
7
, v
9
. Для них аналогично определяются коэффициенты связности с ранее размещенными эле-
ментами
v
1
,
v
3
, v
4
и v
8
, т.е. K
2
(v
2
) = 2 (S
21
+ S
23
+ S
24
+ S
28
) – ρ (v
2
) = 4 – 4 = 0; K
2
(v
5
) = (S
51
+ S
53
+ S
54
+ S
58
) – ρ (v
5
) = 0 – 8 = –8 и т.д. Эти
значения
K
2
(v
i
) также приведены в столбце при матрице S. Максимальную связность с v
1
, v
3
, v
4
, v
8
имеет элемент v
7
, и его раз-
мещаем в очередную свободную позицию монтажного пространства и т.д. Таким образом, в результате выполнения после-
довательного этапа получено первоначальное размещение элементов, показанное на рис. 3.

Страницы