ВУЗ:
Составители:
Рубрика:
91
Далее выбирается третья дуга ветвления (2, 1), матрица расстояний
после стягивания принимает размер 2
×
2 и к уже имеющимся дугам (3, 4),
(1, 5), (2, 1) контура π
1
добавляются две однозначно определяемые дуги
(4, 2), (5, 3). Нижняя граница множества
)4(
1
Z
будет равна длине этого
контура, вычисляемой суммированием длин входящих в него дуг:
)(
)4(
1
Zγ
= σ(π
1
) = 0 + 6 + 10 + 10 + 7 = 33.
На рисунке 49 изображено дерево T, полученное в результате вы-
полненных ветвлений.
Поскольку длина σ(π
1
) = 33 оказалась не больше любой из нижних
границ
)(
)1(
2
Zγ
,
)(
)2(
2
Zγ
,
)(
)3(
2
Zγ
, которые соответствуют другим конеч-
ным узлам дерева, контур π
1
, составленный из дуг (3, 4), (1, 5), (2, 1),
(4, 2) и (5, 3), является искомым оптимальным контуром π
0
.
Задачи и упражнения
1. Решите методом ветвей и границ задачу о коммивояжере для
матрицы расстояний А:
а) j
i
1 2 3 4 5
1 ∞ 5 8 17 19
А =
2 18 ∞ 23 21 6
3 23 11 ∞ 7 19
4 6 18 9 ∞ 12
5 10 16 14 20 ∞
(4
,2)
(5,3)
33)(
)4(
1
=γ Z
(2,1)
33)(
)3(
1
=γ Z
Z(n)
(3,4)
(1,5)
)4,3(
)5,1(
Рис. 49
γ(Z) = 30
40)(
)1(
2
=γ Z
30)(
)1(
1
=γ Z
52)(
)2(
2
=γ Z
)1,2(
57)(
)3(
2
=γ Z
33)(
)2(
1
=γ Z
Страницы
- « первая
- ‹ предыдущая
- …
- 89
- 90
- 91
- 92
- 93
- …
- следующая ›
- последняя »
