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

Как решить задачу коммивояжёра

Задание. Требуется найти кратчайший из замкнутых маршрутов, проходящих точно по одному разу через каждый из шести городов 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 -
где с = m + n

Решение.
Возьмем в качестве произвольного маршрута:
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 j123456di
1M445433
22M71161
323M9452
4132M311
57411M41
623479M2

Затем вычитаем di из элементов рассматриваемой строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
Такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
dj = min(i) dij

i j123456
1M11210
21M6005
301M723
4021M20
56300M3
601257M
dj010000

После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины di и dj называются константами приведения.

i j123456
1M01210
21M6005
300M723
4011M20
56200M3
600257M

Шаг №1.
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).

i j123456di
1M0(0)1210(0)0
21M60(0)0(1)50
30(0)0(0)M7230
40(0)11M20(0)0
5620(1)0(0)M30
60(0)0(0)257M0
dj0010100

Наибольшая сумма констант приведения равна (0 + 1) = 1 для ребра (2,5), следовательно, множество разбивается на два подмножества (2,5) и (2*,5*).
Нижняя граница гамильтоновых циклов этого подмножества:

i j123456di
1M012100
21M60M50
300M7230
4011M200
56200M30
600257M0
dj0000101

В результате получим другую сокращенную матрицу (5 x 5), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:

i j12346di
1M01200
300M730
4011M00
56M0030
60025M0
dj000000

Поскольку нижняя граница этого подмножества (2,5) меньше, чем подмножества (2*,5*), то ребро (2,5) включаем в маршрут.
Шаг №2.
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).

i j12346di
1M0(0)120(0)0
30(0)0(0)M730
40(0)11M0(0)0
56M0(1)0(2)30
60(0)0(0)25M0
dj001200

Наибольшая сумма констант приведения равна (0 + 2) = 2 для ребра (5,4), следовательно, множество разбивается на два подмножества (5,4) и (5*,4*).
Нижняя граница гамильтоновых циклов этого подмножества:

i j12346di
1M01200
300M730
4011M00
56M0M30
60025M0
dj000202

В результате получим другую сокращенную матрицу (4 x 4), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:

i j1236di
1M0100
300M30
401100
6002M0
dj00101

Чтобы исключить подциклы, запретим следующие переходы: (4,2),
Поскольку нижняя граница этого подмножества (5,4) меньше, чем подмножества (5*,4*), то ребро (5,4) включаем в маршрут.
Шаг №3.
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).

i j1236di
1M0(0)0(0)0(0)0
30(0)0(0)M30
40(0)M0(0)0(0)0
60(0)0(0)1M0
dj00000

Наибольшая сумма констант приведения равна (0 + 0) = 0 для ребра (1,2), следовательно, множество разбивается на два подмножества (1,2) и (1*,2*).
Нижняя граница гамильтоновых циклов этого подмножества:

i j1236di
1MM000
300M30
40M000
6001M0
dj00000

В результате получим другую сокращенную матрицу (3 x 3), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:

i j136di
30M30
40000
601M0
dj0000

Чтобы исключить подциклы, запретим следующие переходы: (4,2), (4,1),
Поскольку нижняя граница этого подмножества (1,2) меньше, чем подмножества (1*,2*), то ребро (1,2) включаем в маршрут.
Шаг №4.
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).

i j136di
30(3)M33
4M0(1)0(3)0
60(1)1M1
dj0130

Наибольшая сумма констант приведения равна (3 + 0) = 3 для ребра (3,1), следовательно, множество разбивается на два подмножества (3,1) и (3*,1*).
Нижняя граница гамильтоновых циклов этого подмножества:

i j136di
3MM33
4M000
601M0
dj0003

В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:

i j36di
4000
61M1
dj001

Поскольку нижняя граница этого подмножества (3,1) меньше, чем подмножества (3*,1*), то ребро (3,1) включаем в маршрут.
В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (4,6) и (6,3).
В результате по дереву ветвлений гамильтонов цикл образуют ребра:
(2,5), (5,4), (4,6), (6,3), (3,1), (1,2)
Длина маршрута равна F(Mk) = 13
Решение:xml
загрузка...