Задача 4

Возьмем в качестве произвольного маршрута: X₀ = (1,2);(2,3);(3,4);(4,5);(5,6);(6,7);(7,1) Тогда F(X₀) = 46 + 68 + 19 + 46 + 24 + 52 + 68 = 323 Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент. d_i = min(j) d_ij

i j	1	2	3	4	5	6	7	di
1	M	46	85	23	75	81	68	23
2	46	M	68	15	64	37	20	15
3	85	68	M	19	67	51	27	19
4	23	15	19	M	46	51	23	15
5	71	64	67	46	M	24	29	24
6	81	57	51	51	24	M	52	24
7	68	20	27	13	29	52	M	13

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

i j	1	2	3	4	5	6	7
1	M	23	62	0	52	58	45
2	31	M	53	0	49	22	5
3	66	49	M	0	48	32	8
4	8	0	4	M	31	36	8
5	47	40	43	22	M	0	5
6	57	33	27	27	0	M	28
7	55	7	14	0	16	39	M

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

i j	1	2	3	4	5	6	7
1	M	23	62	0	52	58	45
2	31	M	53	0	49	22	5
3	66	49	M	0	48	32	8
4	8	0	4	M	31	36	8
5	47	40	43	22	M	0	5
6	57	33	27	27	0	M	28
7	55	7	14	0	16	39	M
dj	8	0	4	0	0	0	5

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

i j	1	2	3	4	5	6	7
1	M	23	58	0	52	58	40
2	23	M	49	0	49	22	0
3	58	49	M	0	48	32	3
4	0	0	0	M	31	36	3
5	39	40	39	22	M	0	0
6	49	33	23	27	0	M	23
7	47	7	10	0	16	39	M

Сумма констант приведения определяет нижнюю границу H: H = ∑d_i + ∑d_j H = 23+15+19+15+24+24+13+8+0+4+0+0+0+5 = 150 Элементы матрицы 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	7	di
1	M	23	58	0(23)	52	58	40	23
2	23	M	49	0(0)	49	22	0(0)	0
3	58	49	M	0(3)	48	32	3	3
4	0(23)	0(7)	0(10)	M	31	36	3	0
5	39	40	39	22	M	0(22)	0(0)	0
6	49	33	23	27	0(39)	M	23	23
7	47	7	10	0(7)	16	39	M	7
dj	23	7	10	0	16	22	0	0

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

i j	1	2	3	4	5	6	7	di
1	M	23	58	0	52	58	40	0
2	23	M	49	0	49	22	0	0
3	58	49	M	0	48	32	3	0
4	0	0	0	M	31	36	3	0
5	39	40	39	22	M	0	0	0
6	49	33	23	27	M	M	23	23
7	47	7	10	0	16	39	M	0
dj	0	0	0	0	16	0	0	39

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

i j	1	2	3	4	6	7	di
1	M	23	58	0	58	40	0
2	23	M	49	0	22	0	0
3	58	49	M	0	32	3	0
4	0	0	0	M	36	3	0
5	39	40	39	22	M	0	0
7	47	7	10	0	39	M	0
dj	0	0	0	0	22	0	22

Нижняя граница подмножества (6,5) равна: H(6,5) = 150 + 22 = 172 ≤ 189 Поскольку нижняя граница этого подмножества (6,5) меньше, чем подмножества (6*,5*), то ребро (6,5) включаем в маршрут с новой границей H = 172 Шаг №2. Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*). С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

i j	1	2	3	4	6	7	di
1	M	23	58	0(23)	36	40	23
2	23	M	49	0(0)	0(10)	0(0)	0
3	58	49	M	0(3)	10	3	3
4	0(23)	0(7)	0(10)	M	14	3	0
5	39	40	39	22	M	0(22)	22
7	47	7	10	0(7)	17	M	7
dj	23	7	10	0	10	0	0

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

i j	1	2	3	4	6	7	di
1	M	23	58	0	36	40	0
2	23	M	49	0	0	0	0
3	58	49	M	0	10	3	0
4	M	0	0	M	14	3	0
5	39	40	39	22	M	0	0
7	47	7	10	0	17	M	0
dj	23	0	0	0	0	0	23

Включение ребра (4,1) проводится путем исключения всех элементов 4-ой строки и 1-го столбца, в которой элемент d₁₄заменяем на М, для исключения образования негамильтонова цикла. В результате получим другую сокращенную матрицу (5 x 5), которая подлежит операции приведения. Сумма констант приведения сокращенной матрицы: ∑d_i + ∑d_j = 40 После операции приведения сокращенная матрица будет иметь вид:

i j	2	3	4	6	7	di
1	23	58	M	36	40	23
2	M	49	0	0	0	0
3	49	M	0	10	3	0
5	40	39	22	M	0	0
7	7	10	0	17	M	0
dj	7	10	0	0	0	40

Нижняя граница подмножества (4,1) равна: H(4,1) = 172 + 40 = 212 > 195 Поскольку нижняя граница подмножества (4*,1*) меньше, чем подмножества (4,1), то ребро (4*,1*) включаем в маршрут с новой границей H = 195 Шаг №3. Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*). С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

i j	1	2	3	4	6	7	di
1	M	0(13)	35	M	13	17	13
2	0(16)	M	49	0(0)	0(10)	0(0)	0
3	35	49	M	0(3)	10	3	3
4	M	0(0)	0(10)	M	14	3	0
5	16	40	39	22	M	0(16)	16
7	24	7	10	0(7)	17	M	7
dj	16	0	10	0	10	0	0

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

i j	1	2	3	4	6	7	di
1	M	0	35	M	13	17	0
2	M	M	49	0	0	0	0
3	35	49	M	0	10	3	0
4	M	0	0	M	14	3	0
5	16	40	39	22	M	0	0
7	24	7	10	0	17	M	0
dj	16	0	0	0	0	0	16

Включение ребра (2,1) проводится путем исключения всех элементов 2-ой строки и 1-го столбца, в которой элемент d₁₂заменяем на М, для исключения образования негамильтонова цикла. В результате получим другую сокращенную матрицу (5 x 5), которая подлежит операции приведения. Сумма констант приведения сокращенной матрицы: ∑d_i + ∑d_j = 23 После операции приведения сокращенная матрица будет иметь вид:

i j	2	3	4	6	7	di
1	M	35	M	13	17	13
3	49	M	0	10	3	0
4	0	0	M	14	3	0
5	40	39	22	M	0	0
7	7	10	0	17	M	0
dj	0	0	0	10	0	23

Нижняя граница подмножества (2,1) равна: H(2,1) = 195 + 23 = 218 > 211 Поскольку нижняя граница подмножества (2*,1*) меньше, чем подмножества (2,1), то ребро (2*,1*) включаем в маршрут с новой границей H = 211 Шаг №4. Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*). С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

i j	1	2	3	4	6	7	di
1	M	M	22	M	0(4)	4	4
2	M	M	49	0(0)	0(0)	0(0)	0
3	19	49	M	0(3)	10	3	3
4	M	0(7)	0(10)	M	14	3	0
5	0(8)	40	39	22	M	0(0)	0
7	8	7	10	0(7)	17	M	7
dj	8	7	10	0	0	0	0

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

i j	1	2	3	4	6	7	di
1	M	M	22	M	0	4	0
2	M	M	49	0	0	0	0
3	19	49	M	0	10	3	0
4	M	0	M	M	14	3	0
5	0	40	39	22	M	0	0
7	8	7	10	0	17	M	0
dj	0	0	10	0	0	0	10

Включение ребра (4,3) проводится путем исключения всех элементов 4-ой строки и 3-го столбца, в которой элемент d₃₄заменяем на М, для исключения образования негамильтонова цикла. В результате получим другую сокращенную матрицу (5 x 5), которая подлежит операции приведения. Сумма констант приведения сокращенной матрицы: ∑d_i + ∑d_j = 10 После операции приведения сокращенная матрица будет иметь вид:

i j	1	2	4	6	7	di
1	M	M	M	0	4	0
2	M	M	0	0	0	0
3	19	49	M	10	3	3
5	0	40	22	M	0	0
7	8	7	0	17	M	0
dj	0	7	0	0	0	10

Нижняя граница подмножества (4,3) равна: H(4,3) = 211 + 10 = 221 ≤ 221 Поскольку нижняя граница этого подмножества (4,3) меньше, чем подмножества (4*,3*), то ребро (4,3) включаем в маршрут с новой границей H = 221 Шаг №5. Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*). С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

i j	1	2	4	6	7	di
1	M	M	M	0(4)	4	4
2	M	M	0(0)	0(0)	0(0)	0
3	16	39	M	7	0(7)	7
5	0(8)	33	22	M	0(0)	0
7	8	0(33)	0(0)	17	M	0
dj	8	33	0	0	0	0

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

i j	1	2	4	6	7	di
1	M	M	M	0	4	0
2	M	M	0	0	0	0
3	16	39	M	7	0	0
5	0	33	22	M	0	0
7	8	M	0	17	M	0
dj	0	33	0	0	0	33

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

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

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

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

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

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

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

i j	1	6	7	di
1	M	0	M	0
3	16	7	0	0
5	0	M	0	0
dj	0	0	0	0

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

i j	1	6	7	di
1	M	0(7)	M	0
3	16	7	0(7)	7
5	0(16)	M	0(0)	0
dj	16	7	0	0

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

i j	1	6	7	di
1	M	0	M	0
3	16	7	0	0
5	M	M	0	0
dj	16	0	0	16

Включение ребра (5,1) проводится путем исключения всех элементов 5-ой строки и 1-го столбца, в которой элемент d₁₅заменяем на М, для исключения образования негамильтонова цикла. В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения. Сумма констант приведения сокращенной матрицы: ∑d_i + ∑d_j = 0 После операции приведения сокращенная матрица будет иметь вид:

i j	6	7	di
1	0	M	0
3	7	0	0
dj	0	0	0

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