Задача о коммивояжере
Решить задачу коммивояжера с заданной матрицей расстояний алгоритмом Литтла (или исключения подциклов).| – | 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 |
Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
dj= 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 |
После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины di и dj называются константами приведения.
| 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 с неотрицательными элементами dij>=0
Каждый допустимый маршрут представляет собой цикл, по которому коммивояжер посещает город только один раз и возвращается в исходный город.
Длина маршрута определяется выражением:
F( Mk) = ∑dij
Причем каждая строка и столбец входят в маршрут только один раз с элементом dij.
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (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), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑di+ ∑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), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑di+ ∑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), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑di+ ∑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), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑di+ ∑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
