|
Возьмем в качестве произвольного маршрута:
X0 = (1,2);(2,3);(3,4);(4,5);(5,6);(6,1)
Тогда F(X0) = 16 + 11 + 3 + 9 + 8 + 5 = 52
Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент.
di = min(j) dij
i j 1 2 3 4 5 6 di
1 M 16 17 3 6 12 3
2 14 M 11 1 0 15 0
3 9 0 M 3 6 6 0
4 0 0 10 M 9 7 0
5 3 4 1 16 M 8 1
6 5 8 0 10 4 M 0
Затем вычитаем di из элементов рассматриваемой строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
i j 1 2 3 4 5 6
1 M 13 14 0 3 9
2 14 M 11 1 0 15
3 9 0 M 3 6 6
4 0 0 10 M 9 7
5 2 3 0 15 M 7
6 5 8 0 10 4 M
Такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
dj = min(i) dij
i j 1 2 3 4 5 6
1 M 13 14 0 3 9
2 14 M 11 1 0 15
3 9 0 M 3 6 6
4 0 0 10 M 9 7
5 2 3 0 15 M 7
6 5 8 0 10 4 M
dj 0 0 0 0 0 6
После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины di и dj называютсяконстантами приведения.
i j 1 2 3 4 5 6
1 M 13 14 0 3 3
2 14 M 11 1 0 9
3 9 0 M 3 6 0
4 0 0 10 M 9 1
5 2 3 0 15 M 1
6 5 8 0 10 4 M
Сумма констант приведения определяет нижнюю границу H:
H = ∑di + ∑dj
H = 3+0+0+0+1+0+0+0+0+0+0+6 = 10
Элементы матрицы 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 13 14 0(4) 3 3 3
2 14 M 11 1 0(4) 9 1
3 9 0(0) M 3 6 0(1) 0
4 0(2) 0(0) 10 M 9 1 0
5 2 3 0(1) 15 M 1 1
6 5 8 0(4) 10 4 M 4
dj 2 0 0 1 3 1 0
d(1,4) = 3 + 1 = 4; d(2,5) = 1 + 3 = 4; d(3,2) = 0 + 0 = 0; d(3,6) = 0 + 1 = 1; d(4,1) = 0 + 2 = 2; d(4,2) = 0 + 0 = 0; d(5,3) = 1 + 0 = 1; d(6,3) = 4 + 0 = 4;
Наибольшая сумма констант приведения равна (3 + 1) = 4 для ребра (1,4), следовательно, множество разбивается на два подмножества (1,4) и (1*,4*).
Исключение ребра (1,4) проводим путем замены элемента d14 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (1*,4*), в результате получим редуцированную матрицу.
ВОПРОС: Сумма констант приведения у трех ребер одинакова= 4. Почему выбрали ребро (1,4)?
|
21.09.2014, 17:37 
ом