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

Имеется необходимость посетить 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
Задать вопрос или оставить комментарий Помощь в решении Поиск Поддержать проект