Имеется необходимость посетить n городов в ходе деловой поездки. Спланировать поездку нужно так, чтобы, переезжая из города в город, побывать в каждом не более одного раза и вернуться в исходный город. Определить оптимальный маршрут посещения городов и его минимальное расстояние. 
Задана матрица расстояний между городами c_ij.

Решение проводим с помощью калькулятора Решение задачи коммивояжера. Возьмем в качестве произвольного маршрута: 
X₀ = (1,2);(2,3);(3,4);(4,5);(5,6);(6,7);(7,1) 
Тогда F(X₀) = 20 + 20 + 16 + 9 + 21 + 18 + 12 = 116 
Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент. 
d_i = min(j) d_ij

i  j	1	2	3	4	5	6	7	di
1	M	20	20	16	13	16	20	13
2	18	M	20	16	12	13	18	12
3	16	14	M	16	M	21	14	14
4	16	9	14	M	9	19	22	9
5	M	12	19	20	M	21	12	12
6	11	11	22	22	14	M	18	11
7	12	12	9	M	16	15	M	9

Затем вычесть его из элементов рассматриваемой строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.

i  j	1	2	3	4	5	6	7
1	M	7	7	3	0	3	7
2	6	M	8	4	0	1	6
3	2	0	M	2	M	7	0
4	7	0	5	M	0	10	13
5	M	0	7	8	M	9	0
6	0	0	11	11	3	M	7
7	3	3	0	M	7	6	M

Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент: 
d _j = min(i) d_ij

i  j	1	2	3	4	5	6	7
1	M	7	7	3	0	3	7
2	6	M	8	4	0	1	6
3	2	0	M	2	M	7	0
4	7	0	5	M	0	10	13
5	M	0	7	8	M	9	0
6	0	0	11	11	3	M	7
7	3	3	0	M	7	6	M
dj	0	0	0	2	0	1	0

После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины d_i, d_j называются константами приведения.

i  j	1	2	3	4	5	6	7
1	M	7	7	1	0	2	7
2	6	M	8	2	0	0	6
3	2	0	M	0	M	6	0
4	7	0	5	M	0	9	13
5	M	0	7	6	M	8	0
6	0	0	11	9	3	M	7
7	3	3	0	M	7	5	M

---

Сумма констант приведения определяет нижнюю границу H:  
H = 13+12+14+9+12+11+9+0+0+0+2+0+1+0 = 83 
Элементы матрицы d_ij соответствуют расстоянию от пункта i до пункта j. 
Поскольку в матрице n городов, то D является матрицей nxn с неотрицательными элементами d _ij >=0 
Каждый допустимый маршрут представляет собой цикл, по которому коммивояжер посещает город только один раз и возвращается в исходный город. 
Длина маршрута определяется выражением:  
Причем каждая строка и столбец входят в маршрут только один раз с элементом d_ij . 
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*). 
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

i  j	1	2	3	4	5	6	7	di
1	M	7	7	1	0(1)	2	7	1
2	6	M	8	2	0(0)	0(2)	6	0
3	2	0(0)	M	0(1)	M	6	0(0)	0
4	7	0(0)	5	M	0(0)	9	13	0
5	M	0(0)	7	6	M	8	0(0)	0
6	0(2)	0(0)	11	9	3	M	7	0
7	3	3	0(8)	M	7	5	M	3
dj	2	0	5	1	0	2	0	0

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

i  j	1	2	3	4	5	6	7	di
1	M	7	7	1	0	2	7	0
2	6	M	8	2	0	0	6	0
3	2	0	M	0	M	6	0	0
4	7	0	5	M	0	9	13	0
5	M	0	7	6	M	8	0	0
6	0	0	11	9	3	M	7	0
7	3	3	M	M	7	5	M	3
dj	0	0	5	0	0	0	0	8

Включение ребра (7,3) проводится путем исключения всех элементов 7-ой строки и 3-го столбца, в которой элемент d₃₇ заменяем на М, для исключения образования негамильтонова цикла. 
В результате получим другую сокращенную матрицу (6 x 6), которая подлежит операции приведения. 
Сумма констант приведения сокращенной матрицы: 
 
После операции приведения сокращенная матрица будет иметь вид:

---

i  j	1	2	4	5	6	7	di
1	M	7	1	0	2	7	0
2	6	M	2	0	0	6	0
3	2	0	0	M	6	M	0
4	7	0	M	0	9	13	0
5	M	0	6	M	8	0	0
6	0	0	9	3	M	7	0
dj	0	0	0	0	0	0	0

Нижняя граница подмножества (7,3) равна: 
H(7,3) = 83 + 0 = 83  <  91 
Поскольку нижняя граница этого подмножества (7,3) меньше, чем подмножества (7*,3*), то ребро (7,3) включаем в маршрут. 
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*). 
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

i  j	1	2	4	5	6	7	di
1	M	7	1	0(1)	2	7	1
2	6	M	2	0(0)	0(2)	6	0
3	2	0(0)	0(1)	M	6	M	0
4	7	0(0)	M	0(0)	9	13	0
5	M	0(0)	6	M	8	0(6)	0
6	0(2)	0(0)	9	3	M	7	0
dj	2	0	1	0	2	6	0

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

i  j	1	2	4	5	6	7	di
1	M	7	1	0	2	7	0
2	6	M	2	0	0	6	0
3	2	0	0	M	6	M	0
4	7	0	M	0	9	13	0
5	M	0	6	M	8	M	0
6	0	0	9	3	M	7	0
dj	0	0	0	0	0	6	6

Включение ребра (5,7) проводится путем исключения всех элементов 5-ой строки и 7-го столбца, в которой элемент d₇₅ заменяем на М, для исключения образования негамильтонова цикла. 
В результате получим другую сокращенную матрицу (5 x 5), которая подлежит операции приведения. 
Сумма констант приведения сокращенной матрицы: 
 
После операции приведения сокращенная матрица будет иметь вид:

---

i  j	1	2	4	5	6	di
1	M	7	1	0	2	0
2	6	M	2	0	0	0
3	2	0	0	M	6	0
4	7	0	M	0	9	0
6	0	0	9	3	M	0
dj	0	0	0	0	0	0

Нижняя граница подмножества (5,7) равна: 
H(5,7) = 83 + 0 = 83  <  89 
Чтобы исключить подциклы, запретим следующие переходы: (3,5), 
Поскольку нижняя граница этого подмножества (5,7) меньше, чем подмножества (5*,7*), то ребро (5,7) включаем в маршрут. 
Определяем ребро ветвления  и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) И (i*,j*). 
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

i  j	1	2	4	5	6	di
1	M	7	1	0(1)	2	1
2	6	M	2	0(0)	0(2)	0
3	2	0(0)	0(1)	M	6	0
4	7	0(0)	M	0(0)	9	0
6	0(2)	0(0)	9	3	M	0
dj	2	0	1	0	2	0

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

i  j	1	2	4	5	6	di
1	M	7	1	0	2	0
2	6	M	2	0	M	0
3	2	0	0	M	6	0
4	7	0	M	0	9	0
6	0	0	9	3	M	0
dj	0	0	0	0	2	2

Включение ребра (2,6) проводится путем исключения всех элементов 2-ой строки и 6-го столбца, в которой элемент d₆₂ заменяем на М, для исключения образования негамильтонова цикла. 
В результате получим другую сокращенную матрицу (4 x 4), которая подлежит операции приведения. 
Сумма констант приведения сокращенной матрицы: 
 
После операции приведения сокращенная матрица будет иметь вид:

i  j	1	2	4	5	di
1	M	7	1	0	0
3	2	0	0	M	0
4	7	0	M	0	0
6	0	M	9	3	0
dj	0	0	0	0	0

---

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

i  j	1	2	4	5	di
1	M	7	1	0(1)	1
3	2	0(0)	0(1)	M	0
4	7	0(0)	M	0(0)	0
6	0(5)	M	9	3	3
dj	2	0	1	0	0

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

i  j	1	2	4	5	di
1	M	7	1	0	0
3	2	0	0	M	0
4	7	0	M	0	0
6	M	M	9	3	3
dj	2	0	0	0	5

Включение ребра (6,1) проводится путем исключения всех элементов 6-ой строки и 1-го столбца, в которой элемент d₁₆ заменяем на М, для исключения образования негамильтонова цикла. 
В результате получим другую сокращенную матрицу (3 x 3), которая подлежит операции приведения. 
Сумма констант приведения сокращенной матрицы: 
 
После операции приведения сокращенная матрица будет иметь вид:

i  j	2	4	5	di
1	7	1	0	0
3	0	0	M	0
4	0	M	0	0
dj	0	0	0	0

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

i  j	2	4	5	di
1	M	1	0(1)	1
3	0(0)	0(1)	M	0
4	0(0)	M	0(0)	0
dj	0	1	0	0

---

Смотрите также файлы

• Lektsiya8.doc

• M51_21_-_kopia.pdf

• Zadachi.docx

• Communication theory.docx

• Computer games.docx