Задача коммивояжера.
Возьмем в качестве произвольного маршрута:
X0 = (1,2);(2,3);(3,4);(4,5);(5,6);(6,1)
Тогда F(X0) = 4 + 7 + 9 + 3 + 4 + 2 = 29
Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент.
di = min(j) dij
i  j	1	2	3	4	5	6	di	
1	M	4	4	5	4	3	3	
2	2	M	7	1	1	6	1	
3	2	3	M	9	4	5	2	
4	1	3	2	M	3	1	1	
5	7	4	1	1	M	4	1	
6	2	3	4	7	9	M	2	

Затем вычитаем di из элементов рассматриваемой строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
i  j	1	2	3	4	5	6	
1	M	1	1	2	1	0	
2	1	M	6	0	0	5	
3	0	1	M	7	2	3	
4	0	2	1	M	2	0	
5	6	3	0	0	M	3	
6	0	1	2	5	7	M	

Такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
dj = min(i) dij
i  j	1	2	3	4	5	6	
1	M	1	1	2	1	0	
2	1	M	6	0	0	5	
3	0	1	M	7	2	3	
4	0	2	1	M	2	0	
5	6	3	0	0	M	3	
6	0	1	2	5	7	M	
dj	0	1	0	0	0	0	

После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины di и dj называются константами приведения.
i  j	1	2	3	4	5	6	
1	M	0	1	2	1	0	
2	1	M	6	0	0	5	
3	0	0	M	7	2	3	
4	0	1	1	M	2	0	
5	6	2	0	0	M	3	
6	0	0	2	5	7	M	

Сумма констант приведения определяет нижнюю границу H:
H = ∑di + ∑dj
H = 3+1+2+1+1+2+0+1+0+0+0+0 = 11
Элементы матрицы dij соответствуют расстоянию от пункта i до пункта j.
Поскольку в матрице n городов, то D является матрицей nxn с неотрицательными элементами dij >=0
Каждый допустимый маршрут представляет собой цикл, по которому коммивояжер посещает город только один раз и возвращается в исходный город.
Длина маршрута определяется выражением:
F(Mk) = ∑dij
Причем каждая строка и столбец входят в маршрут только один раз с элементом dij .
Шаг №1.
Определяем ребро ветвления  и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
i  j	1	2	3	4	5	6	di	
1	M	0(0)	1	2	1	0(0)	0	
2	1	M	6	0(0)	0(1)	5	0	
3	0(0)	0(0)	M	7	2	3	0	
4	0(0)	1	1	M	2	0(0)	0	
5	6	2	0(1)	0(0)	M	3	0	
6	0(0)	0(0)	2	5	7	M	0	
dj	0	0	1	0	1	0	0	

d(1,2) = 0 + 0 = 0; d(1,6) = 0 + 0 = 0; d(2,4) = 0 + 0 = 0; d(2,5) = 0 + 1 = 1; d(3,1) = 0 + 0 = 0; d(3,2) = 0 + 0 = 0; d(4,1) = 0 + 0 = 0; d(4,6) = 0 + 0 = 0; d(5,3) = 0 + 1 = 1; d(5,4) = 0 + 0 = 0; d(6,1) = 0 + 0 = 0; d(6,2) = 0 + 0 = 0; 
Наибольшая сумма констант приведения равна (0 + 1) = 1 для ребра (2,5), следовательно, множество разбивается на два подмножества (2,5) и (2*,5*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(2*,5*) = 11 + 1 = 12
Исключение ребра (2,5) проводим путем замены элемента d25 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (2*,5*), в результате получим редуцированную матрицу.
i  j	1	2	3	4	5	6	di	
1	M	0	1	2	1	0	0	
2	1	M	6	0	M	5	0	
3	0	0	M	7	2	3	0	
4	0	1	1	M	2	0	0	
5	6	2	0	0	M	3	0	
6	0	0	2	5	7	M	0	
dj	0	0	0	0	1	0	1	

Включение ребра (2,5) проводится путем исключения всех элементов 2-ой строки и 5-го столбца, в которой элемент d52 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (5 x 5), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑di + ∑dj = 0
После операции приведения сокращенная матрица будет иметь вид:
i  j	1	2	3	4	6	di	
1	M	0	1	2	0	0	
3	0	0	M	7	3	0	
4	0	1	1	M	0	0	
5	6	M	0	0	3	0	
6	0	0	2	5	M	0	
dj	0	0	0	0	0	0	

Нижняя граница подмножества (2,5) равна:
H(2,5) = 11 + 0 = 11  <  12
Поскольку нижняя граница этого подмножества (2,5) меньше, чем подмножества (2*,5*), то ребро (2,5) включаем в маршрут.
Шаг №2.
Определяем ребро ветвления  и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
i  j	1	2	3	4	6	di	
1	M	0(0)	1	2	0(0)	0	
3	0(0)	0(0)	M	7	3	0	
4	0(0)	1	1	M	0(0)	0	
5	6	M	0(1)	0(2)	3	0	
6	0(0)	0(0)	2	5	M	0	
dj	0	0	1	2	0	0	

d(1,2) = 0 + 0 = 0; d(1,6) = 0 + 0 = 0; d(3,1) = 0 + 0 = 0; d(3,2) = 0 + 0 = 0; d(4,1) = 0 + 0 = 0; d(4,6) = 0 + 0 = 0; d(5,3) = 0 + 1 = 1; d(5,4) = 0 + 2 = 2; d(6,1) = 0 + 0 = 0; d(6,2) = 0 + 0 = 0; 
Наибольшая сумма констант приведения равна (0 + 2) = 2 для ребра (5,4), следовательно, множество разбивается на два подмножества (5,4) и (5*,4*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(5*,4*) = 11 + 2 = 13
Исключение ребра (5,4) проводим путем замены элемента d54 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (5*,4*), в результате получим редуцированную матрицу.
i  j	1	2	3	4	6	di	
1	M	0	1	2	0	0	
3	0	0	M	7	3	0	
4	0	1	1	M	0	0	
5	6	M	0	M	3	0	
6	0	0	2	5	M	0	
dj	0	0	0	2	0	2	

Включение ребра (5,4) проводится путем исключения всех элементов 5-ой строки и 4-го столбца, в которой элемент d45 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (4 x 4), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑di + ∑dj = 1
После операции приведения сокращенная матрица будет иметь вид:
i  j	1	2	3	6	di	
1	M	0	1	0	0	
3	0	0	M	3	0	
4	0	1	1	0	0	
6	0	0	2	M	0	
dj	0	0	1	0	1	

Нижняя граница подмножества (5,4) равна:
H(5,4) = 11 + 1 = 12  <  13
Чтобы исключить подциклы, запретим следующие переходы: (4,2), 
Поскольку нижняя граница этого подмножества (5,4) меньше, чем подмножества (5*,4*), то ребро (5,4) включаем в маршрут.
Шаг №3.
Определяем ребро ветвления  и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
i  j	1	2	3	6	di	
1	M	0(0)	0(0)	0(0)	0	
3	0(0)	0(0)	M	3	0	
4	0(0)	M	0(0)	0(0)	0	
6	0(0)	0(0)	1	M	0	
dj	0	0	0	0	0	

d(1,2) = 0 + 0 = 0; d(1,3) = 0 + 0 = 0; d(1,6) = 0 + 0 = 0; d(3,1) = 0 + 0 = 0; d(3,2) = 0 + 0 = 0; d(4,1) = 0 + 0 = 0; d(4,3) = 0 + 0 = 0; d(4,6) = 0 + 0 = 0; d(6,1) = 0 + 0 = 0; d(6,2) = 0 + 0 = 0; 
Наибольшая сумма констант приведения равна (0 + 0) = 0 для ребра (1,2), следовательно, множество разбивается на два подмножества (1,2) и (1*,2*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(1*,2*) = 12 + 0 = 12
Исключение ребра (1,2) проводим путем замены элемента d12 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (1*,2*), в результате получим редуцированную матрицу.
i  j	1	2	3	6	di	
1	M	M	0	0	0	
3	0	0	M	3	0	
4	0	M	0	0	0	
6	0	0	1	M	0	
dj	0	0	0	0	0	

Включение ребра (1,2) проводится путем исключения всех элементов 1-ой строки и 2-го столбца, в которой элемент d21 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (3 x 3), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑di + ∑dj = 0
После операции приведения сокращенная матрица будет иметь вид:
i  j	1	3	6	di	
3	0	M	3	0	
4	0	0	0	0	
6	0	1	M	0	
dj	0	0	0	0	

Нижняя граница подмножества (1,2) равна:
H(1,2) = 12 + 0 = 12  <  12
Чтобы исключить подциклы, запретим следующие переходы: (4,2), (4,1), 
Поскольку нижняя граница этого подмножества (1,2) меньше, чем подмножества (1*,2*), то ребро (1,2) включаем в маршрут.
Шаг №4.
Определяем ребро ветвления  и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
i  j	1	3	6	di	
3	0(3)	M	3	3	
4	M	0(1)	0(3)	0	
6	0(1)	1	M	1	
dj	0	1	3	0	

d(3,1) = 3 + 0 = 3; d(4,3) = 0 + 1 = 1; d(4,6) = 0 + 3 = 3; d(6,1) = 1 + 0 = 1; 
Наибольшая сумма констант приведения равна (3 + 0) = 3 для ребра (3,1), следовательно, множество разбивается на два подмножества (3,1) и (3*,1*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(3*,1*) = 12 + 3 = 15
Исключение ребра (3,1) проводим путем замены элемента d31 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (3*,1*), в результате получим редуцированную матрицу.
i  j	1	3	6	di	
3	M	M	3	3	
4	M	0	0	0	
6	0	1	M	0	
dj	0	0	0	3	

Включение ребра (3,1) проводится путем исключения всех элементов 3-ой строки и 1-го столбца, в которой элемент d13 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑di + ∑dj = 1
После операции приведения сокращенная матрица будет иметь вид:
i  j	3	6	di	
4	0	0	0	
6	1	M	1	
dj	0	0	1	

Нижняя граница подмножества (3,1) равна:
H(3,1) = 12 + 1 = 13  <  15
Поскольку нижняя граница этого подмножества (3,1) меньше, чем подмножества (3*,1*), то ребро (3,1) включаем в маршрут.
В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (4,6) и (6,3).
В результате по дереву ветвлений гамильтонов цикл образуют ребра:
(2,5), (5,4), (4,6), (6,3), (3,1), (1,2), 
Длина маршрута равна F(Mk) = 13

Решение было получено и оформлено с помощью сервиса:
Задача коммивояжера
Copyright © Semestr.RU