Пример решения задачи коммивояжера

Имеется необходимость посетить n городов в ходе деловой поездки. Спланировать поездку нужно так, чтобы, переезжая из города в город, побывать в каждом не более одного раза и вернуться в исходный город. Определить оптимальный маршрут посещения городов и его минимальное расстояние.
Задана матрица расстояний между городами cij.

Решение проводим с помощью калькулятора Решение задачи коммивояжера. Возьмем в качестве произвольного маршрута:
X0 = (1,2);(2,3);(3,4);(4,5);(5,6);(6,7);(7,1)
Тогда F(X0) = 20 + 20 + 16 + 9 + 21 + 18 + 12 = 116
Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент.
di = min(j) dij


  i  j

 1

 2

 3

 4

 5

 6

 7

 di

 1

 M

 20

 20

 16

 13

 16

 20

 13

 2

 18

 M

 20

 16

 12

 13

 18

 12

 3

 16

 14

 M

 16

 M

 21

 14

 14

 4

 16

 9

 14

 M

 9

 19

 22

 9

 5

 M

 12

 19

 20

 M

 21

 12

 12

 6

 11

 11

 22

 22

 14

 M

 18

 11

 7

 12

 12

 9

 M

 16

 15

 M

 9

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

 i  j

 1

 2

 3

 4

 5

 6

 7

 1

 M

 7

 7

 3

 0

 3

 7

 2

 6

 M

 8

 4

 0

 1

 6

 3

 2

 0

 M

 2

 M

 7

 0

 4

 7

 0

 5

 M

 0

 10

 13

 5

 M

 0

 7

 8

 M

 9

 0

 6

 0

 0

 11

 11

 3

 M

 7

 7

 3

 3

 0

 M

 7

 6

 M

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

  i  j

 1

 2

 3

 4

 5

 6

 7

 1

 M

 7

 7

 3

 0

 3

 7

 2

 6

 M

 8

 4

 0

 1

 6

 3

 2

 0

 M

 2

 M

 7

 0

 4

 7

 0

 5

 M

 0

 10

 13

 5

 M

 0

 7

 8

 M

 9

 0

 6

 0

 0

 11

 11

 3

 M

 7

 7

 3

 3

 0

 M

 7

 6

 M

 dj

 0

 0

 0

 2

 0

 1

 0

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

 i  j

 1

 2

 3

 4

 5

 6

 7

 1

 M

 7

 7

 1

 0

 2

 7

 2

 6

 M

 8

 2

 0

 0

 6

 3

 2

 0

 M

 0

 M

 6

 0

 4

 7

 0

 5

 M

 0

 9

 13

 5

 M

 0

 7

 6

 M

 8

 0

 6

 0

 0

 11

 9

 3

 M

 7

 7

 3

 3

 0

 M

 7

 5

 M

Сумма констант приведения определяет нижнюю границу H:
H = 13+12+14+9+12+11+9+0+0+0+2+0+1+0 = 83
Элементы матрицы dij соответствуют расстоянию от пункта i до пункта j.
Поскольку в матрице n городов, то D является матрицей nxn с неотрицательными элементами d ij >=0
Каждый допустимый маршрут представляет собой цикл, по которому коммивояжер посещает город только один раз и возвращается в исходный город.
Длина маршрута определяется выражением:
Причем каждая строка и столбец входят в маршрут только один раз с элементом dij .
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

 i  j

 1

 2

 3

 4

 5

 6

 7

 di

 1

 M

 7

 7

 1

 0(1)

 2

 7

 1

 2

 6

 M

 8

 2

 0(0)

 0(2)

 6

 0

 3

 2

 0(0)

 M

 0(1)

 M

 6

 0(0)

 0

 4

 7

 0(0)

 5

 M

 0(0)

 9

 13

 0

 5

 M

 0(0)

 7

 6

 M

 8

 0(0)

 0

 6

 0(2)

 0(0)

 11

 9

 3

 M

 7

 0

 7

 3

 3

 0(8)

 M

 7

 5

 M

 3

 dj

 2

 0

 5

 1

 0

 2

 0

 0

d(1,5) = 1 + 0 = 1; d(2,5) = 0 + 0 = 0; d(2,6) = 0 + 2 = 2; d(3,2) = 0 + 0 = 0; d(3,4) = 0 + 1 = 1; d(3,7) = 0 + 0 = 0; d(4,2) = 0 + 0 = 0; d(4,5) = 0 + 0 = 0; d(5,2) = 0 + 0 = 0; d(5,7) = 0 + 0 = 0; d(6,1) = 0 + 2 = 2; d(6,2) = 0 + 0 = 0; d(7,3) = 3 + 5 = 8;
Наибольшая сумма констант приведения равна (3 + 5) = 8 для ребра (7,3), следовательно, множество разбивается на два подмножества (7,3) и (7*,3*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(7*,3*) = 83 + 8 = 91
Исключение ребра (7,3) проводим путем замены элемента d73 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (7*,3*), в результате получим редуцированную матрицу.

 i  j

 1

 2

 3

 4

 5

 6

 7

 di

 1

 M

 7

 7

 1

 0

 2

 7

 0

 2

 6

 M

 8

 2

 0

 0

 6

 0

 3

 2

 0

 M

 0

 M

 6

 0

 0

 4

 7

 0

 5

 M

 0

 9

 13

 0

 5

 M

 0

 7

 6

 M

 8

 0

 0

 6

 0

 0

 11

 9

 3

 M

 7

 0

 7

 3

 3

 M

 M

 7

 5

 M

 3

 dj

 0

 0

 5

 0

 0

 0

 0

 8

Включение ребра (7,3) проводится путем исключения всех элементов 7-ой строки и 3-го столбца, в которой элемент d37 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (6 x 6), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:

После операции приведения сокращенная матрица будет иметь вид:

 i  j

 1

 2

 4

 5

 6

 7

 di

 1

 M

 7

 1

 0

 2

 7

 0

 2

 6

 M

 2

 0

 0

 6

 0

 3

 2

 0

 0

 M

 6

 M

 0

 4

 7

 0

 M

 0

 9

 13

 0

 5

 M

 0

 6

 M

 8

 0

 0

 6

 0

 0

 9

 3

 M

 7

 0

 dj

 0

 0

 0

 0

 0

 0

 0

Нижняя граница подмножества (7,3) равна:
H(7,3) = 83 + 0 = 83  <  91
Поскольку нижняя граница этого подмножества (7,3) меньше, чем подмножества (7*,3*), то ребро (7,3) включаем в маршрут.
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

 i  j

 1

 2

 4

 5

 6

 7

 di

 1

 M

 7

 1

 0(1)

 2

 7

 1

 2

 6

 M

 2

 0(0)

 0(2)

 6

 0

 3

 2

 0(0)

 0(1)

 M

 6

 M

 0

 4

 7

 0(0)

 M

 0(0)

 9

 13

 0

 5

 M

 0(0)

 6

 M

 8

 0(6)

 0

 6

 0(2)

 0(0)

 9

 3

 M

 7

 0

 dj

 2

 0

 1

 0

 2

 6

 0

d(1,4) = 1 + 0 = 1; d(2,4) = 0 + 0 = 0; d(2,5) = 0 + 2 = 2; d(3,2) = 0 + 0 = 0; d(3,3) = 0 + 1 = 1; d(4,2) = 0 + 0 = 0; d(4,4) = 0 + 0 = 0; d(5,2) = 0 + 0 = 0; d(5,6) = 0 + 6 = 6; d(6,1) = 0 + 2 = 2; d(6,2) = 0 + 0 = 0;
Наибольшая сумма констант приведения равна (0 + 6) = 6 для ребра (5,7), следовательно, множество разбивается на два подмножества (5,7) и (5*,7*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(5*,7*) = 83 + 6 = 89
Исключение ребра (5,7) проводим путем замены элемента d57 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (5*,7*), в результате получим редуцированную матрицу.

 i  j

 1

 2

 4

 5

 6

 7

 di

 1

 M

 7

 1

 0

 2

 7

 0

 2

 6

 M

 2

 0

 0

 6

 0

 3

 2

 0

 0

 M

 6

 M

 0

 4

 7

 0

 M

 0

 9

 13

 0

 5

 M

 0

 6

 M

 8

 M

 0

 6

 0

 0

 9

 3

 M

 7

 0

 dj

 0

 0

 0

 0

 0

 6

 6

Включение ребра (5,7) проводится путем исключения всех элементов 5-ой строки и 7-го столбца, в которой элемент d75 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (5 x 5), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:

После операции приведения сокращенная матрица будет иметь вид:

 i  j

 1

 2

 4

 5

 6

 di

 1

 M

 7

 1

 0

 2

 0

 2

 6

 M

 2

 0

 0

 0

 3

 2

 0

 0

 M

 6

 0

 4

 7

 0

 M

 0

 9

 0

 6

 0

 0

 9

 3

 M

 0

 dj

 0

 0

 0

 0

 0

 0

Нижняя граница подмножества (5,7) равна:
H(5,7) = 83 + 0 = 83  <  89
Чтобы исключить подциклы, запретим следующие переходы: (3,5),
Поскольку нижняя граница этого подмножества (5,7) меньше, чем подмножества (5*,7*), то ребро (5,7) включаем в маршрут.
Определяем ребро ветвления  и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) И (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

 i  j

 1

 2

 4

 5

 6

 di

 1

 M

 7

 1

 0(1)

 2

 1

 2

 6

 M

 2

 0(0)

 0(2)

 0

 3

 2

 0(0)

 0(1)

 M

 6

 0

 4

 7

 0(0)

 M

 0(0)

 9

 0

 6

 0(2)

 0(0)

 9

 3

 M

 0

 dj

 2

 0

 1

 0

 2

 0

d(1,4) = 1 + 0 = 1; d(2,4) = 0 + 0 = 0; d(2,5) = 0 + 2 = 2; d(3,2) = 0 + 0 = 0; d(3,3) = 0 + 1 = 1; d(4,2) = 0 + 0 = 0; d(4,4) = 0 + 0 = 0; d(5,1) = 0 + 2 = 2; d(5,2) = 0 + 0 = 0;
Наибольшая сумма констант приведения равна (0 + 2) = 2 для ребра (2,6), следовательно, множество разбивается на два подмножества (2,6) и (2*,6*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(2*,6*) = 83 + 2 = 85
Исключение ребра (2,6) проводим путем замены элемента d26 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (2*,6*), в результате получим редуцированную матрицу.

 i  j

 1

 2

 4

 5

 6

 di

 1

 M

 7

 1

 0

 2

 0

 2

 6

 M

 2

 0

 M

 0

 3

 2

 0

 0

 M

 6

 0

 4

 7

 0

 M

 0

 9

 0

 6

 0

 0

 9

 3

 M

 0

 dj

 0

 0

 0

 0

 2

 2

Включение ребра (2,6) проводится путем исключения всех элементов 2-ой строки и 6-го столбца, в которой элемент d62 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (4 x 4), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:

После операции приведения сокращенная матрица будет иметь вид:

 i  j

 1

 2

 4

 5

 di

 1

 M

 7

 1

 0

 0

 3

 2

 0

 0

 M

 0

 4

 7

 0

 M

 0

 0

 6

 0

 M

 9

 3

 0

 dj

 0

 0

 0

 0

 0

Нижняя граница подмножества (2,6) равна:
H(2,6) = 83 + 0 = 83  <  85
Чтобы исключить подциклы, запретим следующие переходы: (3,5),
Поскольку нижняя граница этого подмножества (2,6) меньше, чем подмножества (2*,6*), то ребро (2,6) включаем в маршрут.
Определяем ребро ветвления  и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

 i  j

 1

 2

 4

 5

 di

 1

 M

 7

 1

 0(1)

 1

 3

 2

 0(0)

 0(1)

 M

 0

 4

 7

 0(0)

 M

 0(0)

 0

 6

 0(5)

 M

 9

 3

 3

 dj

 2

 0

 1

 0

 0

d(1,4) = 1 + 0 = 1; d(2,2) = 0 + 0 = 0; d(2,3) = 0 + 1 = 1; d(3,2) = 0 + 0 = 0; d(3,4) = 0 + 0 = 0; d(4,1) = 3 + 2 = 5;
Наибольшая сумма констант приведения равна (3 + 2) = 5 для ребра (6,1), следовательно, множество разбивается на два подмножества (6,1) и (6*,1*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(6*,1*) = 83 + 5 = 88
Исключение ребра (6,1) проводим путем замены элемента d61 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (6*,1*), в результате получим редуцированную матрицу.

 i  j

 1

 2

 4

 5

 di

 1

 M

 7

 1

 0

 0

 3

 2

 0

 0

 M

 0

 4

 7

 0

 M

 0

 0

 6

 M

 M

 9

 3

 3

 dj

 2

 0

 0

 0

 5

Включение ребра (6,1) проводится путем исключения всех элементов 6-ой строки и 1-го столбца, в которой элемент d16 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (3 x 3), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:

После операции приведения сокращенная матрица будет иметь вид:

 i  j

 2

 4

 5

 di

 1

 7

 1

 0

 0

 3

 0

 0

 M

 0

 4

 0

 M

 0

 0

 dj

 0

 0

 0

 0

Нижняя граница подмножества (6,1) равна:
H(6,1) = 83 + 0 = 83  <  88
Чтобы исключить подциклы, запретим следующие переходы: (3,5), (1,2),
Поскольку нижняя граница этого подмножества (6,1) меньше, чем подмножества (6*,1*), то ребро (6,1) включаем в маршрут.
Определяем ребро ветвления  и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) И (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

 i  j

 2

 4

 5

 di

 1

 M

 1

 0(1)

 1

 3

 0(0)

 0(1)

 M

 0

 4

 0(0)

 M

 0(0)

 0

 dj

 0

 1

 0

 0

d(1,3) = 1 + 0 = 1; d(2,1) = 0 + 0 = 0; d(2,2) = 0 + 1 = 1; d(3,1) = 0 + 0 = 0; d(3,3) = 0 + 0 = 0;
Наибольшая сумма констант приведения равна (1 + 0) = 1 для ребра (1,5), следовательно, множество разбивается на два подмножества (1,5) и (1*,5*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(1*,5*) = 83 + 1 = 84
Исключение ребра (1,5) проводим путем замены элемента d15 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (1*,5*), в результате получим редуцированную матрицу.

 i  j

 2

 4

 5

 di

 1

 M

 1

 M

 1

 3

 0

 0

 M

 0

 4

 0

 M

 0

 0

 dj

 0

 0

 0

 1

Включение ребра (1,5) проводится путем исключения всех элементов 1-ой строки и 5-го столбца, в которой элемент d51 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:

После операции приведения сокращенная матрица будет иметь вид:

 i  j

 2

 4

 di

 3

 0

 0

 0

 4

 0

 M

 0

 dj

 0

 0

 0

Нижняя граница подмножества (1,5) равна:
H(1,5) = 83 + 0 = 83  <  84
Поскольку нижняя граница этого подмножества (1,5) меньше, чем подмножества (1*,5*), то ребро (1,5) включаем в маршрут.
В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (3,4) и (4,2).
В результате по дереву ветвлений гамильтонов цикл образуют ребра:
(7,3), (3,4), (4,2), (2,6), (6,1), (1,5), (5,7),
Длина маршрута равна F(Mk) = 83
загрузка...