Пример решений задачи коммивояжера методом ветвей и границ

Пример решения задачи коммивояжера

Решение будем вести с использованием калькулятора. Возьмем в качестве произвольного маршрута:
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

Перейти к онлайн решению своей задачи

загрузка...