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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

Содержание отчета
6.
Название лабораторной работы.
7.
Цель работы.
8.
Исходные данные.
9.
Составленная по электрической схеме матрица смежности.
10.
Решение задачи размещения элементов схемы в монтажном пространстве коммутационной платы последовательно-
итерационным алгоритмом.
11.
Вывод по результатам работы.
12.
Список использованной литературы.
КОНТРОЛЬНЫЕ ВОПРОСЫ
5. Что понимается под монтажным пространством?
6.
Перечислить основные этапы последовательно-итерационного алгоритма и дать их краткое описание.
7.
Для чего определяются и что характеризуют коэффициенты связности?
8.
Как взаимосвязана средняя длина и «центр тяжести»?
9.
Объяснить, могут ли произведенные перестановки элементов в ходе итерационного этапа привести к увеличению
критерия (1) по сравнению с его значением после первоначального размещения?
Лабораторная работа 7
РЕШЕНИЕ ЗАДАЧИ РАЗМЕЩЕНИЯ ИТЕРАЦИОННЫМ
АЛГОРИТМОМ С ИСПОЛЬЗОВАНИЕМ МЕТОДА
«ДЛИННЫХ» И «КОРОТКИХ» РЕБЕР
Цель работы. Ознакомиться с итерационным алгоритмом и решить задачу размещения радиоэлектронных элементов в
монтажном пространстве методом «длинных» и «коротких» ребер.
Исходные данные. Схема электрическая принципиальная, представленная мультиграфом G (V, R) с числом вершин n.
Требуется изучить постановку задачи размещения элементов схемы и итерационный алгоритм решения, основанный на
методе «длинных» и «коротких» ребер; получить вариант задания, решить задачу размещения элементов схемы в монтаж-
ном пространстве коммутационной платы с числом посадочных мест m = n итерационным алгоритмом по минимуму сум-
марной длины соединений.
Методические указания по выполнению работы
В качестве исходных данных для решения задачи размещения рассматриваются схема соединения элементов, заданная в
виде графа G (V, R), где V = {v
1
, …, v
n
} – множество конструкционных элементов, R = {r
1
, …, r
p
} – множество связей между
ними и T = {t
1
, …, t
m
} – множество установочных (посадочных) мест на коммутационной плате, причем T ≥ V.
Требуется так разместить вершины V в посадочных местах T, чтобы минимизировать выбранный критерий оптимально-
сти. Критерием может служить, в частности, минимум суммарной длины соединений, минимум внутрисхемных линий, ми-
нимум соединений, длина которых превышает заданную величину и др. Наиболее часто в задачах размещения минимизиру-
ется суммарная длина соединений
∑
=
=
=
m
j
i
ijij
SlQ
1
,1
2
1
, (1)
где l
ij
– расстояние между i-м и j-м установочными местами, в которых расположены соответствующие конструктивные эле-
менты; S
ij
– число кратных связей между элементами.
Основная идея алгоритма заключается в том, что после начального размещения в виде графа G
(V, R) для каждой вер-
шины v
i
∈ V множество R
i
инцидентных ребер разбивается на два подмножества:
i
R
′
– «короткие» ребра и
i
R
′
′
– «длинные»
ребра. На основе такого деления определяются пары вершин, перестановки которых приводят к уменьшению суммарной
длины связей, т.е. критерия (1).
Деление ребер на «короткие» и «длинные» производится с помощью граничной длины l
гр
. Если длина связи l
ij
между
вершинами v
i
и v
j
меньше l
гр
, ребро r
ij
считается «коротким» (r
ij
∈
i
R
′
). В случае, когда l
ij
> l
гр
, то ребро r
ij
относят к «длин-
ным» (r
ij
∈
i
R
′′
). Приближенно l
гр
равна половине наибольшей длины связи l
max
между элементами. Более точно l
гр
можно
определить из соотношений
(
)
(
)
(
)()
.
,15,01 ,15,01
гр
maxmaxmax
lll
lllllll
′′
<<
′
+
<+
′
′
′
′
+
<
+
′
′
(2)
Рассмотрим основные этапы алгоритма.
1. Проводится произвольное размещение элементов v ∈ V в установочные места t ∈ T монтажного пространства, напри-
мер, v
1
→
t
1
, v
2
→
t
2
и т.д.
2. Рассчитывается значение граничной длины l
гр
.
3. Для каждой вершины v
i
∈ V множество инцидентных ребер R
i
разбивается на подмножества «коротких»
i
R
′
и «длин-
ных»
i
R
′′
ребер и подсчитываются разности
iii
RRR
′
−
′′
=∆
, (3)
где
i
R
′
,
i
R
′′
– число ребер в множествах
i
R
′
,
i
R
′′
(мощность множеств).

Страницы