Задача кольцевого маршрута

Дана схема маршрутов между пунктами. Построить кольцевой маршрут объезда всех пунктов, чтобы длина маршрута была наименьшей и чтобы каждый из пунктов входил только один раз.

Решение.

Возьмем в качестве произвольного маршрута:

X0 = (1,2);(2,3);(3,4);(4,5);(5,6);(6,1)

Тогда F(X0) = 10 + 11 + 3 + 12 + 14 + 17 = 67

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

di = min(j) dij

i  j

1

2

3

4

5

6

di

1

M

10

5

9

16

8

5

2

6

M

11

8

18

19

6

3

7

13

M

3

4

14

3

4

5

9

6

M

12

17

5

5

5

4

11

6

M

14

4

6

17

7

12

13

16

M

7

 

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

i  j

1

2

3

4

5

6

1

M

5

0

4

11

3

2

0

M

5

2

12

13

3

4

10

M

0

1

11

4

0

4

1

M

7

12

5

1

0

7

2

M

10

6

10

0

5

6

9

M

 

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

dj = min(i) dij

i  j

1

2

3

4

5

6

1

M

5

0

4

11

3

2

0

M

5

2

12

13

3

4

10

M

0

1

11

4

0

4

1

M

7

12

5

1

0

7

2

M

10

6

10

0

5

6

9

M

dj

0

0

0

0

1

3

 

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

i  j

1

2

3

4

5

6

1

M

5

0

4

10

0

2

0

M

5

2

11

10

3

4

10

M

0

0

8

4

0

4

1

M

6

9

5

1

0

7

2

M

7

6

10

0

5

6

8

M

 

Сумма констант приведения определяет нижнюю границу H:

H = ∑di + ∑dj

H = 5+6+3+5+4+7+0+0+0+0+1+3 = 34

Элементы матрицы 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

5

0(1)

4

10

0(7)

0

2

0(2)

M

5

2

11

10

2

3

4

10

M

0(2)

0(6)

8

0

4

0(1)

4

1

M

6

9

1

5

1

0(1)

7

2

M

7

1

6

10

0(5)

5

6

8

M

5

dj

0

0

1

2

6

7

0

 

d(1,3) = 0 + 1 = 1; d(1,6) = 0 + 7 = 7; d(2,1) = 2 + 0 = 2; d(3,4) = 0 + 2 = 2; d(3,5) = 0 + 6 = 6; d(4,1) = 1 + 0 = 1; d(5,2) = 1 + 0 = 1; d(6,2) = 5 + 0 = 5;

Наибольшая сумма констант приведения равна (0 + 7) = 7 для ребра (1,6), следовательно, множество разбивается на два подмножества (1,6) и (1*,6*).

Нижняя граница гамильтоновых циклов этого подмножества:

H(1*,6*) = 34 + 7 = 41

Исключение ребра (1,6) проводим путем замены элемента d16 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (1*,6*), в результате получим редуцированную матрицу.

i  j

1

2

3

4

5

6

di

1

M

5

0

4

10

M

0

2

0

M

5

2

11

10

0

3

4

10

M

0

0

8

0

4

0

4

1

M

6

9

0

5

1

0

7

2

M

7

0

6

10

0

5

6

8

M

0

dj

0

0

0

0

0

7

7

 

Включение ребра (1,6) проводится путем исключения всех элементов 1-ой строки и 6-го столбца, в которой элемент d61 заменяем на М, для исключения образования негамильтонова цикла.

В результате получим другую сокращенную матрицу (5 x 5), которая подлежит операции приведения.

Сумма констант приведения сокращенной матрицы:

∑di + ∑dj = 1

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

i  j

1

2

3

4

5

di

2

0

M

5

2

11

0

3

4

10

M

0

0

0

4

0

4

1

M

6

0

5

1

0

7

2

M

0

6

M

0

5

6

8

0

dj

0

0

1

0

0

1

 

Нижняя граница подмножества (1,6) равна:

H(1,6) = 34 + 1 = 35  <  41

Поскольку нижняя граница этого подмножества (1,6) меньше, чем подмножества (1*,6*), то ребро (1,6) включаем в маршрут.

Шаг №2.

Определяем ребро ветвления  и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).

С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

i  j

1

2

3

4

5

di

2

0(2)

M

4

2

11

2

3

4

10

M

0(2)

0(6)

0

4

0(0)

4

0(4)

M

6

0

5

1

0(1)

6

2

M

1

6

M

0(4)

4

6

8

4

dj

0

0

4

2

6

0

 

d(2,1) = 2 + 0 = 2; d(3,4) = 0 + 2 = 2; d(3,5) = 0 + 6 = 6; d(4,1) = 0 + 0 = 0; d(4,3) = 0 + 4 = 4; d(5,2) = 1 + 0 = 1; d(6,2) = 4 + 0 = 4;

Наибольшая сумма констант приведения равна (0 + 6) = 6 для ребра (3,5), следовательно, множество разбивается на два подмножества (3,5) и (3*,5*).

Нижняя граница гамильтоновых циклов этого подмножества:

H(3*,5*) = 35 + 6 = 41

Исключение ребра (3,5) проводим путем замены элемента d35 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (3*,5*), в результате получим редуцированную матрицу.

i  j

1

2

3

4

5

di

2

0

M

4

2

11

0

3

4

10

M

0

M

0

4

0

4

0

M

6

0

5

1

0

6

2

M

0

6

M

0

4

6

8

0

dj

0

0

0

0

6

6

 

Включение ребра (3,5) проводится путем исключения всех элементов 3-ой строки и 5-го столбца, в которой элемент d53 заменяем на М, для исключения образования негамильтонова цикла.

В результате получим другую сокращенную матрицу (4 x 4), которая подлежит операции приведения.

Сумма констант приведения сокращенной матрицы:

∑di + ∑dj = 2

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

i  j

1

2

3

4

di

2

0

M

4

2

0

4

0

4

0

M

0

5

1

0

M

2

0

6

M

0

4

6

0

dj

0

0

0

2

2

 

Нижняя граница подмножества (3,5) равна:

H(3,5) = 35 + 2 = 37  <  41

Поскольку нижняя граница этого подмножества (3,5) меньше, чем подмножества (3*,5*), то ребро (3,5) включаем в маршрут.

Шаг №3.

Определяем ребро ветвления  и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).

С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

i  j

1

2

3

4

di

2

0(0)

M

4

0(0)

0

4

0(0)

4

0(4)

M

0

5

1

0(0)

M

0(0)

0

6

M

0(4)

4

4

4

dj

0

0

4

0

0

 

d(2,1) = 0 + 0 = 0; d(2,4) = 0 + 0 = 0; d(4,1) = 0 + 0 = 0; d(4,3) = 0 + 4 = 4; d(5,2) = 0 + 0 = 0; d(5,4) = 0 + 0 = 0; d(6,2) = 4 + 0 = 4;

Наибольшая сумма констант приведения равна (0 + 4) = 4 для ребра (4,3), следовательно, множество разбивается на два подмножества (4,3) и (4*,3*).

Нижняя граница гамильтоновых циклов этого подмножества:

H(4*,3*) = 37 + 4 = 41

Исключение ребра (4,3) проводим путем замены элемента d43 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (4*,3*), в результате получим редуцированную матрицу.

i  j

1

2

3

4

di

2

0

M

4

0

0

4

0

4

M

M

0

5

1

0

M

0

0

6

M

0

4

4

0

dj

0

0

4

0

4

 

Включение ребра (4,3) проводится путем исключения всех элементов 4-ой строки и 3-го столбца, в которой элемент d34 заменяем на М, для исключения образования негамильтонова цикла.

В результате получим другую сокращенную матрицу (3 x 3), которая подлежит операции приведения.

Сумма констант приведения сокращенной матрицы:

∑di + ∑dj = 0

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

i  j

1

2

4

di

2

0

M

0

0

5

1

0

0

0

6

M

0

4

0

dj

0

0

0

0

 

Нижняя граница подмножества (4,3) равна:

H(4,3) = 37 + 0 = 37  <  41

Чтобы исключить подциклы, запретим следующие переходы: (5,4),

Поскольку нижняя граница этого подмножества (4,3) меньше, чем подмножества (4*,3*), то ребро (4,3) включаем в маршрут.

Шаг №4.

Определяем ребро ветвления  и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).

С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

i  j

1

2

4

di

2

0(1)

M

0(4)

0

5

1

0(1)

M

1

6

M

0(4)

4

4

dj

1

0

4

0

 

d(2,1) = 0 + 1 = 1; d(2,4) = 0 + 4 = 4; d(5,2) = 1 + 0 = 1; d(6,2) = 4 + 0 = 4;

Наибольшая сумма констант приведения равна (0 + 4) = 4 для ребра (2,4), следовательно, множество разбивается на два подмножества (2,4) и (2*,4*).

Нижняя граница гамильтоновых циклов этого подмножества:

H(2*,4*) = 37 + 4 = 41

Исключение ребра (2,4) проводим путем замены элемента d24 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (2*,4*), в результате получим редуцированную матрицу.

i  j

1

2

4

di

2

0

M

M

0

5

1

0

M

0

6

M

0

4

0

dj

0

0

4

4

 

Включение ребра (2,4) проводится путем исключения всех элементов 2-ой строки и 4-го столбца, в которой элемент d42 заменяем на М, для исключения образования негамильтонова цикла.

В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения.

Сумма констант приведения сокращенной матрицы:

∑di + ∑dj = 1

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

i  j

1

2

di

5

1

0

0

6

M

0

0

dj

1

0

1

 

Нижняя граница подмножества (2,4) равна:

H(2,4) = 37 + 1 = 38  <  41

Поскольку нижняя граница этого подмножества (2,4) меньше, чем подмножества (2*,4*), то ребро (2,4) включаем в маршрут.

В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (5,1) и (6,2).

В результате по дереву ветвлений гамильтонов цикл образуют ребра:

(1,6), (6,2), (2,4), (4,3), (3,5), (5,1),

Длина маршрута равна F(Mk) = 38

загрузка...