Имеется необходимость посетить 6 городов в ходе деловой поездки

Возьмем в качестве произвольного маршрута:X0 = (1,2);(2,3);(3,4);(4,5);(5,6);(6,1)
Тогда F(X0) = 9 + 1 + 6 + 4 + 3 + 6 = 29
Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент.
di = min(j) dij
i j 1 2 3 4 5 6 di
1 M 9 7 1 1 1 1
2 9 M 1 7 2 2 1
3 6 2 M 6 7 1 1
4 8 10 1 M 4 9 1
5 5 1 7 10 M 3 1
6 6 10 10 10 5 M 5
Затем вычитаем di из элементов рассматриваемой строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
i j 1 2 3 4 5 6
1 M 8 6 0 0 0
2 8 M 0 6 1 1
3 5 1 M 5 6 0
4 7 9 0 M 3 8
5 4 0 6 9 M 2
6 1 5 5 5 0 M
Такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
dj = min(i) dij
i j 1 2 3 4 5 6
1 M 8 6 0 0 0
2 8 M 0 6 1 1
3 5 1 M 5 6 0
4 7 9 0 M 3 8
5 4 0 6 9 M 2
6 1 5 5 5 0 M
dj
1 0 0 0 0 0
После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины di и dj называются константами приведения.
i j 1 2 3 4 5 6
1 M 8 6 0 0 0
2 7 M 0 6 1 1
3 4 1 M 5 6 0
4 6 9 0 M 3 8
5 3 0 6 9 M 2
6 0 5 5 5 0 M
Сумма констант приведения определяет нижнюю границу H:H = ∑di + ∑djH = 1+1+1+1+1+5+1+0+0+0+0+0 = 11
Элементы матрицы dij соответствуют расстоянию от пункта i до пункта j.
Поскольку в матрице n городов, то D является матрицей nxn с неотрицательными элементами dij ≥ 0
Каждый допустимый маршрут представляет собой цикл, по которому коммивояжер посещает город только один раз и возвращается в исходный город.
Длина маршрута определяется выражением:
F(Mk) = ∑dij
Причем каждая строка и столбец входят в маршрут только один раз с элементом dij.
Шаг №1.
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
i j 1 2 3 4 5 6 di
1 M 8 6 0(5) 0(0) 0(0) 0
2 7 M 0(1) 6 1 1 1
3 4 1 M 5 6 0(1) 1
4 6 9 0(3) M 3 8 3
5 3 0(3) 6 9 M 2 2
6 0(3) 5 5 5 0(0) M 0
dj
3 1 0 5 0 0 0
d(1,4) = 0 + 5 = 5;
d(1,5) = 0 + 0 = 0;
d(1,6) = 0 + 0 = 0;
d(2,3) = 1 + 0 = 1;
d(3,6) = 1 + 0 = 1;
d(4,3) = 3 + 0 = 3;
d(5,2) = 2 + 1 = 3;
d(6,1) = 0 + 3 = 3;
d(6,5) = 0 + 0 = 0.
Наибольшая сумма констант приведения равна (0 + 5) = 5 для ребра (1,4), следовательно, множество разбивается на два подмножества (1,4) и (1*,4*).
Исключение ребра (1,4) проводим путем замены элемента d14 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (1*,4*), в результате получим редуцированную матрицу.
i j 1 2 3 4 5 6 di
1 M 8 6 M 0 0 0
2 7 M 0 6 1 1 0
3 4 1 M 5 6 0 0
4 6 9 0 M 3 8 0
5 3 0 6 9 M 2 0
6 0 5 5 5 0 M 0
dj
0 0 0 5 0 0 5
Нижняя граница гамильтоновых циклов этого подмножества:H(1*,4*) = 11 + 5 = 16
Включение ребра (1,4) проводится путем исключения всех элементов 1-ой строки и 4-го столбца, в которой элемент d41 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (5 x 5), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
i j 1 2 3 5 6 di
2 7 M 0 1 1 0
3 4 1 M 6 0 0
4 M 9 0 3 8 0
5 3 0 6 M 2 0
6 0 5 5 0 M 0
dj
0 0 0 0 0 0
Сумма констант приведения сокращенной матрицы:∑di + ∑dj = 0
Нижняя граница подмножества (1,4) равна:H(1,4) = 11 + 0 = 11 ≤ 16
Поскольку нижняя граница этого подмножества (1,4) меньше, чем подмножества (1*,4*), то ребро (1,4) включаем в маршрут с новой границей H = 11
Шаг №2.
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
i j 1 2 3 5 6 di
2 7 M 0(1) 1 1 1
3 4 1 M 6 0(2) 1
4 M 9 0(3) 3 8 3
5 3 0(3) 6 M 2 2
6 0(3) 5 5 0(1) M 0
dj
3 1 0 1 1 0
d(2,3) = 1 + 0 = 1;
d(3,6) = 1 + 1 = 2;
d(4,3) = 3 + 0 = 3;
d(5,2) = 2 + 1 = 3;
d(6,1) = 0 + 3 = 3;
d(6,5) = 0 + 1 = 1.
Наибольшая сумма констант приведения равна (0 + 3) = 3 для ребра (6,1), следовательно, множество разбивается на два подмножества (6,1) и (6*,1*).
Исключение ребра (6,1) проводим путем замены элемента d61 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (6*,1*), в результате получим редуцированную матрицу.
i j 1 2 3 5 6 di
2 7 M 0 1 1 0
3 4 1 M 6 0 0
4 M 9 0 3 8 0
5 3 0 6 M 2 0
6 M 5 5 0 M 0
dj
3 0 0 0 0 3
Нижняя граница гамильтоновых циклов этого подмножества:
H(6*,1*) = 11 + 3 = 14
Включение ребра (6,1) проводится путем исключения всех элементов 6-ой строки и 1-го столбца, в которой элемент d16 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (4 x 4), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
i j 2 3 5 6 di
2 M 0 1 1 0
3 1 M 6 0 0
4 9 0 3 8 0
5 0 6 M 2 0
dj
0 0 1 0 1
Сумма констант приведения сокращенной матрицы:∑di + ∑dj = 1
Нижняя граница подмножества (6,1) равна:H(6,1) = 11 + 1 = 12 ≤ 14
Чтобы исключить подциклы, запретим следующие переходы: (4,6),Поскольку нижняя граница этого подмножества (6,1) меньше, чем подмножества (6*,1*), то ребро (6,1) включаем в маршрут с новой границей H = 12
Шаг №3.
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
i j 2 3 5 6 di
2 M 0(0) 0(2) 1 0
3 1 M 5 0(2) 1
4 9 0(2) 2 M 2
5 0(3) 6 M 2 2
dj
1 0 2 1 0
d(2,3) = 0 + 0 = 0;
d(2,5) = 0 + 2 = 2;
d(3,6) = 1 + 1 = 2;
d(4,3) = 2 + 0 = 2;
d(5,2) = 2 + 1 = 3.
Наибольшая сумма констант приведения равна (2 + 1) = 3 для ребра (5,2), следовательно, множество разбивается на два подмножества (5,2) и (5*,2*).
Исключение ребра (5,2) проводим путем замены элемента d52 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (5*,2*), в результате получим редуцированную матрицу.
i j 2 3 5 6 di
2 M 0 0 1 0
3 1 M 5 0 0
4 9 0 2 M 0
5 M 6 M 2 2
dj
1 0 0 0 3
Нижняя граница гамильтоновых циклов этого подмножества:H(5*,2*) = 12 + 3 = 15
Включение ребра (5,2) проводится путем исключения всех элементов 5-ой строки и 2-го столбца, в которой элемент d25 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (3 x 3), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
i j 3 5 6 di
2 0 M 1 0
3 M 5 0 0
4 0 2 M 0
dj
0 2 0 2
Сумма констант приведения сокращенной матрицы:∑di + ∑dj = 2
Нижняя граница подмножества (5,2) равна:H(5,2) = 12 + 2 = 14 ≤ 15
Чтобы исключить подциклы, запретим следующие переходы: (4,6),
Поскольку нижняя граница этого подмножества (5,2) меньше, чем подмножества (5*,2*), то ребро (5,2) включаем в маршрут с новой границей H = 14
Шаг №4.
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
i j 3 5 6 di
2 0(1) M 1 1
3 M 3 0(4) 3
4 0(0) 0(3) M 0
dj
0 3 1 0
d(2,3) = 1 + 0 = 1;
d(3,6) = 3 + 1 = 4;
d(4,3) = 0 + 0 = 0;
d(4,5) = 0 + 3 = 3.
Наибольшая сумма констант приведения равна (3 + 1) = 4 для ребра (3,6), следовательно, множество разбивается на два подмножества (3,6) и (3*,6*).
Исключение ребра (3,6) проводим путем замены элемента d36 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (3*,6*), в результате получим редуцированную матрицу.
i j 3 5 6 di
2 0 M 1 0
3 M 3 M 3
4 0 0 M 0
dj
0 0 1 4
Нижняя граница гамильтоновых циклов этого подмножества:H(3*,6*) = 14 + 4 = 18
Включение ребра (3,6) проводится путем исключения всех элементов 3-ой строки и 6-го столбца, в которой элемент d63 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
i j 3 5 di
2 0 M 0
4 0 0 0
dj
0 0 0
Сумма констант приведения сокращенной матрицы:∑di + ∑dj = 0
Нижняя граница подмножества (3,6) равна:H(3,6) = 14 + 0 = 14 ≤ 18
Поскольку нижняя граница этого подмножества (3,6) меньше, чем подмножества (3*,6*), то ребро (3,6) включаем в маршрут с новой границей H = 14
В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (2,3) и (4,5).
В результате по дереву ветвлений гамильтонов цикл образуют ребра:(1,4), (4,5), (5,2), (2,3), (3,6), (6,1),
Оптимальный путь: 1→4→5→2→3→6→1.
Длина маршрута равна F(Mk) = 14.