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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

15
Применительно к графу (табл. 1), при старте гонцов из УИ
1
A первым
прибудет (на первой итерации 1
=
t
) гонец в пункт
4
AA
t
j
=
, пройдя при
этом путь длиной
3)8;6;3min()(min
1
=
=
j
j
c к моменту
3
4
1
==
c
j
TT
.
Если при этом номер достигнутой вершины совпадает с нужным
(т.е. 4=
l
), то кратчайший путь найден на первой же итерации. При этом
гонец пройдет по маршруту
4;1
4,1
=
μ
, а его длина
4,1
L будет равна
3)(
4,14,14,1
=== cLL
μ
. Столбец 4=
j
из табл. 1 удаляется.
Однако если найденный кратчайший маршрут не является искомым
(
lj
t
≠= 4
1
), то к остальным гонцам, стартовавшим из
k
A , добавляется новая
партия гонцов, получившая эстафету в момент 3
4
=
T и стартующая из
пункта
4
A ко всем ещё не «оповещённым» пунктам (рис. 1;
56
, AA ).
Момент старта 3
4
=
c
T удобно записывать справа от строки 4=i
(табл. 1).
Из новой группы выделяется лидер – он первым из этой партии
прибудет к своему пункту (
6
A ). Так как этот лидер стартовал через
3
4
=
c
T ед. времени после старта первой группы, то при единой системе
отсчёта времени он прибудет в
6
A в момент времени
523
6,446
=
+=+= cTT
ед.
Новый лидер в первой стартовавшей группе прибудет в
5
A позднее – в
момент 6
5,15
== cT
c
ед. (табл. 1). Следовательно, очередной кратчайший
маршрут будет иметь длину
5
6,1
=
L
ед., при этом его концевая дуга (4;6)
закончится в вершине
6
A
(табл. 2; 2
=
t
). Чтобы найти новый кратчайший
маршрут, необходимо его концевую дугу (4;6)
достроить слева
кратчайшим маршрутом, который к данной итерации уже был найден
(
4;1
0
4,1
=
μ
). Очередной кратчайший маршрут запишется (табл. 3):
6;4;16;44;1
0
6,4
0
4,1
0
6,1
=∪=∪=
μμμ
. (2.2)
Если граничная вершина полученного кратчайшего маршрута (
6
A )
совпадает с искомой (т.е.
lj
6
2
), то процесс оканчивается. При
l
≠
6
столбец 6
=
j
из табл. 1 удаляется, и цикл повторяется до выполнения
условия
lj
t
= , где −
t
j номер граничной вершины кратчайшего маршрута,
который будет найден на текущей итерации
t
.

Страницы