Элементарные решения неэлементарных задач на графах. Берзин Е.А. - 19 стр.

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

21
2.3. Алгоритм эстафетного метода (ЭМ)
Рассмотренная схема расчётов может быть представлена в форме
алгоритма, для описания которого введем дополнительно некоторые
обозначения:
−
t
G
множество номеров вершин
j
A , к которым при выполнении
t
-го
шага (итерации) процесса ещё не найдены кратчайшие маршруты
(например,
{
jG ∀=
1
}
)k≠
;
−
t
i
G множество номеров вершин
j
A , к которым при выполнении
t
-го
шага от вершины
i
A существует конечная дуга (0>
ij
c ) и, следовательно,
к этим вершинам ещё возможно построение маршрута
tt
ij
t
i
IiGjcjG ∈∈>= },,0|{
,
где
−
t
I
множество номеров вершин
i
A
(УИ
i
A
), от которых за все t шагов
стартовали группы гонцов (например, }{
1
kI = );
{}
−
t
j множество номеров концевых вершин
j
A , к которым на
t
-м
шаге были найдены кратчайшие маршруты;
Проиллюстрируем динамику работы алгоритма ЭМ при построении
кратчайшего маршрута
0
3,1
μ
, блок-схема которого представлена на рис. 2.
Исходной информацией является матрица
c (табл. 1) и концевые
вершины
()
−= )3;1(;lk
пункт
0
1. Для первого шага ;1( =
t
пункт )2
0
вычисляются начальные значения текущих величин:
{}
{
}
{}
{
}{}
.0 ,1 ,6,5,46,5,4,3,2 ,0| ,6,5,4,3,2 :3
1
1
1
1
1
10
===∈>==
c
j
TIjcjGG
Начало отсчёта (время старта каждой группы гонцов) не зависит от
номера шага
t и при «ручных» расчётах последовательно в ходе процесса
записывается справа от табл. 1.
Множество концевых дуг
{
}
),(
t
ji лидеров стартовавших групп для
шага 1=
t
(}1{}{
1
== kI ) согласно
0
4 равно:
).4;1(),(3)8;6;3min();;(min)(min :1
16,15,14,1,1
Gj
1
1
=⇒
=
=
==
∈
jicccci
j
Концевые дуги ),(
t
ji и их длины
t
ij
c запоминаются в памяти ЭВМ
(при «ручных» расчётах записываются в табл. 2, 1
=
t
).
Поскольку множество концевых дуг лидеров не пусто
(
0
5 -), то это означает, что к некоторым вершинам могут быть построены
маршруты.

Страницы