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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

42
(
)
{
}
6,5,4,3,2,0,1
10
1
=== GLt
μ
:
.3,4,3,138501,3,,4,1
;7,5,4,2317601,3,2,,4,1
;,,3,1310301,3,6,,1
;,,3,135801,,6,4,1
;0,5
4
20
,4,2011901,3,,6,4,1
1
161
1
161
1
161
1
151
1
151
1
151
1
141
1
141
1
141
1
131
1
131
1
131
1
121
1
121
1
121
===+=−=
===+=−=
===+=−=
===+=−=
====+=−=
⋅⋅⋅⋅⋅⋅
⋅⋅⋅⋅⋅⋅
⋅⋅⋅⋅⋅⋅
⋅⋅⋅⋅⋅⋅
⋅⋅⋅⋅⋅⋅
γδ
γδ
γδ
γδ
γδ
nL
nL
nL
nL
nL
6
5
344
343
2
В соответствии с минимальным удельным приращением цикла
(
3,4
1
131
=
⋅⋅
γ
) в цикл включено множество номеров {4,6,3}. За последующие
два шага поочередно в цикл будут включены и последующие два
оставшихся элемента множества
{
}
5;2
2
=G . Однако для уменьшения числа
шагов необходимо проверить возможность включения в цикл большего
числа элементов, чем у маршрута
1
131 ⋅⋅
μ
, который соответствует
минимальному значению удельного приращения.
Цикл
1
131 ⋅⋅
μ
может быть заменен более расширенным циклом
1
11 ⋅⋅ j
μ
при
выполнении трех условий:
- удельное приращение
1
11 ⋅⋅ j
γ
является ближайшим к минимальному
1
131 ⋅⋅
γ
;
- новый цикл
1
11 ⋅⋅ j
μ
включает в себя рассматриваемый
1
131
1
121
1,3,6,4,11,3,2,6,4,1
⋅⋅⋅⋅
=⊃=
μμ
;
- новый цикл (
1
131 ⋅⋅
μ
) содержит в себе большее количество элементов
множества G
1
, чем
1
131 ⋅⋅
μ
:
13111 ⋅⋅⋅⋅
> nn
j
.
Этим условиям удовлетворяет только маршрут
1
121 ⋅⋅
μ
(j = 2), он
доминирует над маршрутом
1
131 ⋅⋅
μ
, ),(
1
1.3.1
1
1.2.1
μμ
f поэтому после первого
шага вместо
1
131 ⋅⋅
μ
получим
{}
5 ,201,3,2,6,4,1)( :
2
121
====
⋅⋅
GLL
μ
2t . (3.11)

Страницы