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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

4. Выделяется подмножество вершин элементов V
n
⊂ V, для которых ∆ R
i
> 0.
5. Из подмножества V
n
выбирается вершина v
m
с максимальным числом инцидентных ребер или с максимальным зна-
чением ∆R
i
, т.е. ∆ R
m
= max (∆ R
i
) и относительно нее множество V делится на подмножества
.и
mm
VV
′′′
В
m
V
′
включается вер-
шина v
m
и отстоящие от нее вершины на расстояние не больше l
гр
, в подмножество
m
V
′
′
– остальные вершины.
6. Формируется подмножество V
µ
, в которое включаются вершины, инцидентные длинным ребрам v
m
и V
n
/ v
µ
, т.е.
(
)
µµ
/vVVV
n
∩
′
′
=
. (4)
7. Для вершин v
j
∈ V
µ
подсчитывается число ребер )(
mj
VR
′
и )(
mj
VR
′′
, инцидентных соответственно вершинам подмно-
жеств
m
V
′
и
m
V
′′
, и затем разность
)()(
mjmjj
VRVRR
′′
−
′
=∆ . (5)
Определяется вершина v
µ
, для которой ∆ R
µ
= max (∆ R
j
).
8. Проверяется выполнение условия
0>
∆
+
∆
µ
RR
m
. (6)
Если оно имеет место, то производится перестановка вершин v
m
и v
µ
, иначе берется другая вершина из подмножества V
n
и повторяются п. 5 – 8.
9. Подсчитывается суммарная длина связей по формуле (1).
Далее на каждой итерации выполняются п. 3 – 9. Расчет прекращается, когда подмножество V
n
станет пустым или для
всех v ∈ V
n
условие (6) не выполняется.
Рассмотрим данный алгоритм на примере. Пусть в результате начального размещения получен граф G
(V, R), представ-
ленный на рис. 1. Требуется решить задачу размещения методом «длинных» и «коротких» ребер.
В соответствии с исходными данными, максимальная длина ребра l
max
= 5, в качестве граничного значения, определяе-
мого из соотношения (2), берется l
гр
≈ 2,5. Значения
i
R
′
,
i
R
′′
и ∆ R
i
для всех вершин, рассчитанные с использованием форму-
лы (3), представлены в табл. 1.
Таблица 1
Вершина 1 2 3 4 5 6 7 8 9 10 11 12
i
R
′
0 4 3 3 3 3 3 2 0 3 1 1
i
R
′′
2 2 0 3 0 1 1 0 3 0 2 3
∆ R
i
2 –2 –3 0 –3 –2 –2 –2 3 –3 1 2
Здесь вершина v
1
не содержит коротких ребер с l
1j
< l
гр
и
i
R
′
= 0, оба ребра r
1,11
и r
1,12
«длинные», поэтому
i
R
′′
= 2 и ∆ R
1
=
.2=
′
−
′′
ii
RR Аналогично определяются ∆ R
i
и для других вершин.
Вершины с ∆
R
i
> 0 образуют подмножество V
n
= {v
1
, v
9
, v
11
, v
12
}. Выбирается в качестве первой вершины v
m
пары (v
m
, v
µ
)
для перестановки вершина v
12
, имеющая максимальную степень (ρ (v
12
) = 4). Относительно нее множество V делится на под-
множества
12
V
′
= {v
4
, v
7
, v
8
, v
10
, v
11
, v
12
} и
12
V
′′
= {v
1
, v
2
, v
3
, v
5
, v
6
, v
9
}. В соответствии с формулой (4) формируется подмножест-
во
()
{
}
{
}
911191121212
,,,\ vvvvvVvVVV
n
=
∩
′
′
=
∩
′
=
µ
.
Для вершин v
1
и v
9
определяются числа R
1
(
12
V
′
) = 2, R
1
(
12
V
′
′
) = 0, R
9
(
12
V
′
) = 3, R
9
(
12
V
′′
) = 0 и далее по формуле
(5) подсчитываются их разности

Страницы