Исходная матрица имеет вид: A B C D A M 5 3 5 B 6 M 6

Исходная матрица имеет вид: A B C D A M 5 3 5 B 6 M 6 7 C 3 5 M 5 D 6 7 3 M В рассматриваемом примере у нас 4 города (обозначенных буквами латинского алфавита) и в таблице указано расстояние от каждого города к 3-м другим. Названия строк соответствуют городам отправления, названия столбцов — городам назначения Требуется Найти самый выгодный маршрута (с точки зрения минимизации пройденного расстояния), проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город.

Возьмем в качестве произвольного маршрута:
X0 = (1,2) ;(2,3) ;(3,4) ;(4,1)
Тогда F(X0) = 5 + 6 + 5 + 6 = 22
Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент.
di = min(j) dij
i/j 1 2 3 4 di
1 M 5 3 5 3
2 6 M 6 7 6
3 3 5 M 5 3
4 6 7 3 M 3
Затем вычитаем di из элементов рассматриваемой строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
i/j 1 2 3 4
1 M 2 0 2
2 0 M 0 1
3 0 2 M 2
4 3 4 0 M
Такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
dj = min(i) dij
i/j 1 2 3 4
1 M 2 0 2
2 0 M 0 1
3 0 2 M 2
4 3 4 0 M
dj
0 2 0 1
После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины di и dj называются константами приведения.
i/j 1 2 3 4
1 M 0 0 1
2 0 M 0 0
3 0 0 M 1
4 3 2 0 M
Сумма констант приведения определяет нижнюю границу H:
H = ∑di + ∑dj
H = 3+6+3+3+0+2+0+1 = 18
Элементы матрицы dij соответствуют расстоянию от пункта i до пункта j.
Поскольку в матрице n городов, то D является матрицей nxn с неотрицательными элементами dij ≥ 0
Каждый допустимый маршрут представляет собой цикл, по которому коммивояжер посещает город только один раз и возвращается в исходный город.
Длина маршрута определяется выражением:
F(Mk) = ∑dij
Причем каждая строка и столбец входят в маршрут только один раз с элементом dij.
Шаг №1.
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
i/j 1 2 3 4 di
1 M 0(0) 0(0) 1 0
2 0(0) M 0(0) 0(1) 0
3 0(0) 0(0) M 1 0
4 3 2 0(2) M 2
dj
0 0 0 1 0
d(1,2) = 0 + 0 = 0; d(1,3) = 0 + 0 = 0; d(2,1) = 0 + 0 = 0; d(2,3) = 0 + 0 = 0; d(2,4) = 0 + 1 = 1; d(3,1) = 0 + 0 = 0; d(3,2) = 0 + 0 = 0; d(4,3) = 2 + 0 = 2;
Наибольшая сумма констант приведения равна (2 + 0) = 2 для ребра (4,3), следовательно, множество разбивается на два подмножества (4,3) и (4*,3*).
Исключение ребра (4,3) проводим путем замены элемента d43 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (4*,3*), в результате получим редуцированную матрицу.
i/j 1 2 3 4 di
1 M 0 0 1 0
2 0 M 0 0 0
3 0 0 M 1 0
4 3 2 M M 2
dj
0 0 0 0 2
Нижняя граница гамильтоновых циклов этого подмножества:H(4*,3*) = 18 + 2 = 20
Включение ребра (4,3) проводится путем исключения всех элементов 4-ой строки и 3-го столбца, в которой элемент d34 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (3 x 3), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
i j 1 2 4 di
1 M 0 1 0
2 0 M 0 0
3 0 0 M 0
dj
0 0 0 0
Сумма констант приведения сокращенной матрицы:∑di + ∑dj = 0
Нижняя граница подмножества (4,3) равна:H(4,3) = 18 + 0 = 18 ≤ 20
Поскольку нижняя граница этого подмножества (4,3) меньше, чем подмножества (4*,3*), то ребро (4,3) включаем в маршрут с новой границей H = 18
Шаг №2.
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
i/j 1 2 4 di
1 M 0(1) 1 1
2 0(0) M 0(1) 0
3 0(0) 0(0) M 0
dj
0 0 1 0
d(1,2) = 1 + 0 = 1; d(2,1) = 0 + 0 = 0; d(2,4) = 0 + 1 = 1; d(3,1) = 0 + 0 = 0; d(3,2) = 0 + 0 = 0;
Наибольшая сумма констант приведения равна (1 + 0) = 1 для ребра (1,2), следовательно, множество разбивается на два подмножества (1,2) и (1*,2*).
Исключение ребра (1,2) проводим путем замены элемента d12 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (1*,2*), в результате получим редуцированную матрицу.
i/j 1 2 4 di
1 M M 1 1
2 0 M 0 0
3 0 0 M 0
dj
0 0 0 1
Нижняя граница гамильтоновых циклов этого подмножества:H(1*,2*) = 18 + 1 = 19
Включение ребра (1,2) проводится путем исключения всех элементов 1-ой строки и 2-го столбца, в которой элемент d21 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
i/j 1 4 di
2 M 0 0
3 0 M 0
dj
0 0 0
Сумма констант приведения сокращенной матрицы:
∑di + ∑dj = 0
Нижняя граница подмножества (1,2) равна:
H(1,2) = 18 + 0 = 18 ≤ 19
Поскольку нижняя граница этого подмножества (1,2) меньше, чем подмножества (1*,2*), то ребро (1,2) включаем в маршрут с новой границей H = 18
В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (2,4) и (3,1).
В результате по дереву ветвлений гамильтонов цикл образуют ребра:(4,3), (3,1), (1,2), (2,4).
Длина маршрута равна F(Mk) = 18