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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

52
Рис. 4. Блок-схема алгоритма решения обобщенной задачи коммивояжера
+
−
Н
ачало
Ввод:
ij
c=c
,
(
)
j
aa
=
, nm,
1
=
t
Начальные значения: 1,,1
1
m
t
=
μ
,
{
}
{
}
mnG
t
;1\;1= ,
(
)
(
)
11111
ccacaЭЭ
tt
+⋅+⋅==
μ
Нумерация интервалов:
}
}
4847648476
1
11
2
2
1
1
:
1
,,...,,,...,,,1
+
+−
=
t
tt
r
rr
r
t
jjjjjj
μ
1,1 +=∀ tr ,
t
G∈∀
γ
:
()
()
⎟
⎠
⎞
⎜
⎝
⎛
−+⋅
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎝
⎛
+⋅=
−−
∑∑
∈∈
rrrr
tt
jjjj
jij
jij
cccaca
,,,
,
t
r
11
11
γΔ
γγ
μμ
γ
γγ
Определение
tr
r
t
,
:
()
{}
()
{
}
()
tt
t
t
rtr
t
r
r
t
r
tr
t
r
G
tr
r
γγγγ
γ
,minminmin
1;11;1
⇒Δ=Δ=
⎭
⎬
⎫
⎩
⎨
⎧
Δ
+=
∈
+=
Номер
t
r
j
= включается в интервал
t
r цикла
t
r
μ
. Пересчет:
{}
t
r
tt
γμμ
U
1
1
1
=
+
,
{
}
t
r
tt
GG
γ
\
1
=
+
,
(
)
t
t
r
t
r
tt
ЭЭ
γ
Δ+=
+1
,
1+
=
tt
=
t
G
∅?
Вывод:
1,...,,...,,1
1
0
1
mj
t
==
μμ
,
(
)
t
ЭЭ =
0
1
μ
Конец
1°
2°
3°
4°
5°
6°
7°
8°
9°

Страницы