Применение методов решения задачи коммивояжера на практике

 

d(1,6) = 1 + 0 = 1; d(2,1) = 0 + 1 = 1; d(2,3) = 0 + 0 = 0; d(3,5) = 2 + 0 = 2; d(4,6) = 1 + 0 = 1; d(5,2) = 1 + 3 = 4; d(6,3) = 0 + 0 = 0; d(6,4) = 0 + 1 = 1; d(6,5) = 0 + 0 = 0; 

Наибольшая сумма констант приведения равна (1 + 3) = 4 для ребра (5,2), следовательно, множество разбивается на два подмножества (5,2) и (5*,2*). Нижняя граница этого подмножества:

H(5*,2*) = 8 + 4 = 12

Исключение ребра (5,2) проводим путем замены элемента d52 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (5*,2*), в результате получим редуцированную матрицу. (Таблица 7)

Таблица 7 Приведение матрицы расстояний для подмножества (5*,2*), матрица размерностью 6´6

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

 

Включение ребра (5,2) проводится путем исключения всех элементов 5-ой строки и 2-го столбца, в которой элемент d25 заменяем на М, для исключения образования негамильтонова цикла.

В результате получим другую сокращенную матрицу (5 x 5), которая подлежит операции приведения.

Сумма констант приведения сокращенной матрицы: ∑di + ∑dj = 0

После операции приведения сокращенная матрица будет иметь вид:  (Таблица 8)

Таблица 8 Сокращённая матрица, матрица размерностью 5´5

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

 

Нижняя граница подмножества (5,2) равна: H(5,2) = 8 + 0 = 8  ≤  12

Поскольку нижняя граница этого подмножества (5,2) меньше, чем подмножества (5*,2*), то ребро (5,2) включаем в маршрут с новой границей H = 8

Шаг №2. Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).

С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М (бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках. (Таблица 9)

Таблица 9 Определение ребра ветвления (5,2), матрица размерностью 5´5

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

 

Продолжение таблицы 9 Сумма образовавшихся констант приведения, матрица размерностью 5´5

4	3	5	M	1	0(1)	1
6	4	0(0)	0(1)	0(0)	M	0
dj	3	0	1	0	0	0

 

d(1,6) = 1 + 0 = 1; d(2,1) = 0 + 3 = 3; d(2,3) = 0 + 0 = 0; d(3,5) = 2 + 0 = 2; d(4,6) = 1 + 0 = 1; d(6,3) = 0 + 0 = 0; d(6,4) = 0 + 1 = 1; d(6,5) = 0 + 0 = 0; 

Наибольшая сумма констант приведения равна (0 + 3) = 3 для ребра (2,1), следовательно, множество разбивается на два подмножества (2,1) и (2*,1*).

Нижняя граница гамильтоновых циклов этого подмножества:

H(2*,1*) = 8 + 3 = 11

Исключение ребра (2,1) проводим путем замены элемента d21 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (2*,1*), в результате получим редуцированную матрицу. (Таблица 10)

Таблица 10 Приведение матрицы расстояний для подмножества (2*,1*) матрица размерностью 5´5

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

 

Включение ребра (2,1) проводится путем исключения всех элементов 2-ой строки и 1-го столбца, в которой элемент d12 заменяем на М, для исключения образования негамильтонова цикла.

В результате получим другую сокращенную матрицу (4 x 4), которая подлежит операции приведения.

Сумма констант приведения сокращенной матрицы: ∑di + ∑dj = 0

После операции приведения сокращенная матрица будет иметь вид (Таблица 11):

Таблица 11 Сокращённая матрица, матрица размерностью 4´4

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

 

Нижняя граница подмножества (2,1) равна:

H(2,1) = 8 + 0 = 8  ≤  11

Чтобы исключить подциклы, запретим следующие переходы: (1,5), 

Поскольку нижняя граница этого подмножества (2,1) меньше, чем подмножества (2*,1*), то ребро (2,1) включаем в маршрут с новой границей H = 8

Шаг №3. Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).

С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М (бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках. (Таблица 12)

Таблица 12 Определение ребра ветвления (2,1) матрица размерностью 4´4

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

 

d(1,6) = 1 + 0 = 1; d(3,5) = 2 + 0 = 2; d(4,6) = 1 + 0 = 1; d(6,3) = 0 + 2 = 2; d(6,4) = 0 + 1 = 1; d(6,5) = 0 + 0 = 0; 

Наибольшая сумма констант приведения равна (0 + 2) = 2 для ребра (6,3), следовательно, множество разбивается на два подмножества (6,3) и (6*,3*).

Нижняя граница гамильтоновых циклов этого подмножества:

H(6*,3*) = 8 + 2 = 10

Исключение ребра (6,3) проводим путем замены элемента d63 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (6*,3*), в результате получим редуцированную матрицу. (Таблица 13)