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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

18
Итоговые результаты записаны в табл. 3, 2
=
t
.
Так как концевая вершина
36
=
≠
=
l
j
, то процесс продолжается.
Шаг 3=
t
:
-
столбец 6
=
j
удаляется из памяти ЭВМ (табл. 1; столбцы 4 –6);
-
момент старта из
6
A
5
0
6,16
==LT
c
записывается правее строки 6=i ;
-
согласно (2.4), (2.5) вычисляются элементы для 3
=
t
(табл. 2).
Из полученного столбца (табл. 2; 3
=
t
) следует, что очередные два
кратчайших маршрута имеют длины 6
0
5,1
=L и 6
0
5,4
=L ; концевые дуги:
5,4,1)5;4( ;5;1)5;1(
5,1
0
5,1
=⇒=⇒
μμ
(табл. 3). Так как пункт
3
A не
является концевым у найденного кратчайшего маршрута (53
≠=
l
), то
процесс продолжается (столбец 5
=
j
из табл. 1 удаляется).
Шаг 4=
t
.
Далее, для большей наглядности, процесс продолжен в табл. 4 и 5, из
которых убраны ненужные предыдущие записи:
-
момент старта
6
0
5,15
==LT
c
записывается правее строки 5=i на
одном уровне с нею;
-
согласно (2.3), (2.4) вычисляются моменты финиша лидеров всех
групп
t
Ii ∈ (табл. 5, 4=
t
; в группах
{
}
{
}
4
4;1 Ii ⊂= гонцов уже не осталось,
а в группах
{}
3;2 они ещё не стартовали);
-
из полученного столбца следует, что лидер
3,6
Л , определяющий
очередной кратчайший маршрут, финиширует в
заданной вершине
3
A
(
33
4
=== lt
).
Концевая дуга (6;3) позволяет построить кратчайший маршрут
3,6,4,1)3;6(6,4,1
0
3,1
=∪=
μ
при этом 8
0
3,1
=L ,
что записано в табл. 3. Процесс прекращается.
Примечания:
1. В табл. 5 выполнен шаг 5
=
t
, завершающий построение всего
множества кратчайших маршрутов из УИ
1
A . Это множество
представлено первой строкой табл. 9. Другие строки табл. 9
содержат аналогичные результаты, полученные при других УИ
i
A
(промежуточные вычисления опущены).
В диагональных клетках табл. 9 можно было записать
0
00
,
==
kkk
LL
, kk
kkk
,
00
,
==
μμ
. Однако вместо этого тривиального
результата в них записаны
запасные (кратчайшие из оставшихся)
кольцевые маршруты. Такие кратчайшие маршруты получаются,
если перед началом расчётов столбец
k
j
=
не удалять из табл. 1.

Страницы