Об оптимизации трассы прокладки оптического кабеля
7
близких к оптимальному трасс прокладки применяется алгоритм, ос-
нованный на методе последовательного анализа вариантов [5] и ис-
пользовании правила отбраковки бесперспективных вариантов до
получения окончательного решения.
Как известно, в алгоритме Дейкстры для поиска кратчайшего пу-
ти вершинам графа приписывают временные или постоянные помет-
ки. Они определяют для вершины верхнюю границу длины пути от
i
вершины до текущей. Величины временных пометок вершин посте-
пенно уменьшаются. Значение пометки определяет возможную дли-
ну пути от начальной до этой вершины. На каждом шаге алгоритма
только одна из пометок с минимальным значением на рассматривае-
мом уровне выбирается в качестве постоянной. Другими словами,
значение пометки является длиной кратчайшей трассы из
i
вершины
в текущую вершину.
Введем следующие обозначения:
V
(
s
) — множество ребер, вхо-
дящих или выходящих из вершины
s
(
V
(
s
)
⊆
W
); |
V
(
s
)| — мощность
множества;
p
sj
— пометки вершины
s
∈
A
,
j
= 0, 2, …, |
V
(
s
)|–1;
B
—
множество вершин с постоянными пометками для
j
= 0.
Алгоритм первого этапа
поиска оптимальной трассы прокладки
ОК состоит из шести шагов.
Шаг 1. Присвоить пометке начальной вершины
p
i0
= 0 и считать
постоянной. Для всех остальных вершин
s
∈
A
/{
i
} установить
p
s0
= ∞ и
считать эти пометки временными. Установить
d
=
i
;
B
= {
i
}. Обно-
вить метки.
Шаг 2. Для всех вершин
s
∈
V
(
d
) вычисляются новые значения
( )
,
0, 2, ...,
1
sj
dj
ds
p p t j
V s
= + =
−
.
(1)
Таким образом, для каждой вершины будет определена длина
трассы прокладки для всех возможных трасс от исходной вершины
i
до вершины
s
.
Для
j
= 0 временные пометки вычисляют, используя выражение
(
)
0
0
0
min ,
s
s
d
ds
p
p p t
⎡
⎤
=
+
⎣
⎦
,
(2)
и превращают эти пометки в постоянные.
Шаг 3. Среди всех вершин с временными пометками
s
∈
A
\
B
найти
такую вершину
k
, для которой значение пометки минимально
p
k
0
= min
p
s
0
.
Шаг 4. Считать пометку
p
k
0
постоянной и установить
d
=
k
. В
множество
B
добавить вершину
k
.
Шаг 5. Если
d
≠
j
, то перейти к шагу 2. Если
d
=
j
, то
p
k
0
является
длиной оптимальной трассы
R
ij
из вершины
i
в вершину
j
.
