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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

39
Из (3.7) видно, что для вычисления приращений исходной
информацией будут являться кратчайшие маршруты
0
kj
μ
и их длины,
вычисляемые по мере необходимости эстафетным методом (рис. 2), и
длины дуг
ij
c (табл. 13). Для иллюстрации удобно кратчайшие маршруты и
их длины вычислить заранее и поместить в совмещенной матрице
00
kjkj
L
μ
(табл. 14). Длины дуг
ij
c записаны в табл. 13. Например, для начального
цикла
3,6,3 согласно табл. 14 имеем
21 ==
tt
rr
.5,10,21162116163,6,,4,6,10,1035836,,3
,5,1016224163,2,,6,7,6,20316736,5,2,,6,3
,5,1016206163,,4,6,7,6,20314936,5,,4,6,3
,,γ
,13161316163,,2,4,6,7,10,323161936,3,,2,4,6,3
2
356
2
356
1
653
1
653
2
346
2
346
1
643
1
643
2
326
2
326
1
62.3
1
623
2
.316
2
316
1
643
1
613
==−+=−===−+=−=
==−+=−===−+=−=
==−+=−===−+=−=
==−+=−===−+=−=
⋅⋅⋅⋅⋅⋅⋅⋅
⋅⋅⋅⋅⋅⋅⋅⋅
⋅⋅⋅⋅⋅⋅⋅⋅
⋅⋅⋅⋅⋅⋅⋅⋅
γδγδ
γδγδ
γδγδ
δγδ
55
44
22
3411
LL
LL
LL
LL
(3.8)
Принудительно включаемый в r-й интервал текущего цикла элемент j
(3.7), разделяющий кратчайшие маршруты
0
kj
μ
и
0
ji
μ
, выделен в (3.8)
жирным шрифтом. Длины соответствующих кратчайших маршрутов
берутся из табл. 14, например
191,2,4,6,3
0
13
0
==
⋅⋅
LL
jk
, 166,3,1
0
61
==
⋅
LL ,
3
6,3
=c (табл. 13). Однако теперь совместно с принудительно включаемым
в цикл элементом
j
в цикл могут быть попутно включены и некоторые
другие элементы из множества
t
G
.
Таким образом, наряду с показателем
t
ijk
⋅⋅
δ
необходимо учитывать и
другой показатель
t
ijk
n
⋅⋅
– общее количество номеров вершин,
{}
t
Gj ⊂ ,
которые впервые включаются в цикл на t-м шаге. Например, при
вычислении
1
613 ⋅⋅
δ
(3.8) наряду с элементом j = 1 в цикл будет включено и
множество элементов
{} { }
1
4;2 Gj ⊂= .
Указанные два частных критерия могут быть объединены в один:
среднее приращение длины цикла, приходящееся на каждый впервые
включенный элемент
t
Gj ∈
,
t
ijk
t
ijk
t
ijk
n
⋅⋅⋅⋅⋅⋅
=
δγ
,
t
Gj ∈
,
t
r
∀
. (3.9)
Вычисленный
удельный прирост длины цикла (3.9) эквивалентен
{
}
.
5,4,2,1,3,6,3;
11
=
=
G
L
1t

Страницы