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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

40
главному критерию
()
k
L
μ
, т.к. при constn
=
минимизация среднего
расстояния между вершинами
(
)
nL
k
μ
равносильна минимизации его
длины
)(
k
L
μ
.
Из (3.8) следует, что
{
}
{
}
(
)
11
316
1
316
1,2,4 ,3 ,13 Gjn ⊂===
⋅⋅⋅⋅
δ
и 3,4
3
13
1
316
≈=
⋅⋅
γ
.
Найденный
удельный прирост является минимальным для всех
1
Gj ∈ и интервалов
1
r
(3.8). Поэтому на первом шаге в интервал с
номером 2
1
==
r
r
t
между его левой (j = 6) и правой (j = 3) границами
включаются элементы
{}{ }
124 ,,=
t
j
(см. 3,,,,6 124L ,
1
316 ⋅⋅
δ
в (3.8)).
После пересчета текущих величин ко второму шагу процесса имеем
{
}
5 ,323,1,2,4,6,3 :
22
=== GL2t .
Так как осталось включить в цикл только один элемент, то согласно
(3.9) для каждого интервала имеем
2
5
2
5
ikik ⋅⋅⋅⋅
=
δγ
:
,2021111,214916,
321
2
2.5.4
2
4.5.6
2
6.5.3
222
=−+==−+==
===
δδδ
10
rrr
.23132115 ,1310149
5 4
2
3.5.1
2
1.5.2
22
=−+==−+=
==
δδ
rr
Поскольку минимальное приращение соответствует включению
элемента 5
2
=j в первый интервал, то согласно (3.7) и табл. 14 в
развернутом виде имеем
103586,5,3
6,36,3
0
6,5
0
5,3
2
653
=−+=−=−=
⋅⋅
cLcL
μμδ
U ,
т.е. в интервал 1
2
=
r
, (3 ÷ 6) включается только элемент 5
2
=j .
Окончательно получаем
423,1,2,4,6,,3
=
5L .
Исходный цикл влияет на точность решения, а в модифицированном
методе расширения цикла он будет влиять и на объем вычислений. В

Страницы