Построение совмещенного графика взаимодействия транспорта

 

d(1,5) = 7 + 35 = 42; d(2,1) = 16 + 25 = 41; d(3,2) = 0 + 0 = 0; d(3,6) = 0 + 13 = 13; d(4,2) = 0 + 0 = 0; d(4,3) = 0 + 4 = 4; d(5,4) = 24 + 0 = 24; d(6,4) = 4 + 0 = 4; 

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

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

i  j	1	2	3	4	5	6	di
1	Х	70	7	48	Х	82	7
2	0	Х	40	16	41	81	0
3	25	0	Х	104	36	0	0
4	67	0	0	Х	35	13	0
5	30	38	24	0	Х	69	0
6	57	37	4	0	51	Х	0
dj	0	0	0	0	35	0	42

 

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

H(1*,5*) = 348 + 42 = 390

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

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

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

i  j	1	2	3	4	6	di
2	0	Х	40	16	81	0
3	25	0	Х	104	0	0
4	67	0	0	Х	13	0
5	Х	38	24	0	69	0
6	57	37	4	0	Х	0
dj	0	0	0	0	0	0

 

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

∑di + ∑dj = 0

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

H(1,5) = 348 + 0 = 348  ≤  390

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

Шаг №2.

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

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

i  j	1	2	3	4	6	di
2	0(41)	Х	40	16	81	16
3	25	0(0)	Х	104	0(13)	0
4	67	0(0)	0(4)	Х	13	0
5	Х	38	24	0(24)	69	24
6	57	37	4	0(4)	Х	4
dj	25	0	4	0	13	0

 

d(2,1) = 16 + 25 = 41; d(3,2) = 0 + 0 = 0; d(3,6) = 0 + 13 = 13; d(4,2) = 0 + 0 = 0; d(4,3) = 0 + 4 = 4; d(5,4) = 24 + 0 = 24; d(6,4) = 4 + 0 = 4; 

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

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

i  j	1	2	3	4	6	di
2	Х	Х	40	16	81	16
3	25	0	Х	104	0	0
4	67	0	0	Х	13	0
5	Х	38	24	0	69	0
6	57	37	4	0	Х	0
dj	25	0	0	0	0	41

 

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

H(2*,1*) = 348 + 41 = 389

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

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

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

 

i  j	2	3	4	6	di
3	0	Х	104	0	0
4	0	0	Х	13	0
5	38	24	0	69	0
6	37	4	0	Х	0
dj	0	0	0	0	0

 

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

∑di + ∑dj = 0

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

H(2,1) = 348 + 0 = 348  ≤  389

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

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

Шаг №3.

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

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

i  j	2	3	4	6	di
3	0(0)	Х	104	0(13)	0
4	0(0)	0(4)	Х	13	0
5	Х	24	0(24)	69	24
6	37	4	0(4)	Х	4
dj	0	4	0	13	0

 

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

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

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

 

i  j	2	3	4	6	di
3	0	Х	104	0	0
4	0	0	Х	13	0
5	Х	24	Х	69	24
6	37	4	0	Х	0
dj	0	0	0	0	24

 

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

H(5*,4*) = 348 + 24 = 372

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

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

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

 

i  j	2	3	6	di
3	0	Х	0	0
4	0	0	13	0
6	37	4	Х	4
dj	0	0	0	4

 

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

∑di + ∑dj = 4

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

H(5,4) = 348 + 4 = 352  ≤  372

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

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

Шаг №4.

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

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

i  j	2	3	6	di
3	0(33)	Х	0(13)	0
4	Х	0(13)	13	13
6	33	0(33)	Х	33
dj	33	0	13	0