ВУЗ:
Составители:
Рубрика:
85
Этот метод заключается в том, что в графе G выбирается некоторая
дуга ветвления (b, c) и множество Z(n) разбивается на подмножество
)1(
)1(
1
−nZ
всех контуров, содержащих дугу (b, c), и подмножество
)1(
)1(
2
−nZ
всех контуров, не содержащих дугу (b, c). Затем в G выбирает-
ся вторая дуга ветвления (p, q) и множество
)1(
)1(
1
−nZ
разбивается на
подмножество
)2(
)2(
1
−nZ
всех контуров, содержащих дуги (b, c) и (p, q),
и подмножество
)2(
)2(
2
−nZ
всех контуров, содержащих дугу (b, c), но не
содержащих дугу (p, q). Подобное разбиение множеств продолжается и
фиксируется, наконец, последняя дуга (x, y), определяющая множество
)1(
)1(
1
−n
Z
из единственного гамильтонова контура, который составлен из
дуг (b, c), (p, q), ..., (x, y). На рисунке 48 изображено дерево T, представ-
ляющее такое ветвление.
Каждой вершине этого дерева сопоставляется значение нижней гра-
ницы соответствующего множества контуров.
Вычисление нижней границы множества Z(n) производится после
приведения матрицы расстояний А, заключающегося в том, что: из каж-
дого элемента каждой строки вычитают минимальный элемент этой
строки и получают матрицу А′ (приведение по строкам); затем из каждого
элемента каждого столбца матрицы А′ вычитают минимальный элемент
этого столбца и получают матрицу
A
~
(приведение по столбцам).
Очевидно, что длина оптимального контура
)
~
(
0
Aσ
, вычисленная по
приведённой матрице
A
~
, связана с длиной оптимального контура σ
0
(A),
вычисленной по матрице А, соотношением:
β+α+σ=σ
∑∑
==
n
j
j
n
i
i
AA
11
00
)
~
()(
,
Z(n)
(b, c)
(p, q)
(x, y)
),( cb
)1(
)1(
2
−nZ
)1(
)1(
1
−nZ
)2(
)2(
1
−nZ
),( qp
)1(
)1(
1
−n
Z
…
…
Рис. 48
)2(
)2(
2
−nZ
Страницы
- « первая
- ‹ предыдущая
- …
- 83
- 84
- 85
- 86
- 87
- …
- следующая ›
- последняя »
