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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

38
Таблица 14. Совмещенная матрица
0
0
kj
kj
L
μ
j
k
1 2 3 4 5 6
1
16
1,2,1
6
2;1
13
3;1
7
4,2,1
15
5,2,1
16
6,3,1
2
10
1;2
3
2,4,2
20
3;2
1
4;2
9
5;2
14
6,5,2
3
19
1,2,4,6,3
9
2,4,6,3
19
3,6,3
7
4,6,3
8
5;3
3
6;3
4
12
1,2,4
2
2;4
22
3,2,4
3
4,2,4
11
5,2,4
16
6,5,2,4
5
14
1;5
11
)2,5(2,4,6,5
21
3,6,5
9
4,6,5
20
5,2,4,6,5
5
6;5
6
16
1,2,4,6
6
2,4,6
16
3;6
4
4;6
16
5,4,6
19
6,3,6
3.3. Модифицированный метод расширения цикла,
примеры вычислений и эффективность метода
Основное отличие модифицированного метода расширения цикла от
метода расширения цикла состоит в том, что на каждом
t
-м шаге процесса
при пробном включении
j
-й (
t
Gj ∈ ) вершины в интервал
(
k
– i ) вместо дуг ),(
j
k
и ),( i
j
при вычислении приращения
t
ijk
⋅⋅
δ
[см. формулу (3.1)] используются кратчайшие маршруты
0
kj
μ
и
0
,ij
μ
:
(
)
(
)
(
)
t
kijikjkijikj
t
ijk
GjcLcLL ∈−=−+=
⋅⋅
,
0000
μμμμδ
U , (3.7)
где точки в (3.7) между
k
,
i
;
j
,
i
отражают тот факт, что
соответствующие вершины
соединены через кратчайшие маршруты.
Использование (3.7) предполагает отказ от жесткого условия об
однократности включения каждой вершины в цикл, а следовательно,
создает дополнительные условия для уменьшения его длины.
Вычисление приращений по формуле (3.7) обеспечивает и
выполнение отмеченного выше необходимого условия оптимальности, что
исключает необходимость его проверки. Проиллюстрируем порядок
расчетов на числовом примере табл. 13.

Страницы