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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

41
качестве начального цикла (1
=
t
) в модифицированном методе
расширения цикла целесообразно брать цикл, составленный из двух
кратчайших маршрутов, которые
соединяются между собой включаемым
в нулевой цикл
kk, номером j. По аналогии с методом расширения цикла
можно записать
kjk
k
⋅⋅=
1
μ
, (метод расширения цикла
kjk
k
,,
1
=
μ
),
1;1 −= nk ,
k
j
≠
, (3.10)
где точка между индексами означает, что
k
,
j
и
k
соединены
кратчайшими маршрутами. Например, на основании табл. 14 имеем
3201319 ,3,,2,4,6,333
1
3
1
3
1
3
=−+===⋅⋅=
μμ
LL11 .
Совместно с принудительно включенным элементом 1=
j
в цикл
вошли элементы
{
}
2;4;6 ( 4
313
=
⋅⋅
n ), и, следовательно, удельный прирост
длины цикла (3.9) равен
.8432
313
=
=
⋅⋅
γ
В табл. 15 приведено множество решений, полученных методом
расширения цикла и модифицированным методом расширения цикла при
всех начальных циклах, образованных включением в цикл
kk, элемента
j
по кратчайшим маршрутам согласно (3.10) и табл. 14.
Из сравнения вариантов решений, записанных в табл. 9, можно
видеть, что средняя погрешность для модифицированного метода
расширения цикла (ММРЦ) снизится до 7,6 % и останется практически
прежней для метода расширения цикла (МРЦ) и совмещенного метода
(5,2 %), (правый столбец). Для обоих методов число итераций существенно
сокращается.
Если матрица
с не является полной (1
<
ϕ
), то решение может быть
получено
только модифицированным методом расширения цикла.
Решение также следует начать с нулевого цикла
kk,, поочередно
включая в него элементы
k
j
≠
. Порядок решения проиллюстрируем на
числовом примере, представленном в табл. 16 (рис. 1).
Множество кратчайших маршрутов вычислено согласно алгоритму
эстафетного метода (рис. 2) и записано в табл. 17. Начало цикла
выбирается произвольно, пусть 1
=
k
.
Для начального цикла 1;1
0
1
=
μ
с помощью табл. 17 запишем пять
циклов первого шага с последовательным включением в них элемента
1
Gj ∈ , соединяющего два кратчайших маршрута.
Согласно (3.7) и табл. 17 для первого шага имеем:

Страницы