Примеры решений Теория игр Задача о назначениях Поток сети Транспортная задача Графический метод Решение дифф уравнений Симплексный метод Двойственная задача Параметры сетевой модели

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

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

Решение будем вести с использованием калькулятора. Возьмем в качестве произвольного маршрута:
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 j12345di
1M90804010040
260M40507040
35030M602020
4107020M5010
520405020M20

Затем вычитаем diиз элементов рассматриваемой строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
i j12345
1M5040060
220M01030
33010M400
406010M40
5020300M

Такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
dj= min(i) dij
i j12345
1M5040060
220M01030
33010M400
406010M40
5020300M
dj010000

После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины diи djназываются константами приведения.
i j12345
1M4040060
220M01030
3300M400
405010M40
5010300M

Сумма констант приведения определяет нижнюю границу 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 j12345di
1M40400(40)6040
220M0(20)103010
3300(10)M400(30)0
40(10)5010M4010
50(0)10300(0)M0
dj010100300

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 j12345di
1M4040M6040
220M010300
3300M4000
405010M400
5010300M0
dj0000040

Включение ребра (1,4) проводится путем исключения всех элементов 1-ой строки и 4-го столбца, в которой элемент d41заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (4 x 4), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑di+ ∑dj= 10
После операции приведения сокращенная матрица будет иметь вид:
i j1235di
220M0300
3300M00
4M50104010
501030M0
dj000010

Нижняя граница подмножества (1,4) равна:
H(1,4) = 140 + 10 = 150 ≤ 180
Поскольку нижняя граница этого подмножества (1,4) меньше, чем подмножества (1*,4*), то ребро (1,4) включаем в маршрут с новой границей H = 150
Шаг №2.
Определяем ребро ветвленияи разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
i j1235di
220M0(20)3020
3300(10)M0(30)0
4M400(30)3030
50(30)1030M10
dj20100300

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 j1235di
220M0300
3300MM0
4M400300
501030M0
dj0003030

Включение ребра (3,5) проводится путем исключения всех элементов 3-ой строки и 5-го столбца, в которой элемент d53заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (3 x 3), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑di+ ∑dj= 10
После операции приведения сокращенная матрица будет иметь вид:
i j123di
220M00
4M4000
5010M0
dj010010

Нижняя граница подмножества (3,5) равна:
H(3,5) = 150 + 10 = 160 ≤ 180
Поскольку нижняя граница этого подмножества (3,5) меньше, чем подмножества (3*,5*), то ребро (3,5) включаем в маршрут с новой границей H = 160
Шаг №3.
Определяем ребро ветвленияи разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
i j123di
220M0(20)20
4M300(30)30
50(20)0(30)M0
dj203000

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 j123di
220M00
4M3000
50MM0
dj030030

Включение ребра (5,2) проводится путем исключения всех элементов 5-ой строки и 2-го столбца, в которой элемент d25заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑di+ ∑dj= 20
После операции приведения сокращенная матрица будет иметь вид:
i j13di
22000
4M00
dj20020

Нижняя граница подмножества (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 -
где с = 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

Посмотреть все итерации
В результате по дереву ветвлений гамильтонов цикл образуют ребра:
(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  j123456di
1M10591685
26M11818196
3713M34143
4596M12175
554116M144
6177121316M7
Затем вычитаем diиз элементов рассматриваемой строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
i  j123456
1M504113
20M521213
3410M0111
4041M712
51072M10
6100569M
Такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент: dj= min(i) dij
i  j123456
1M504113
20M521213
3410M0111
4041M712
51072M10
6100569M
dj000013
После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины diи djназываются константами приведения.
i  j123456
1M504100
20M521110
3410M008
4041M69
51072M7
6100568M
Сумма констант приведения определяет нижнюю границу H: H = ∑di+ ∑dj = H = 5+6+3+5+4+7+0+0+0+0+1+3 = 34

Посмотреть все итерации

В результате по дереву ветвлений гамильтонов цикл образуют ребра:

(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) равна: H(1,5) = 83 + 0 = 83  <  84
Поскольку нижняя граница этого подмножества (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
Задача о кратчайшем пути
Алгоритм Беллмана-Форда. Решение по шагам
Алгоритм Дейкстры онлайн
Решение онлайн
Упростить логическое выражение
Решение по шагам
(a→c)→ba
Упростим функцию, используя основные законы логики высказываний.
Замена импликации: A → B = A v B
Решение онлайн
Учебно-методический
√ курсы переподготовки и повышения квалификации
√ вебинары
√ сертификаты на публикацию методического пособия
Подробнее