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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

80
Таблица 33. Динамика процесса решения задачи коммивояжера
модифицированным методом расширения цикла
1=
t
,
{}
6,5,4,3,2
1
=G , 1;1
1
=
Н
μ
, 0
=
H
L
№
r
γ
rr
jj ,
1− rr
jj ⋅⋅
−
γ
1
),(
γδ
r
t
),(
γ
rn
t
),(
γε
r
t
t
L
t
G
1 2 3 4 5 6 7 8 9
1 1 2 1;1 1,2,6,1 1+9-0=10 2
5,0
10 3,4,5
2 1 3 1;1 1,4,5,3,4,1 14+18-0=32 3 10,7 32 2;6
3 1 4 1;1 1,4,1 5+4-0=9 1 9,0 9 2,3,5,6
4 1 5 1;1 1,4,5,4,1 12+17-0=29 2 14,5 29 2,3,6
5 1 6 1;1 1,2,6,1 4+6-0=10 2
5,0
10 3,4,5
6
2=
t
,
{}
5,4,3
2
=G , 1,6,2,1
1
1
=
μ
, 10
1
=
L
7 1 3 1;2 1,4,5,3,2 14+18-1=31 3
10,3 41
∅
8 1 4 1;2 1,4,1,2 5+5-1=9 1
9,0
19 3;5
9 1 5 1;2 1,4,5,4,1,2 12+18-1=29 2 14,5 39 3;4
10 2 3 2;6 2,3,2,6 21+21-3=39 1 39,0 49 4;5
11 2 4 2;6 2,4,1,2,6 10+8-3=15 1 15,0 25 3;5
12 2 5 2;6 2,6,5,6 22+17-3=36 1 36,0 46 3;4
13 3 3 6;1 6,4,5,3,4,1 20+18-6=32 3 10,7 42
∅
14 3 4 6;1 6,4,1 11+4-6=9 1
9,0
19 3;5
15 3 5 6;1 6,4,5,4,1 18+17-6=29 2 14,5 39 3
16
3=
t
,
∅=
3
G
, 1,6,2,3,5,4,1
2
1
=
μ
,
41)(
2
1
2
==
μ
LL
Примечания:
rr
rr
jj
jj
t
cLLr
,
0
,
0
,
1
1
)()(),(
−
−
−+=
γγ
μμγδ
, (5.2)
),(/),(),(
γγδγε
rnrr
ttt
= ,
),(
1
γδ
rLL
ttt
+=
. (5.3)
Следовательно, на первом шаге в цикл включается элемент
2=
γ
и
попутно с ним элемент 6=
j
(строка 1), или наоборот:
6=
γ
и 2
=
j
(строка 5). Полученный
расширенный цикл (строка 6) является исходным
для второго шага процесса.
Минимальное
удельное приращение длины цикла ),(
2
γε
r = 9,0
(табл. 33, 2=
t
, графа 7) обеспечивается при включении элемента
γ
= 4 в
интервал
r
= 1 (строка 8) или элемента
γ
= 4 в интервал
r
= 3 (строка 14).

Страницы