Задание № 2. Задача о коммивояжере. Метод ветвей и границ
Расстояния между пунктами заданы матрицей:
|
|
|
1 |
2 |
3 |
4 |
5 |
6 |
|
С = |
1 |
∞ |
4 |
5 |
6 |
7 |
1 |
|
2 |
1 |
∞ |
1 |
3 |
2 |
4 | |
|
3 |
6 |
5 |
∞ |
1 |
4 |
3 | |
|
4 |
1 |
7 |
6 |
∞ |
5 |
1 | |
|
5 |
4 |
1 |
2 |
5 |
∞ |
4 | |
|
6 |
5 |
6 |
3 |
4 |
1 |
∞ |
Решение задачи о коммивояжере методом ветвей и границ начинается с приведения матрицы (вычитания из каждой строки (столбца) матрицы C минимального элемента этой строки (столбца).
Произведем приведение матрицы Cпо строкам:
hν=min(i)hνi
|
|
|
1 |
2 |
3 |
4 |
5 |
6 |
hν |
|
С’= |
1 |
∞ |
4 |
5 |
6 |
7 |
1 |
1 |
|
2 |
1 |
∞ |
1 |
3 |
2 |
4 |
1 | |
|
3 |
6 |
5 |
∞ |
1 |
4 |
3 |
1 | |
|
4 |
1 |
7 |
6 |
∞ |
5 |
1 |
1 | |
|
5 |
4 |
1 |
2 |
5 |
∞ |
4 |
1 | |
|
6 |
5 |
6 |
3 |
4 |
1 |
∞ |
1 |
Произведем приведение матрицы Cпо столбцам:
gi= min(υ)gνi
|
|
|
1 |
2 |
3 |
4 |
5 |
6 |
|
С’= |
1 |
∞ |
3 |
4 |
5 |
6 |
0 |
|
2 |
0 |
∞ |
0 |
2 |
1 |
3 | |
|
3 |
5 |
4 |
∞ |
0 |
3 |
2 | |
|
4 |
0 |
6 |
5 |
∞ |
4 |
0 | |
|
5 |
3 |
0 |
1 |
4 |
∞ |
3 | |
|
6 |
4 |
5 |
2 |
3 |
0 |
∞ | |
|
|
gi |
0 |
0 |
0 |
0 |
0 |
0 |
В итоге получаем полностью приведенную (редуцированную) матрицу:
|
|
|
1 |
2 |
3 |
4 |
5 |
6 |
hν |
|
С0= |
1 |
∞ |
3 |
4 |
5 |
6 |
0 |
1 |
|
2 |
0 |
∞ |
0 |
2 |
1 |
3 |
1 | |
|
3 |
5 |
4 |
∞ |
0 |
3 |
2 |
1 | |
|
4 |
0 |
6 |
5 |
∞ |
4 |
0 |
1 | |
|
5 |
3 |
0 |
1 |
4 |
∞ |
3 |
1 | |
|
6 |
4 |
5 |
2 |
3 |
0 |
∞ |
1 | |
|
|
gi |
0 |
0 |
0 |
0 |
0 |
0 |
|
Величины hνиgiназываютсяконстантами приведения.
Нижняя граница цикла: d0=1+1+1+1+1+1+0+0+0+0+0+0 = 6
(
).
Шаг №1.
Определяем
ребро ветвленияи разобьем все
множество допустимых значенийQ0относительно этого ребра на два
непересекающихся подмножества (
)
и (
),
т.е.
,
где
В приведенной матрице исследуем все нулевые переходы.
|
|
|
1 |
2 |
3 |
4 |
5 |
6 |
αν |
|
C0 = |
1 |
∞ |
3 |
4 |
5 |
6 |
0(3) |
3 |
|
2 |
0(0) |
∞ |
0(1) |
2 |
1 |
3 |
0 | |
|
3 |
5 |
4 |
∞ |
0(4) |
3 |
2 |
2 | |
|
4 |
0(0) |
6 |
5 |
∞ |
4 |
0(0) |
0 | |
|
5 |
3 |
0(4) |
1 |
4 |
∞ |
3 |
1 | |
|
6 |
4 |
5 |
2 |
3 |
0(3) |
∞ |
2 | |
|
|
βi |
0 |
3 |
1 |
2 |
1 |
0 |
|
Наибольшая сумма констант приведения равна
υ34= α3+β4=2+2=4, следовательно,
множество
разбивается на два подмножества
и
.
Оценка
длины цикла:
.
Исключение
ребра (3,4) проводим путем замены элемента
υ34= 0 на ∞, после чего осуществляем
очередное приведение матрицы расстояний
для образовавшегося подмножества (
),
в результате получим редуцированную
матрицу.
|
|
|
1 |
2 |
3 |
4 |
5 |
6 |
αν |
|
С0' = |
1 |
∞ |
3 |
4 |
5 |
6 |
0 |
0 |
|
2 |
0 |
∞ |
0 |
2 |
1 |
3 |
0 | |
|
3 |
5 |
4 |
∞ |
∞ |
3 |
2 |
2 | |
|
4 |
0 |
6 |
5 |
∞ |
4 |
0 |
0 | |
|
5 |
3 |
0 |
1 |
4 |
∞ |
3 |
0 | |
|
6 |
4 |
5 |
2 |
3 |
0 |
∞ |
0 | |
|
|
βi |
0 |
0 |
0 |
2 |
0 |
0 |
|
Включение ребра (3,4) проводится путем исключения всех элементов 3-ой строки и 4-го столбца, в которой элемент υ43заменяем на ∞, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (5x5), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
|
|
|
1 |
2 |
3 |
5 |
6 |
hν |
|
|
1 |
∞ |
3 |
4 |
6 |
0 |
0 |
|
|
2 |
0 |
∞ |
0 |
1 |
3 |
0 |
|
C1= |
4 |
0 |
6 |
∞ |
4 |
0 |
0 |
|
|
5 |
3 |
0 |
1 |
∞ |
3 |
0 |
|
|
6 |
4 |
5 |
2 |
0 |
∞ |
0 |
|
|
gi |
0 |
0 |
0 |
0 |
0 |
|
d1=0
Шаг №2.
Определяем
ребро ветвленияи разобьем все
множество допустимых значенийQ1относительно этого ребра на два
непересекающихся подмножества
.
В приведенной матрице исследуем все нулевые переходы.
|
|
|
1 |
2 |
3 |
5 |
6 |
αν |
|
|
1 |
∞ |
3 |
4 |
6 |
0(3) |
3 |
|
|
2 |
0(0) |
∞ |
0(1) |
1 |
3 |
0 |
|
C1= |
4 |
0(0) |
6 |
∞ |
4 |
0(0) |
0 |
|
|
5 |
3 |
0(4) |
1 |
∞ |
3 |
1 |
|
|
6 |
4 |
5 |
2 |
0(3) |
∞ |
2 |
|
|
βi |
0 |
3 |
1 |
1 |
0 |
|
Наибольшая сумма констант приведения равна
υ52=1+3=4, следовательно,
множество
разбивается на два подмножества
и
.
Оценка
длины цикла:
.
Оценка
на перспективном множестве:
В результате получим другую сокращенную матрицу (4x4), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
|
|
|
1 |
3 |
5 |
6 |
hν |
|
C2 = |
2 |
∞ |
4 |
6 |
0 |
0 |
|
3 |
0 |
0 |
∞ |
3 |
0 | |
|
5 |
0 |
∞ |
4 |
0 |
0 | |
|
6 |
4 |
2 |
0 |
∞ |
0 | |
|
|
gi |
0 |
0 |
0 |
0 |
|
d2=0
Шаг №3.
Определяем
ребро ветвленияи разобьем все
множество допустимых значенийQ2относительно этого ребра на два
непересекающихся подмножества
.
В приведенной матрице исследуем все нулевые переходы.
|
|
|
1 |
3 |
5 |
6 |
αν |
|
C2 = |
1 |
∞ |
4 |
6 |
0(4) |
4 |
|
2 |
0(0) |
0(2) |
∞ |
3 |
0 | |
|
4 |
0(0) |
∞ |
4 |
0(0) |
0 | |
|
6 |
4 |
2 |
0(6) |
∞ |
2 | |
|
|
βi |
0 |
2 |
4 |
0 |
|
Наибольшая сумма констант приведения равна
υ65=2+4=6, следовательно,
множество
разбивается на два подмножества
и
.
Оценка
длины цикла:
.
Оценка
на перспективном множестве:
В результате получим другую сокращенную матрицу (3x3), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
|
|
|
1 |
3 |
6 |
hν |
|
|
1 |
0 |
∞ |
0 |
0 |
|
C3 = |
2 |
∞ |
0 |
1 |
0 |
|
|
4 |
0 |
5 |
0 |
0 |
|
|
gi |
0 |
0 |
0 |
|
d3=0
Шаг №4.
Определяем
ребро ветвленияи разобьем все
множество допустимых значенийQ3относительно этого ребра на два
непересекающихся подмножества
.
В приведенной матрице исследуем все нулевые переходы.
|
|
|
1 |
3 |
6 |
αν |
|
|
1 |
∞ |
4 |
0(4) |
4 |
|
C3 = |
2 |
0(0) |
0(4) |
∞ |
0 |
|
|
4 |
0(0) |
∞ |
0(0) |
0 |
|
|
βi |
0 |
4 |
0 |
|
Наибольшая сумма констант приведения равна
υ16=4+0=4, следовательно,
множество
разбивается на два подмножества
и
.
Оценка
длины цикла:
.
Оценка
на перспективном множестве:
В результате получим другую сокращенную матрицу (2x2), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
|
|
|
1 |
3 |
hν |
|
C4 = |
2 |
0 |
0 |
0 |
|
4 |
0 |
∞ |
0 | |
|
|
gi |
0 |
0 |
|
d4=0
В
соответствии с этой матрицей включаем
в маршрут
и
.
Ответ: l* =C34+C41+C16+C65+C52+C23=1+1+1+1+1+1=6.
Дерево решения имеет следующий вид:
