Задача коммивояжера. Пример

Решение.
Возьмем в качестве произвольного маршрута:
X0 = (1,2);(2,3);(3,1)
Тогда F(X0) = 22 + 22 + 12 = 56
Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент.
di = min(j) dij

i  j

1

2

3

di

1

M

22

44

22

2

55

M

22

22

3

12

43

M

12


 
Затем вычитаем di из элементов рассматриваемой строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.

i  j

1

2

3

1

M

0

22

2

33

M

0

3

0

31

M


 
Такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
dj = min(i) dij

i  j

1

2

3

1

M

0

22

2

33

M

0

3

0

31

M

dj

0

0

0


 
После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины di и dj называются константами приведения.

i  j

1

2

3

1

M

0

22

2

33

M

0

3

0

31

M


 
Сумма констант приведения определяет нижнюю границу H:
H = ∑di + ∑dj
H = 22+22+12+0+0+0 = 56
Элементы матрицы dij соответствуют расстоянию от пункта i до пункта j.
Поскольку в матрице n городов, то D является матрицей nxn с неотрицательными элементами dij >=0
Каждый допустимый маршрут представляет собой цикл, по которому коммивояжер посещает город только один раз и возвращается в исходный город.
Длина маршрута определяется выражением:
F(Mk) = ∑dij
Причем каждая строка и столбец входят в маршрут только один раз с элементом dij .
Шаг №1.
Определяем ребро ветвления  и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

i  j

1

2

3

di

1

M

0(53)

22

22

2

33

M

0(55)

33

3

0(64)

31

M

31

dj

33

31

22

0


 
d(1,2) = 22 + 31 = 53; d(2,3) = 33 + 22 = 55; d(3,1) = 31 + 33 = 64;
Наибольшая сумма констант приведения равна (31 + 33) = 64 для ребра (3,1), следовательно, множество разбивается на два подмножества (3,1) и (3*,1*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(3*,1*) = 56 + 64 = 120
Исключение ребра (3,1) проводим путем замены элемента d31 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (3*,1*), в результате получим редуцированную матрицу.

i  j

1

2

3

di

1

M

0

22

0

2

33

M

0

0

3

M

31

M

31

dj

33

0

0

64


 
Включение ребра (3,1) проводится путем исключения всех элементов 3-ой строки и 1-го столбца, в которой элемент d13 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑di + ∑dj = 0
После операции приведения сокращенная матрица будет иметь вид:

i  j

2

3

di

1

0

M

0

2

M

0

0

dj

0

0

0


 
Нижняя граница подмножества (3,1) равна:
H(3,1) = 56 + 0 = 56  <  120
Поскольку нижняя граница этого подмножества (3,1) меньше, чем подмножества (3*,1*), то ребро (3,1) включаем в маршрут.
Поскольку 56 ≥ 56, исключаем подмножество (3,1) для дальнейшего ветвления.
Возвращаемся к прежнему плану X2.
В результате по дереву ветвлений гамильтонов цикл образуют ребра:
для первого плана X0. F(X0) = 56
 
Решение было получено и оформлено с помощью сервиса:
Задача коммивояжера
загрузка...