Автоматизация конструкторского и технологического проектирования. Литовка Ю.В. - 9 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

9
r(a
1
),r(a
2
),r(b
2
),r(b
1
) - соответственно номера каналов, в которых находятся лу-
чи a
1
b
1
, a
2
b
2
.
Рассмотрим несколько частных случаев.
1. Аппараты А и В размещены в одном продольном ряде. Для соедине-
ния аппаратов в этом случае достаточно выполнить условия r(a
1
) = r(b
2
) или
r(a
3
) = r(b
3
), т.е. трассировка заканчивается, как только лучи попадают в один
и тот же канал.
2. Аппараты А и В размещены в
одном поперечном ряде (по ширине
цеха). При этом случае должно выполняться условие:
r(a
2
) = r(b
2
) или r(a
4
) = r(b
4
)
3. Аппараты А и В размещены в одной строительной клетке: допуска-
ется прямое соединение аппаратов, без выхода в канал.
Как правило, получается два варианта трассировки. Выбор лучшего ва-
рианта осуществляется по критерию минимальной длины трассы. Если длина
трасс одинакова, то предпочтение отдается трассе с меньшим числом пово-
ротов.
Алгоритм прокладки трасс
для разветвленных соединений выпол-
няется в два этапа:
На первом этапе с использованием алгоритма Краскала производится
построение кратчайшего связывающего дерева Прима.
На втором этапе для каждого ребра дерева Прима формируется множе-
ство реализующих его вариантов S-ребер (под S-ребром понимается цепь ре-
бер в ортогональном графе Q, имеющая началом и концом две
вершины V
i
,
V
j
), покрывающих минимальное дерево Штейнера и выбираем S-ребро,
обеспечивающее минимальную суммарную длину дерева Штейнера. Этот
процесс повторяется для всех разветвленных соединений.
Алгоритм построения кратчайшего связывающего дерева (задание
8) состоит в следующей последовательности.
1. Для заданного подмножества вершин К
1
, на которых надо построить
кратчайшее связывающее дерево, вычисляется расстояние между всеми вер-
шинами и заносится в матрицу
x
ij
xkkdD
′
= .
2. Определяется ребро с минимальным весом.
3. Определяется следующее ребро. При этом новое ребро не должно сов-
падать с уже выбранным.
Процесс повторяется до построения
)1k(
−
′
-го ребра.
Полученный список ребер и является искомым деревом Прима с мини-
мальным весом. Проиллюстрируем сказанное на примере построения крат-
чайшей связывающей сети в ортогональном графе (рис 2).
Пусть надо построить схему соединений на 3-х вершинах V
11
, V
25
, V
32
.
Для простоты расстояние между двумя смежными вершинами возьмем рав-
ное 1.
1. Вычисляем расстояние между вершинами:
d(V
11
, V
25
)=5; d(V
11
, V
32
) =3; d(V
25
, V
32
)=4.
2. Определяем ребра кратчайшего связывающего дерева:

Страницы