Действия над матрицами

 

Решение

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

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

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

i  j	1	2	3	4	5	6
1	M	26	42	15	29	25	15
2	7	M	16	1	30	25	1
3	20	13	M	35	5	0	0
4	21	16	25	M	18	18	16
5	12	46	27	48	M	5	5
6	23	5	5	9	5	M	5

 

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

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

i  j	1	2	3	4	5	6
1	M	11	27	0	14	10
2	6	M	15	0	29	24
3	20	13	M	35	5	0
4	5	0	9	M	2	2
5	7	41	22	43	M	0
6	18	0	0	4	0	M
	5	0	0	0	0	0

 

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

i  j	1	2	3	4	5	6
1	M	11	27	0	14	10
2	1	M	15	0	29	24
3	15	13	M	35	5	0
4	0	0	9	M	2	2
5	2	41	22	43	M	0
6	13	0	0	4	0	M

 

Шаг №1.

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

i  j	1	2	3	4	5	6
1	M	11	27	0(10)	14	10	10
2	1	M	15	0(1)	29	24	1
3	15	13	M	35	5	0(5)	5
4	0(1)	0(0)	9	M	2	2	0
5	2	41	22	43	M	0(2)	2
6	13	0(0)	0(9)	4	0(2)	M	0
	1	0	9	0	2	0	0

 

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

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

H(1*,4*) = 47 + 10 = 57

i  j	1	2	3	4	5	6
1	M	11	27	M	14	10	10
2	1	M	15	0	29	24	0
3	15	13	M	35	5	0	0
4	0	0	9	M	2	2	0
5	2	41	22	43	M	0	0
6	13	0	0	4	0	M	0
	0	0	0	0	0	0	10

 

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

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

∑d_i + ∑d_j = 2

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

i  j	1	2	3	5	6
2	1	M	15	29	24	1
3	15	13	M	5	0	0
4	M	0	9	2	2	0
5	2	41	22	M	0	0
6	13	0	0	0	M	0
	1	0	0	0	0	2

 

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

H(1,4) = 47 + 2 = 49  <  57

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

Шаг №2.

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

i j	1	2	3	5	6
2	0(16)	M	15	29	24	15
3	14	13	M	5	0(5)	5
4	M	0(2)	9	2	2	2
5	1	41	22	M	0(1)	1
6	12	0(0)	0(9)	0(2)	M	0
	1	0	9	2	0	0

 

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

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

H(2*,1*) = 49 + 16 = 65

i  j	1	2	3	5	6
2	M	M	15	29	24	15
3	14	13	M	5	0	0
4	M	0	9	2	2	0
5	1	41	22	M	0	0
6	12	0	0	0	M	0
	1	0	0	0	0	16

 

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

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

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

i  j	2	3	5	6
3	13	M	5	0	0
4	0	9	2	2	0
5	41	22	M	0	0
6	0	0	0	M	0
	0	0	0	0	0

 

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

H(2,1) = 49 + 0 = 49  < 65

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

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

Шаг №3.

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

i  j	2	3	5	6
3	13	M	5	0(5)	5
4	M	7	0(0)	0(0)	0
5	41	22	M	0(22)	22
6	0(13)	0(7)	0(0)	M	0
	13	7	0	0	0