3.2 Комивояжер

Задача коммивояжера.

Возьмем в качестве произвольного маршрута:

X₀ = (1,2);(2,3);(3,4);(4,5);(5,6);(6,1)

Тогда F(X₀) = 14 + 34 + 24 + 9 + 30 + 1 = 112

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

d_i = min(j) d_ij

i j	1	2	3	4	5	6	di
1	M	14	40	33	16	51	14
2	48	M	34	4	11	24	4
3	57	85	M	24	38	52	24
4	30	50	44	M	9	31	9
5	18	42	24	31	M	30	18
6	1	38	31	19	32	M	1

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

i j	1	2	3	4	5	6
1	M	0	26	19	2	37
2	44	M	30	0	7	20
3	33	61	M	0	14	28
4	21	41	35	M	0	22
5	0	24	6	13	M	12
6	0	37	30	18	31	M

Такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:

d_j = min(i) d_ij

i j	1	2	3	4	5	6
1	M	0	26	19	2	37
2	44	M	30	0	7	20
3	33	61	M	0	14	28
4	21	41	35	M	0	22
5	0	24	6	13	M	12
6	0	37	30	18	31	M
dj	0	0	6	0	0	12

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

i j	1	2	3	4	5	6
1	M	0	20	19	2	25
2	44	M	24	0	7	8
3	33	61	M	0	14	16
4	21	41	29	M	0	10
5	0	24	0	13	M	0
6	0	37	24	18	31	M

Сумма констант приведения определяет нижнюю границу H:

H = ∑d_i + ∑d_j

H = 14+4+24+9+18+1+0+0+6+0+0+12 = 88

Элементы матрицы d_ij соответствуют расстоянию от пункта i до пункта j.

Поскольку в матрице n городов, то D является матрицей nxn с неотрицательными элементами d_ij ≥ 0

Каждый допустимый маршрут представляет собой цикл, по которому коммивояжер посещает город только один раз и возвращается в исходный город.

Длина маршрута определяется выражением:

F(M_k) = ∑d_ij

Причем каждая строка и столбец входят в маршрут только один раз с элементом d_ij.

Шаг №1.

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

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

i j	1	2	3	4	5	6	di
1	M	0(26)	20	19	2	25	2
2	44	M	24	0(7)	7	8	7
3	33	61	M	0(14)	14	16	14
4	21	41	29	M	0(12)	10	10
5	0(0)	24	0(20)	13	M	0(8)	0
6	0(18)	37	24	18	31	M	18
dj	0	24	20	0	2	8	0

d(1,2) = 2 + 24 = 26; d(2,4) = 7 + 0 = 7; d(3,4) = 14 + 0 = 14; d(4,5) = 10 + 2 = 12; d(5,1) = 0 + 0 = 0; d(5,3) = 0 + 20 = 20; d(5,6) = 0 + 8 = 8; d(6,1) = 18 + 0 = 18;

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

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

i j	1	2	3	4	5	6	di
1	M	M	20	19	2	25	2
2	44	M	24	0	7	8	0
3	33	61	M	0	14	16	0
4	21	41	29	M	0	10	0
5	0	24	0	13	M	0	0
6	0	37	24	18	31	M	0
dj	0	24	0	0	0	0	26

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

H(1*,2*) = 88 + 26 = 114

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

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

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

i j	1	3	4	5	6	di
2	M	24	0	7	8	0
3	33	M	0	14	16	0
4	21	29	M	0	10	0
5	0	0	13	M	0	0
6	0	24	18	31	M	0
dj	0	0	0	0	0	0

Сумма констант приведения сокращенной матрицы:

∑d_i + ∑d_j = 0

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

H(1,2) = 88 + 0 = 88 ≤ 114

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

Шаг №2.

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

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

i j	1	3	4	5	6	di
2	M	24	0(7)	7	8	7
3	33	M	0(14)	14	16	14
4	21	29	M	0(17)	10	10
5	0(0)	0(24)	13	M	0(8)	0
6	0(18)	24	18	31	M	18
dj	0	24	0	7	8	0

d(2,4) = 7 + 0 = 7; d(3,4) = 14 + 0 = 14; d(4,5) = 10 + 7 = 17; d(5,1) = 0 + 0 = 0; d(5,3) = 0 + 24 = 24; d(5,6) = 0 + 8 = 8; d(6,1) = 18 + 0 = 18;

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

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

i j	1	3	4	5	6	di
2	M	24	0	7	8	0
3	33	M	0	14	16	0
4	21	29	M	0	10	0
5	0	M	13	M	0	0
6	0	24	18	31	M	0
dj	0	24	0	0	0	24

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

H(5*,3*) = 88 + 24 = 112

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

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

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

i j	1	4	5	6	di
2	M	0	7	8	0
3	33	0	M	16	0
4	21	M	0	10	0
6	0	18	31	M	0
dj	0	0	0	8	8

Сумма констант приведения сокращенной матрицы:

∑d_i + ∑d_j = 8

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

H(5,3) = 88 + 8 = 96 ≤ 112

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

Шаг №3.

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

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

i j	1	4	5	6	di
2	M	0(0)	7	0(2)	0
3	33	0(8)	M	8	8
4	21	M	0(9)	2	2
6	0(39)	18	31	M	18
dj	21	0	7	2	0

d(2,4) = 0 + 0 = 0; d(2,6) = 0 + 2 = 2; d(3,4) = 8 + 0 = 8; d(4,5) = 2 + 7 = 9; d(6,1) = 18 + 21 = 39;

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

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

i j	1	4	5	6	di
2	M	0	7	0	0
3	33	0	M	8	0
4	21	M	0	2	0
6	M	18	31	M	18
dj	21	0	0	0	39