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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

24
Уточнение множества
t
G равносильно удалению соответствующих
столбцов в матрице
c при «ручных» расчётах.
Номера концевых вершин
j
A , к которым ещё возможно построение
маршрута на втором шаге (2
=
t
) процесса из пунктов старта
i
A
}4;1{
2
=∈ Ii , найдутся по рекуррентной формуле (пункт
0
9
)
⎩
⎨
⎧
====
====
=
}.6;5{}4{\}6;5{}{\ :4
},6;5{}4{\}6;5;4{}{\ :1
1
1
4
2
4
1
1
1
2
1
2
jGGi
jGGi
I
Величины задержек моментов старта гонцов остаются прежними для
всех стартовавших ранее групп (
t
I
i
∈
), а для стартовавших вновь (поле
t
-го шага процесса) задержка численно равна длине кратчайшего
маршрута до соответствующего УИ
i
A (}{
t
ji
∈
). Для 2=
t
согласно
0
9
имеем
.3
0
4,14
1
=== LTT
cc
j
Далее осуществляется переход к шагу 2
=
t
(пункт
0
10 ), и весь цикл
повторяется уже с двумя стартовавшими группами (}4;1{
2
=I ).
Согласно
0
4 определяются концевые дуги лидеров )},{(
t
ji (табл. 2;
2=
t
). Так как найденное множество дуг не пусто (
−
0
5), то определяется
(
0
6) концевая дуга очередного кратчайшего маршрута (или множество
}{
t
j ), строится сам кратчайший маршрут (
0
7) и находится его длина
5
0
6,1
=L (табл. 2; 2
=
t
;
0
7), полученный результат при «ручных» расчётах
заносится в табл. 3, 2=
t
.
Поскольку искомый кратчайший маршрут не найден
( −∉=
0
8 },6{3l ), то после пересчёта текущих величин (
0
9) выполняется
очередная итерация (
0
10 , 3
=
t
), время задержки новой группы гонцов,
стартующей от УИ
6
A
5
6
=
c
T , записано справа от строки 6=i в табл. 1.
На итерации 3=
t
согласно
0
6 множество концевых дуг содержит уже
три элемента:
)}3;6(),5;4(),5;1{()},{(
33
=ji (табл. 2; 3
=
t
).
Две дуги соответствуют более коротким маршрутам
(
83,6,4,16
0
5,1
=<= LL ) и ведут к одному УП
5
A . Значит, к вершине
5
A

Страницы