Дискретная математика. Громов Ю.Ю - 87 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

87
ется равным ∞, так как гамильтонов контур должен быть простым по оп-
ределению. Заметим, что в дальнейшем номера b и c считаются эквива-
лентными.
Аналогично приведению матрицы А, приводится матрица А
1
и опре-
деляется константа приведения h
1
. Нижняя граница множества
)1(
)1(
1
−nZ
вычисляется путём прибавления к нижней границе его непосредственно-
го предшественника Z(n) константы h
1
:
1
)1(
1
)()( hZZ +γ=γ
.
Для приведённой матрицы
1
~
A
составляется множество D дуг, отве-
чающих её нулевым элементам, определяется следующая дуга ветвления
(p, q) и вычисляется нижняя граница множества
)2(
)2(
2
−nZ
:
pq
ZZ α
′
+γ=γ )()(
)1(
1
)2(
2
.
Затем матрица
1
~
A
стягивается по выбранной дуге ветвления (p, q) и
получается матрица А
2
порядка (n − 2), соответствующая множеству
)2(
)2(
1
−nZ
, а номера p и q полагаются эквивалентными.
Нижняя граница множества
)2(
)2(
1
−nZ
вычисляется путём прибав-
ления к нижней границе его непосредственного предшественника
)1(
)1(
1
−nZ
константы приведения матрицы А
2
:
2
)1(
1
)2(
1
)()( hZZ +γ=γ
.
Подобным образом процесс ветвления и вычисления нижних границ
множеств контуров продолжается до тех пор, пока не будет зафиксирован
последний элемент (x, y) множества
)1(
)1(
1
−n
Z
, составленного из дуг (b, c),
(p, q), ..., (x, y) гамильтонова контура π
1
, и вычислена нижняя граница
)(
)1(
1
−
γ
n
Z
, равная длине σ(π
1
) этого контура.
Если σ(π
1
) окажется не больше любой из нижних границ
)(
)1(
2
Zγ
,
)(
)2(
2
Zγ
, ...,
)(
)2(
2
−
γ
n
Z
множеств, соответствующих другим конечным уз-
лам дерева (см. рис. 48), то контур π
1
следует считать искомым опти-
мальным контуром π
0
. В противном случае необходимо произвести ветв-
ление тех узлов
)(
)(
2
knZ
k
−
, для которых σ(π
1
) <
)(
)(
2
k
Zγ
, получить кон-
туры π
2
, ..., π
m
и, сравнив их длины между собой, выбрать оптимальный
контур.
Рассмотрим пример решения задачи о коммивояжёре методом вет-
вей и границ для матрицы расстояний А, представленной табл. 16.

Страницы