Информационный анализ и автоматизированное проектирование трехмерных компоновок оборудования химико-технологических схем. Малыгин Е.Н - 26 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

От каждого аппарата будем распространять два луча:
А
1
– ОТ ТОЧКИ А
1
ВПРАВО И А
2
– ОТ ТОЧКИ А
2
ВВЕРХ;
b
1
– от точки B
3
влево и b
2
– от B
4
вниз.
Если аппарат
В будет левее А, то путевые координаты вправо и влево надо поменять местами. Одновре-
менно будем распространять все четыре луча до встречи двух разноименных лучей в точке
V
∗
, либо до блоки-
рования всех лучей. Продвижение лучей по каналу будем осуществлять с шагом соответствующим расстоянию
между каналами.
Для реализации соединения воспользуемся матрицей пересечения каналов
попрп
,
kk
jiP ,
где
=
,1
;0
ij
P 0 – не пересекаются, 1 – пересекаются.
Распределение лучей закончится, когда после очередного шага будет выполнено одно из условий:
(
)
(
)
1
21
=
brar
P или
(
)
(
)
1
22
=
brar
P , где )(),(),(),(
1221
brbrarar – соответственно номера каналов, в которых нахо-
дятся лучи
.,,
2211
baba Рассмотрим несколько частных случаев:
1. Аппараты
А и В размещены в одном продольном ряде. Для соединения аппаратов в этом случае доста-
точно выполнить условия
)()(
21
brar = или )()(
33
brar = , т.е. трассировка заканчивается как только лучи попа-
дают в один и тот же канал.
2. Аппараты
А и В размещены в одном поперечном ряде (по ширине цеха).
В этом случае должно выполняться условие:
)()(
22
brar = или )()(
44
brar = .
3. Аппараты А и В размещены в одной строительной клетке.
Для этого случая допускается прямое соединение аппаратов, без выхода в канал.
Как правило, получается два варианта трассировки. Выбор лучшего варианта осуществляется по критерию
минимальной длины трассы. Если длина трасс одинакова, то предпочтение отдается трассе с меньшим числом
поворотов.
Алгоритм прокладки трасс для разветвленных ТП.
Решение задачи выполняется в два этапа:
На первом этапе с использованием алгоритма Краскала производится построение КСД-дерева Прима.
На втором этапе для каждого ребра дерева Прима формируется множество реализующих его вариантов
S-
ребер (под
S-ребром понимается цепь ребер в ортогональном графе Q, имеющая началом и концом две верши-
ны
ji
VV ,
), покрывающих минимальное дерево Штейнера и выбираем S-ребро, обеспечивающее min суммар-
ную длину дерева Штейнера. Этот процесс повторяется для всех разветвленных ТП.
Алгоритм построения КСД.
1. Для заданного подмножества вершин
t
k , на которых надо построить КСД вычисляется расстояние ме-
жду всеми вершинами и заносится в матрицу
xt
ij
xkkdD = .
2. Определяется ребро с минимальным весом.
3. Определяется следующее ребро. При этом новое ребро не должно совпадать с уже выбранным.
Процесс повторяется до построения
(
)
1−
t
k
-го ребра.
Полученный список ребер и является искомым деревом Прима с минимальным весом. Проиллюстрируем
сказанное на примере (рис. 2.2).
Пусть надо построить СС на 3-х вершинах
.,,
322511
VVV Для простоты расстояние между двумя смежными
вершинами возьмем равным 1.
1. Вычисляем расстояние между вершинами:
()
(
)
(
)
4,;3,;5,
322532112511
=
=
= VVdVVdVVd .
2. Определяем ребра КСД.
1)
3211
VV − 2)
2532
VV −
3. Формируем два варианта
S-ребер для каждого из ребер
3211
VV
−
и
2532
VV
−
по каналам прямоугольной
зоны, внутри которой лежат вершины. Это варианты:
32312111
,,, VVVV и
32221211
,,, VVVV для ребра
3211
VV
−
.
25232232
,,, VVVV и
2535343332
,,,, VVVVV для ребра
2532
VV
−
.

Страницы