Задача кольцевого маршрута
Дана схема маршрутов между пунктами. Построить кольцевой маршрут объезда всех пунктов, чтобы длина маршрута была наименьшей и чтобы каждый из пунктов входил только один раз.Решение.
Возьмем в качестве произвольного маршрута:
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