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

Решить задачу коммивояжера с заданной матрицей расстояний алгоритмом Литтла (или исключения подциклов).


31

15

19

8

55

19


22

31

7

35

25

43


53

57

16

5

50

49


39

9

24

24

33

5


14

34

26

6

3

36

Решение осуществляем с помощью калькулятора Задача коммивояжера.
Возьмем в качестве произвольного маршрута:
X0 = (1,2);(2,3);(3,4);(4,5);(5,6);(6,1)
Тогда F(X0) = 31 + 22 + 53 + 39 + 14 + 34 = 193.
Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент.
di = min(j) dij


i  j

1

2

3

4

5

6

di

1

M

31

15

19

8

55

8

2

19

M

22

31

7

35

7

3

25

43

M

53

57

16

16

4

5

50

49

M

39

9

5

5

24

24

33

5

M

14

5

6

34

26

6

3

36

M

3

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

i  j

1

2

3

4

5

6

1

M

23

7

11

0

47

2

12

M

15

24

0

28

3

9

27

M

37

41

0

4

0

45

44

M

34

4

5

19

19

28

0

M

9

6

31

23

3

0

33

M

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

i  j

1

2

3

4

5

6

1

M

23

7

11

0

47

2

12

M

15

24

0

28

3

9

27

M

37

41

0

4

0

45

44

M

34

4

5

19

19

28

0

M

9

6

31

23

3

0

33

M

dj

0

19

3

0

0

0

После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины lang=EN-US>j называются константами приведения.

i  j

1

2

3

4

5

6

1

M

4

4

11

0

47

2

12

M

12

24

0

28

3

9

8

M

37

41

0

4

0

26

41

M

34

4

5

19

0

25

0

M

9

6

31

4

0

0

33

M

Сумма констант приведения определяет нижнюю границу H:
H = ∑di + ∑dj
H = 8+7+16+5+5+3+0+19+3+0+0+0 = 66
Элементы матрицы dij соответствуют расстоянию от пункта i до пункта j.
Поскольку в матрице n городов, то D является матрицей nxn с неотрицательными элементами d ij >=0
Каждый допустимый маршрут представляет собой цикл, по которому коммивояжер посещает город только один раз и возвращается в исходный город.
Длина маршрута определяется выражением:
F( Mk) = ∑dij
Причем каждая строка и столбец входят в маршрут только один раз с элементом d ij .
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

i  j

1

2

3

4

5

6

di

1

M

4

4

11

0(4)

47

4

2

12

M

12

24

0(12)

28

12

3

9

8

M

37

41

0(12)

8

4

0(13)

26

41

M

34

4

4

5

19

0(4)

25

0(0)

M

9

0

6

31

4

0(4)

0(0)

33

M

0

dj

9

4

4

0

0

4

0

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

i  j

1

2

3

4

5

6

di

1

M

4

4

11

0

47

0

2

12

M

12

24

0

28

0

3

9

8

M

37

41

0

0

4

M

26

41

M

34

4

4

5

19

0

25

0

M

9

0

6

31

4

0

0

33

M

0

dj

9

0

0

0

0

0

13

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

i  j

2

3

4

5

6

di

1

4

4

M

0

47

0

2

M

12

24

0

28

0

3

8

M

37

41

0

0

5

0

25

0

M

9

0

6

4

0

0

33

M

0

dj

0

0

0

0

0

0

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

i  j

2

3

4

5

6

di

1

4

4

M

0(4)

47

4

2

M

12

24

0(12)

28

12

3

8

M

37

41

0(17)

8

5

0(4)

25

0(0)

M

9

0

6

4

0(4)

0(0)

33

M

0

dj

4

4

0

0

9

0

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

i  j

2

3

4

5

6

di

1

4

4

M

0

47

0

2

M

12

24

0

28

0

3

8

M

37

41

M

8

5

0

25

0

M

9

0

6

4

0

0

33

M

0

dj

0

0

0

0

9

17

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

i  j

2

3

4

5

di

1

4

4

M

0

0

2

M

12

24

0

0

5

0

25

0

M

0

6

4

M

0

33

0

dj

0

4

0

0

4

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

i  j

2

3

4

5

di

1

4

0(8)

M

0(0)

0

2

M

8

24

0(8)

8

5

0(4)

21

0(0)

M

0

6

4

M

0(4)

33

4

dj

4

8

0

0

0

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

i  j

2

3

4

5

di

1

4

M

M

0

0

2

M

8

24

0

0

5

0

21

0

M

0

6

4

M

0

33

0

dj

0

8

0

0

8

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

i  j

2

4

5

di

2

M

24

0

0

5

0

0

M

0

6

4

0

33

0

dj

0

0

0

0

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

i  j

2

4

5

di

2

M

24

0(53)

24

5

0(0)

0(24)

M

0

6

0(29)

M

29

29

dj

0

24

29

0

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

i  j

2

4

5

di

2

M

24

M

24

5

0

0

M

0

6

0

M

29

0

dj

0

0

29

53

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

i  j

2

4

di

5

M

0

0

6

0

M

0

dj

0

0

0

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