Пример решений задачи коммивояжера методом ветвей и границ
Пример решения задачи коммивояжера
Решение будем вести с использованием калькулятора. Возьмем в качестве произвольного маршрута:X0= (1,2);(2,3);(3,4);(4,5);(5,1)
Тогда F(X0) = 90 + 40 + 60 + 50 + 20 = 260
Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент.
di= min(j) dij
| i j | 1 | 2 | 3 | 4 | 5 | di |
| 1 | M | 90 | 80 | 40 | 100 | 40 |
| 2 | 60 | M | 40 | 50 | 70 | 40 |
| 3 | 50 | 30 | M | 60 | 20 | 20 |
| 4 | 10 | 70 | 20 | M | 50 | 10 |
| 5 | 20 | 40 | 50 | 20 | M | 20 |
Затем вычитаем diиз элементов рассматриваемой строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
| i j | 1 | 2 | 3 | 4 | 5 |
| 1 | M | 50 | 40 | 0 | 60 |
| 2 | 20 | M | 0 | 10 | 30 |
| 3 | 30 | 10 | M | 40 | 0 |
| 4 | 0 | 60 | 10 | M | 40 |
| 5 | 0 | 20 | 30 | 0 | M |
Такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
dj= min(i) dij
| i j | 1 | 2 | 3 | 4 | 5 |
| 1 | M | 50 | 40 | 0 | 60 |
| 2 | 20 | M | 0 | 10 | 30 |
| 3 | 30 | 10 | M | 40 | 0 |
| 4 | 0 | 60 | 10 | M | 40 |
| 5 | 0 | 20 | 30 | 0 | M |
| dj | 0 | 10 | 0 | 0 | 0 |
После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины diи djназываются константами приведения.
| i j | 1 | 2 | 3 | 4 | 5 |
| 1 | M | 40 | 40 | 0 | 60 |
| 2 | 20 | M | 0 | 10 | 30 |
| 3 | 30 | 0 | M | 40 | 0 |
| 4 | 0 | 50 | 10 | M | 40 |
| 5 | 0 | 10 | 30 | 0 | M |
Сумма констант приведения определяет нижнюю границу H:
H = ∑di+ ∑dj
H = 40+40+20+10+20+0+10+0+0+0 = 140
Элементы матрицы dijсоответствуют расстоянию от пункта i до пункта j.
Поскольку в матрице n городов, то D является матрицей nxn с неотрицательными элементами dij>=0
Каждый допустимый маршрут представляет собой цикл, по которому коммивояжер посещает город только один раз и возвращается в исходный город.
Длина маршрута определяется выражением:
F(Mk) = ∑dij
Причем каждая строка и столбец входят в маршрут только один раз с элементом dij.
Шаг №1.
Определяем ребро ветвленияи разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
| i j | 1 | 2 | 3 | 4 | 5 | di |
| 1 | M | 40 | 40 | 0(40) | 60 | 40 |
| 2 | 20 | M | 0(20) | 10 | 30 | 10 |
| 3 | 30 | 0(10) | M | 40 | 0(30) | 0 |
| 4 | 0(10) | 50 | 10 | M | 40 | 10 |
| 5 | 0(0) | 10 | 30 | 0(0) | M | 0 |
| dj | 0 | 10 | 10 | 0 | 30 | 0 |
d(1,4) = 40 + 0 = 40; d(2,3) = 10 + 10 = 20; d(3,2) = 0 + 10 = 10; d(3,5) = 0 + 30 = 30; d(4,1) = 10 + 0 = 10; d(5,1) = 0 + 0 = 0; d(5,4) = 0 + 0 = 0;
Наибольшая сумма констант приведения равна (40 + 0) = 40 для ребра (1,4), следовательно, множество разбивается на два подмножества (1,4) и (1*,4*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(1*,4*) = 140 + 40 = 180
Исключение ребра (1,4) проводим путем замены элемента d14= 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (1*,4*), в результате получим редуцированную матрицу.
| i j | 1 | 2 | 3 | 4 | 5 | di |
| 1 | M | 40 | 40 | M | 60 | 40 |
| 2 | 20 | M | 0 | 10 | 30 | 0 |
| 3 | 30 | 0 | M | 40 | 0 | 0 |
| 4 | 0 | 50 | 10 | M | 40 | 0 |
| 5 | 0 | 10 | 30 | 0 | M | 0 |
| dj | 0 | 0 | 0 | 0 | 0 | 40 |
Включение ребра (1,4) проводится путем исключения всех элементов 1-ой строки и 4-го столбца, в которой элемент d41заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (4 x 4), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑di+ ∑dj= 10
После операции приведения сокращенная матрица будет иметь вид:
| i j | 1 | 2 | 3 | 5 | di |
| 2 | 20 | M | 0 | 30 | 0 |
| 3 | 30 | 0 | M | 0 | 0 |
| 4 | M | 50 | 10 | 40 | 10 |
| 5 | 0 | 10 | 30 | M | 0 |
| dj | 0 | 0 | 0 | 0 | 10 |
Нижняя граница подмножества (1,4) равна:
H(1,4) = 140 + 10 = 150 ≤ 180
Поскольку нижняя граница этого подмножества (1,4) меньше, чем подмножества (1*,4*), то ребро (1,4) включаем в маршрут с новой границей H = 150
Шаг №2.
Определяем ребро ветвленияи разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
| i j | 1 | 2 | 3 | 5 | di |
| 2 | 20 | M | 0(20) | 30 | 20 |
| 3 | 30 | 0(10) | M | 0(30) | 0 |
| 4 | M | 40 | 0(30) | 30 | 30 |
| 5 | 0(30) | 10 | 30 | M | 10 |
| dj | 20 | 10 | 0 | 30 | 0 |
d(2,3) = 20 + 0 = 20; d(3,2) = 0 + 10 = 10; d(3,5) = 0 + 30 = 30; d(4,3) = 30 + 0 = 30; d(5,1) = 10 + 20 = 30;
Наибольшая сумма констант приведения равна (0 + 30) = 30 для ребра (3,5), следовательно, множество разбивается на два подмножества (3,5) и (3*,5*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(3*,5*) = 150 + 30 = 180
Исключение ребра (3,5) проводим путем замены элемента d35= 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (3*,5*), в результате получим редуцированную матрицу.
| i j | 1 | 2 | 3 | 5 | di |
| 2 | 20 | M | 0 | 30 | 0 |
| 3 | 30 | 0 | M | M | 0 |
| 4 | M | 40 | 0 | 30 | 0 |
| 5 | 0 | 10 | 30 | M | 0 |
| dj | 0 | 0 | 0 | 30 | 30 |
Включение ребра (3,5) проводится путем исключения всех элементов 3-ой строки и 5-го столбца, в которой элемент d53заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (3 x 3), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑di+ ∑dj= 10
После операции приведения сокращенная матрица будет иметь вид:
| i j | 1 | 2 | 3 | di |
| 2 | 20 | M | 0 | 0 |
| 4 | M | 40 | 0 | 0 |
| 5 | 0 | 10 | M | 0 |
| dj | 0 | 10 | 0 | 10 |
Нижняя граница подмножества (3,5) равна:
H(3,5) = 150 + 10 = 160 ≤ 180
Поскольку нижняя граница этого подмножества (3,5) меньше, чем подмножества (3*,5*), то ребро (3,5) включаем в маршрут с новой границей H = 160
Шаг №3.
Определяем ребро ветвленияи разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
| i j | 1 | 2 | 3 | di |
| 2 | 20 | M | 0(20) | 20 |
| 4 | M | 30 | 0(30) | 30 |
| 5 | 0(20) | 0(30) | M | 0 |
| dj | 20 | 30 | 0 | 0 |
d(2,3) = 20 + 0 = 20; d(4,3) = 30 + 0 = 30; d(5,1) = 0 + 20 = 20; d(5,2) = 0 + 30 = 30;
Наибольшая сумма констант приведения равна (0 + 30) = 30 для ребра (5,2), следовательно, множество разбивается на два подмножества (5,2) и (5*,2*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(5*,2*) = 160 + 30 = 190
Исключение ребра (5,2) проводим путем замены элемента d52= 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (5*,2*), в результате получим редуцированную матрицу.
| i j | 1 | 2 | 3 | di |
| 2 | 20 | M | 0 | 0 |
| 4 | M | 30 | 0 | 0 |
| 5 | 0 | M | M | 0 |
| dj | 0 | 30 | 0 | 30 |
Включение ребра (5,2) проводится путем исключения всех элементов 5-ой строки и 2-го столбца, в которой элемент d25заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑di+ ∑dj= 20
После операции приведения сокращенная матрица будет иметь вид:
| i j | 1 | 3 | di |
| 2 | 20 | 0 | 0 |
| 4 | M | 0 | 0 |
| dj | 20 | 0 | 20 |
Нижняя граница подмножества (5,2) равна:
H(5,2) = 160 + 20 = 180 ≤ 190
Поскольку нижняя граница этого подмножества (5,2) меньше, чем подмножества (5*,2*), то ребро (5,2) включаем в маршрут с новой границей H = 180
В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (2,1) и (4,3).
В результате по дереву ветвлений гамильтонов цикл образуют ребра:
(1,4), (4,3), (3,5), (5,2), (2,1),
Длина маршрута равна F(Mk) = 180
Перейти к онлайн решению своей задачи
Пример №2. Требуется найти кратчайший из замкнутых маршрутов, проходящих точно по одному разу через каждый из шести городов A1, A2,…, A6. Задана матрица расстояний между любыми парами городов, причём расстояние от города Ai до города Aj может не совпадать с расстоянием от Ai до Aj. Элемент матрицы aij считается равным расстоянию от Ai до Aj.
| A1 | A2 | A3 | A4 | A5 | A6 | |
| A1 | - | c+2 | 2c | c+3 | 2c | c+1 |
| A2 | c | - | c+5 | c-1 | c-1 | 3c |
| A3 | c | c+1 | - | c+7 | c+2 | c+3 |
| A4 | c-1 | c+2 | c | - | c+1 | c-1 |
| A5 | c+5 | c+2 | c | c | - | 2c |
| A6 | c | c+1 | c+2 | c+5 | c+7 | - |
Решение. Возьмем в качестве произвольного маршрута: X0= (1,2);(2,3);(3,4);(4,5);(5,6);(6,1)
Тогда F(X0) = 4 + 7 + 9 + 3 + 4 + 2 = 29
Для определения нижней границы множества воспользуемся операцией редукцииили приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент.
di= min(j) dij
| i j | 1 | 2 | 3 | 4 | 5 | 6 | di |
| 1 | M | 4 | 4 | 5 | 4 | 3 | 3 |
| 2 | 2 | M | 7 | 1 | 1 | 6 | 1 |
| 3 | 2 | 3 | M | 9 | 4 | 5 | 2 |
| 4 | 1 | 3 | 2 | M | 3 | 1 | 1 |
| 5 | 7 | 4 | 1 | 1 | M | 4 | 1 |
| 6 | 2 | 3 | 4 | 7 | 9 | M | 2 |
Посмотреть все итерации
В результате по дереву ветвлений гамильтонов цикл образуют ребра:
(2,5), (5,4), (4,6), (6,3), (3,1), (1,2)
Длина маршрута равна F(Mk) = 13
Решение
Пример №3. Рассмотрим пример решения задачи с помощью сервиса задачи коммивояжера
.
Возьмем в качестве произвольного маршрута: 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 |
| 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 |
| 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 |
| 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 |
В результате по дереву ветвлений гамильтонов цикл образуют ребра:
(1,6), (6,2), (2,4), (4,3), (3,5), (5,1),
Длина маршрута равна F(Mk) = 38
Перейти к онлайн решению своей задачи
Пример №4. Имеется необходимость посетить n городов в ходе деловой поездки. Спланировать поездку нужно так, чтобы, переезжая из города в город, побывать в каждом не более одного раза и вернуться в исходный город. Определить оптимальный маршрут посещения городов и его минимальное расстояние.
Задана матрица расстояний между городами cij.
Решение проводим с помощью калькулятора Решение задачи коммивояжера
. Возьмем в качестве произвольного маршрута: X0 = (1,2);(2,3);(3,4);(4,5);(5,6);(6,7);(7,1)
Тогда F(X0) = 20 + 20 + 16 + 9 + 21 + 18 + 12 = 116
Посмотреть все итерации
После операции приведения сокращенная матрица будет иметь вид:
|
i j |
2 |
4 |
di |
|
3 |
0 |
0 |
0 |
|
4 |
0 |
M |
0 |
|
dj |
0 |
0 |
0 |
Поскольку нижняя граница этого подмножества (1,5) меньше, чем подмножества (1*,5*), то ребро (1,5) включаем в маршрут.
В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (3,4) и (4,2).
В результате по дереву ветвлений гамильтонов цикл образуют ребра: (7,3), (3,4), (4,2), (2,6), (6,1), (1,5), (5,7),
Длина маршрута равна F(Mk) = 83
