Имеется необходимость посетить 6 городов в ходе деловой поездки. Спланировать поездку нужно так, чтобы, переезжая из города в город, побывать в каждом не более одного раза и вернуться в исходный город. Определить оптимальный маршрут посещения городов и его минимальное расстояние.
Требуется найти кратчайший из замкнутых маршрутов, проходящих точно по одному разу через каждый из шести городов A1, A2,…, A6. Задана матрица расстояний между любыми парами городов, причём расстояние от города Ai до города Aj может не совпадать с расстоянием от Aj до Ai. Элемент матрицы aij считается равным расстоянию от Ai до Aj.
Данные:
Матрица расстояний между городами
∞ 9 7 1 1 1
9 ∞ 1 7 2 2
6 2 ∞ 6 7 1
8 10 1 ∞ 4 9
5 1 7 10 ∞ 3
6 1 10 10 5 ∞
Решение
Возьмем в качестве произвольного маршрута:X0 = (1,2);(2,3);(3,4);(4,5);(5,6);(6,1)
Тогда F(X0) = 9 + 1 + 6 + 4 + 3 + 6 = 29
Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент.
di = min(j) dij
i j 1 2 3 4 5 6 di
1 M 9 7 1 1 1 1
2 9 M 1 7 2 2 1
3 6 2 M 6 7 1 1
4 8 10 1 M 4 9 1
5 5 1 7 10 M 3 1
6 6 10 10 10 5 M 5
Затем вычитаем di из элементов рассматриваемой строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
i j 1 2 3 4 5 6
1 M 8 6 0 0 0
2 8 M 0 6 1 1
3 5 1 M 5 6 0
4 7 9 0 M 3 8
5 4 0 6 9 M 2
6 1 5 5 5 0 M
Такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
dj = min(i) dij
i j 1 2 3 4 5 6
1 M 8 6 0 0 0
2 8 M 0 6 1 1
3 5 1 M 5 6 0
4 7 9 0 M 3 8
5 4 0 6 9 M 2
6 1 5 5 5 0 M
dj
1 0 0 0 0 0
После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины di и dj называются константами приведения.
i j 1 2 3 4 5 6
1 M 8 6 0 0 0
2 7 M 0 6 1 1
3 4 1 M 5 6 0
4 6 9 0 M 3 8
5 3 0 6 9 M 2
6 0 5 5 5 0 M
Сумма констант приведения определяет нижнюю границу H:H = ∑di + ∑djH = 1+1+1+1+1+5+1+0+0+0+0+0 = 11
Элементы матрицы 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 8 6 0(5) 0(0) 0(0) 0
2 7 M 0(1) 6 1 1 1
3 4 1 M 5 6 0(1) 1
4 6 9 0(3) M 3 8 3
5 3 0(3) 6 9 M 2 2
6 0(3) 5 5 5 0(0) M 0
dj
3 1 0 5 0 0 0
d(1,4) = 0 + 5 = 5;
d(1,5) = 0 + 0 = 0;
d(1,6) = 0 + 0 = 0;
d(2,3) = 1 + 0 = 1;
d(3,6) = 1 + 0 = 1;
d(4,3) = 3 + 0 = 3;
d(5,2) = 2 + 1 = 3;
d(6,1) = 0 + 3 = 3;
d(6,5) = 0 + 0 = 0.
Наибольшая сумма констант приведения равна (0 + 5) = 5 для ребра (1,4), следовательно, множество разбивается на два подмножества (1,4) и (1*,4*).
Исключение ребра (1,4) проводим путем замены элемента d14 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (1*,4*), в результате получим редуцированную матрицу.
i j 1 2 3 4 5 6 di
1 M 8 6 M 0 0 0
2 7 M 0 6 1 1 0
3 4 1 M 5 6 0 0
4 6 9 0 M 3 8 0
5 3 0 6 9 M 2 0
6 0 5 5 5 0 M 0
dj
0 0 0 5 0 0 5
Нижняя граница гамильтоновых циклов этого подмножества:H(1*,4*) = 11 + 5 = 16
Включение ребра (1,4) проводится путем исключения всех элементов 1-ой строки и 4-го столбца, в которой элемент d41 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (5 x 5), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
i j 1 2 3 5 6 di
2 7 M 0 1 1 0
3 4 1 M 6 0 0
4 M 9 0 3 8 0
5 3 0 6 M 2 0
6 0 5 5 0 M 0
dj
0 0 0 0 0 0
Сумма констант приведения сокращенной матрицы:∑di + ∑dj = 0
Нижняя граница подмножества (1,4) равна:H(1,4) = 11 + 0 = 11 ≤ 16
Поскольку нижняя граница этого подмножества (1,4) меньше, чем подмножества (1*,4*), то ребро (1,4) включаем в маршрут с новой границей H = 11
Шаг №2.
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
i j 1 2 3 5 6 di
2 7 M 0(1) 1 1 1
3 4 1 M 6 0(2) 1
4 M 9 0(3) 3 8 3
5 3 0(3) 6 M 2 2
6 0(3) 5 5 0(1) M 0
dj
3 1 0 1 1 0
d(2,3) = 1 + 0 = 1;
d(3,6) = 1 + 1 = 2;
d(4,3) = 3 + 0 = 3;
d(5,2) = 2 + 1 = 3;
d(6,1) = 0 + 3 = 3;
d(6,5) = 0 + 1 = 1.
Наибольшая сумма констант приведения равна (0 + 3) = 3 для ребра (6,1), следовательно, множество разбивается на два подмножества (6,1) и (6*,1*).
Исключение ребра (6,1) проводим путем замены элемента d61 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (6*,1*), в результате получим редуцированную матрицу.
i j 1 2 3 5 6 di
2 7 M 0 1 1 0
3 4 1 M 6 0 0
4 M 9 0 3 8 0
5 3 0 6 M 2 0
6 M 5 5 0 M 0
dj
3 0 0 0 0 3
Нижняя граница гамильтоновых циклов этого подмножества:
H(6*,1*) = 11 + 3 = 14
Включение ребра (6,1) проводится путем исключения всех элементов 6-ой строки и 1-го столбца, в которой элемент d16 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (4 x 4), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
i j 2 3 5 6 di
2 M 0 1 1 0
3 1 M 6 0 0
4 9 0 3 8 0
5 0 6 M 2 0
dj
0 0 1 0 1
Сумма констант приведения сокращенной матрицы:∑di + ∑dj = 1
Нижняя граница подмножества (6,1) равна:H(6,1) = 11 + 1 = 12 ≤ 14
Чтобы исключить подциклы, запретим следующие переходы: (4,6),Поскольку нижняя граница этого подмножества (6,1) меньше, чем подмножества (6*,1*), то ребро (6,1) включаем в маршрут с новой границей H = 12
Шаг №3.
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
i j 2 3 5 6 di
2 M 0(0) 0(2) 1 0
3 1 M 5 0(2) 1
4 9 0(2) 2 M 2
5 0(3) 6 M 2 2
dj
1 0 2 1 0
d(2,3) = 0 + 0 = 0;
d(2,5) = 0 + 2 = 2;
d(3,6) = 1 + 1 = 2;
d(4,3) = 2 + 0 = 2;
d(5,2) = 2 + 1 = 3.
Наибольшая сумма констант приведения равна (2 + 1) = 3 для ребра (5,2), следовательно, множество разбивается на два подмножества (5,2) и (5*,2*).
Исключение ребра (5,2) проводим путем замены элемента d52 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (5*,2*), в результате получим редуцированную матрицу.
i j 2 3 5 6 di
2 M 0 0 1 0
3 1 M 5 0 0
4 9 0 2 M 0
5 M 6 M 2 2
dj
1 0 0 0 3
Нижняя граница гамильтоновых циклов этого подмножества:H(5*,2*) = 12 + 3 = 15
Включение ребра (5,2) проводится путем исключения всех элементов 5-ой строки и 2-го столбца, в которой элемент d25 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (3 x 3), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
i j 3 5 6 di
2 0 M 1 0
3 M 5 0 0
4 0 2 M 0
dj
0 2 0 2
Сумма констант приведения сокращенной матрицы:∑di + ∑dj = 2
Нижняя граница подмножества (5,2) равна:H(5,2) = 12 + 2 = 14 ≤ 15
Чтобы исключить подциклы, запретим следующие переходы: (4,6),
Поскольку нижняя граница этого подмножества (5,2) меньше, чем подмножества (5*,2*), то ребро (5,2) включаем в маршрут с новой границей H = 14
Шаг №4.
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
i j 3 5 6 di
2 0(1) M 1 1
3 M 3 0(4) 3
4 0(0) 0(3) M 0
dj
0 3 1 0
d(2,3) = 1 + 0 = 1;
d(3,6) = 3 + 1 = 4;
d(4,3) = 0 + 0 = 0;
d(4,5) = 0 + 3 = 3.
Наибольшая сумма констант приведения равна (3 + 1) = 4 для ребра (3,6), следовательно, множество разбивается на два подмножества (3,6) и (3*,6*).
Исключение ребра (3,6) проводим путем замены элемента d36 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (3*,6*), в результате получим редуцированную матрицу.
i j 3 5 6 di
2 0 M 1 0
3 M 3 M 3
4 0 0 M 0
dj
0 0 1 4
Нижняя граница гамильтоновых циклов этого подмножества:H(3*,6*) = 14 + 4 = 18
Включение ребра (3,6) проводится путем исключения всех элементов 3-ой строки и 6-го столбца, в которой элемент d63 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
i j 3 5 di
2 0 M 0
4 0 0 0
dj
0 0 0
Сумма констант приведения сокращенной матрицы:∑di + ∑dj = 0
Нижняя граница подмножества (3,6) равна:H(3,6) = 14 + 0 = 14 ≤ 18
Поскольку нижняя граница этого подмножества (3,6) меньше, чем подмножества (3*,6*), то ребро (3,6) включаем в маршрут с новой границей H = 14
В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (2,3) и (4,5).
В результате по дереву ветвлений гамильтонов цикл образуют ребра:(1,4), (4,5), (5,2), (2,3), (3,6), (6,1),
Оптимальный путь: 1→4→5→2→3→6→1.
Длина маршрута равна F(Mk) = 14.
Задать вопрос
на новый заказ в Автор24.
