Исходные данные:
Пункты (узлы) | Исх.1 | |||||
Исх.1 | - | |||||
- | ||||||
- | ||||||
- | ||||||
- | ||||||
- |
Решение:
Возьмем в качестве произвольного маршрута:
X0 = (1,2);(2,3);(3,4);(4,5);(5,6);(6,1)
Тогда F(X0) = 33 + 22 + 37 + 28 + 13 + 33 = 166
Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент.
di = min(j) dij
i j | di | ||||||
M | |||||||
M | |||||||
M | |||||||
M | |||||||
M | |||||||
M |
Затем вычитаем di из элементов рассматриваемой строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
i j | ||||||
M | ||||||
M | ||||||
M | ||||||
M | ||||||
M | ||||||
M |
Такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
dj = min(i) dij
i j | ||||||
M | ||||||
M | ||||||
M | ||||||
M | ||||||
M | ||||||
M | ||||||
dj |
После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины di и dj называются константами приведения.
|
i j | ||||||
M | ||||||
M | ||||||
M | ||||||
M | ||||||
M | ||||||
M |
Сумма констант приведения определяет нижнюю границу H:
H = ∑di + ∑dj
H = 17+7+8+17+13+7+0+0+0+0+4+0 = 73
Элементы матрицы dij соответствуют расстоянию от пункта i до пункта j.
Поскольку в матрице n городов, то D является матрицей nxn с неотрицательными элементами dij ≥ 0
Каждый допустимый маршрут представляет собой цикл, по которому коммивояжер посещает город только один раз и возвращается в исходный город.
Длина маршрута определяется выражением:
F(Mk) = ∑dij
Причем каждая строка и столбец входят в маршрут только один раз с элементом dij.
Шаг №1.
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
i j | di | ||||||
M | 0(17) | ||||||
0(6) | M | ||||||
M | 0(1) | 0(0) | |||||
0(10) | M | ||||||
M | 0(4) | ||||||
0(15) | M | ||||||
dj |
d(1,4) = 15 + 2 = 17; d(2,1) = 2 + 4 = 6; d(3,5) = 0 + 1 = 1; d(3,6) = 0 + 0 = 0; d(4,2) = 5 + 5 = 10; d(5,6) = 4 + 0 = 4; d(6,3) = 1 + 14 = 15;
|
Наибольшая сумма констант приведения равна (15 + 2) = 17 для ребра (1,4), следовательно, множество разбивается на два подмножества (1,4) и (1*,4*).
Исключение ребра (1,4) проводим путем замены элемента d14 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (1*,4*), в результате получим редуцированную матрицу.
i j | di | ||||||
M | M | ||||||
M | |||||||
M | |||||||
M | |||||||
M | |||||||
M | |||||||
dj |
Нижняя граница гамильтоновых циклов этого подмножества:
H(1*,4*) = 73 + 17 = 90
Включение ребра (1,4) проводится путем исключения всех элементов 1-ой строки и 4-го столбца, в которой элемент d41 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (5 x 5), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
i j | di | |||||
M | ||||||
M | ||||||
M | ||||||
M | ||||||
M | ||||||
dj |
Сумма констант приведения сокращенной матрицы:
∑di + ∑dj = 0
Нижняя граница подмножества (1,4) равна:
H(1,4) = 73 + 0 = 73 ≤ 90
Поскольку нижняя граница этого подмножества (1,4) меньше, чем подмножества (1*,4*), то ребро (1,4) включаем в маршрут с новой границей H = 73
|
Шаг №2.
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
i j | di | |||||
0(19) | M | |||||
M | 0(1) | 0(0) | ||||
M | 0(10) | |||||
M | 0(4) | |||||
0(15) | M | |||||
dj |
d(2,1) = 15 + 4 = 19; d(3,5) = 0 + 1 = 1; d(3,6) = 0 + 0 = 0; d(4,2) = 5 + 5 = 10; d(5,6) = 4 + 0 = 4; d(6,3) = 1 + 14 = 15;
Наибольшая сумма констант приведения равна (15 + 4) = 19 для ребра (2,1), следовательно, множество разбивается на два подмножества (2,1) и (2*,1*).
Исключение ребра (2,1) проводим путем замены элемента d21 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (2*,1*), в результате получим редуцированную матрицу.
i j | di | |||||
M | M | |||||
M | ||||||
M | ||||||
M | ||||||
M | ||||||
dj |
Нижняя граница гамильтоновых циклов этого подмножества:
H(2*,1*) = 73 + 19 = 92
Включение ребра (2,1) проводится путем исключения всех элементов 2-ой строки и 1-го столбца, в которой элемент d12 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (4 x 4), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
i j | di | ||||
M | |||||
M | |||||
M | |||||
dj |
Сумма констант приведения сокращенной матрицы:
∑di + ∑dj = 0
Нижняя граница подмножества (2,1) равна:
H(2,1) = 73 + 0 = 73 ≤ 92
Чтобы исключить подциклы, запретим следующие переходы: (4,2),
Поскольку нижняя граница этого подмножества (2,1) меньше, чем подмножества (2*,1*), то ребро (2,1) включаем в маршрут с новой границей H = 73
Шаг №3.
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
i j | di | ||||
M | 0(1) | 0(0) | |||
M | 0(2) | ||||
M | 0(14) | ||||
0(9) | 0(11) | M | |||
dj |
d(3,5) = 0 + 1 = 1; d(3,6) = 0 + 0 = 0; d(4,6) = 2 + 0 = 2; d(5,6) = 14 + 0 = 14; d(6,2) = 0 + 9 = 9; d(6,3) = 0 + 11 = 11;
Наибольшая сумма констант приведения равна (14 + 0) = 14 для ребра (5,6), следовательно, множество разбивается на два подмножества (5,6) и (5*,6*).
Исключение ребра (5,6) проводим путем замены элемента d56 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (5*,6*), в результате получим редуцированную матрицу.
i j | di | ||||
M | |||||
M | |||||
M | M | ||||
M | |||||
dj |
Нижняя граница гамильтоновых циклов этого подмножества:
H(5*,6*) = 73 + 14 = 87
Включение ребра (5,6) проводится путем исключения всех элементов 5-ой строки и 6-го столбца, в которой элемент d65 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (3 x 3), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
i j | di | |||
M | ||||
M | ||||
M | ||||
dj |
Сумма констант приведения сокращенной матрицы:
∑di + ∑dj = 2
Нижняя граница подмножества (5,6) равна:
H(5,6) = 73 + 2 = 75 ≤ 87
Чтобы исключить подциклы, запретим следующие переходы: (4,2),
Поскольку нижняя граница этого подмножества (5,6) меньше, чем подмножества (5*,6*), то ребро (5,6) включаем в маршрут с новой границей H = 75
Шаг №4.
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
i j | di | |||
M | 0(9) | |||
M | 0(9) | |||
0(9) | 0(9) | M | ||
dj |
d(3,5) = 9 + 0 = 9; d(4,5) = 9 + 0 = 9; d(6,2) = 0 + 9 = 9; d(6,3) = 0 + 9 = 9;
Наибольшая сумма констант приведения равна (0 + 9) = 9 для ребра (6,2), следовательно, множество разбивается на два подмножества (6,2) и (6*,2*).
Исключение ребра (6,2) проводим путем замены элемента d62 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (6*,2*), в результате получим редуцированную матрицу.
i j | di | |||
M | ||||
M | ||||
M | M | |||
dj |
Нижняя граница гамильтоновых циклов этого подмножества:
H(6*,2*) = 75 + 9 = 84
Включение ребра (6,2) проводится путем исключения всех элементов 6-ой строки и 2-го столбца, в которой элемент d26 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
i j | di | ||
M | |||
dj |
Сумма констант приведения сокращенной матрицы:
∑di + ∑dj = 9
Нижняя граница подмножества (6,2) равна:
H(6,2) = 75 + 9 = 84 ≤ 84
Поскольку нижние границы подмножества (6,2) и подмножества (6*,2*) равны, то ребро (6,2) включаем в маршрут с новой границей H = 84
В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (3,5) и (4,3).
В результате по дереву ветвлений гамильтонов цикл образуют ребра:
(1,4), (4,3), (3,5), (5,6), (6,2), (2,1),
Длина маршрута равна F(Mk) = 94