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

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

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

Решение будем вести с использованием калькулятора. Возьмем в качестве произвольного маршрута:
X₀= (1,2);(2,3);(3,4);(4,5);(5,1)
Тогда F(X₀) = 90 + 40 + 60 + 50 + 20 = 260
Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент.
d_i= min(j) d_ij

Затем вычитаем d_iиз элементов рассматриваемой строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.

Такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
d_j= min(i) d_ij

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

Сумма констант приведения определяет нижнюю границу H:
H = ∑d_i+ ∑d_j
H = 40+40+20+10+20+0+10+0+0+0 = 140
Элементы матрицы d_ijсоответствуют расстоянию от пункта i до пункта j.
Поскольку в матрице n городов, то D является матрицей nxn с неотрицательными элементами d_ij>=0
Каждый допустимый маршрут представляет собой цикл, по которому коммивояжер посещает город только один раз и возвращается в исходный город.
Длина маршрута определяется выражением:
F(M_k) = ∑d_ij
Причем каждая строка и столбец входят в маршрут только один раз с элементом d_ij.
Шаг №1.
Определяем ребро ветвленияи разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

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) проводим путем замены элемента d₁₄= 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (1*,4*), в результате получим редуцированную матрицу.

Включение ребра (1,4) проводится путем исключения всех элементов 1-ой строки и 4-го столбца, в которой элемент d₄₁заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (4 x 4), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑d_i+ ∑d_j= 10
После операции приведения сокращенная матрица будет иметь вид:

Нижняя граница подмножества (1,4) равна:
H(1,4) = 140 + 10 = 150 ≤ 180
Поскольку нижняя граница этого подмножества (1,4) меньше, чем подмножества (1*,4*), то ребро (1,4) включаем в маршрут с новой границей H = 150
Шаг №2.
Определяем ребро ветвленияи разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

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) проводим путем замены элемента d₃₅= 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (3*,5*), в результате получим редуцированную матрицу.

Включение ребра (3,5) проводится путем исключения всех элементов 3-ой строки и 5-го столбца, в которой элемент d₅₃заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (3 x 3), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑d_i+ ∑d_j= 10
После операции приведения сокращенная матрица будет иметь вид:

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

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) проводим путем замены элемента d₅₂= 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (5*,2*), в результате получим редуцированную матрицу.

Включение ребра (5,2) проводится путем исключения всех элементов 5-ой строки и 2-го столбца, в которой элемент d₂₅заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑d_i+ ∑d_j= 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

Решение. Возьмем в качестве произвольного маршрута: X₀= (1,2);(2,3);(3,4);(4,5);(5,6);(6,1)
Тогда F(X₀) = 4 + 7 + 9 + 3 + 4 + 2 = 29
Для определения нижней границы множества воспользуемся операцией редукцииили приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент.
d_i= min(j) d_ij

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

Возьмем в качестве произвольного маршрута: X₀ = (1,2);(2,3);(3,4);(4,5);(5,6);(6,1)

Тогда F(X₀) = 10 + 11 + 3 + 12 + 14 + 17 = 67

Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент.

d_i = min(j) d_ij

Затем вычитаем d_iиз элементов рассматриваемой строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.

Такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент: d_j= min(i) d_ij

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

Сумма констант приведения определяет нижнюю границу H: H = ∑d_i+ ∑d_j = H = 5+6+3+5+4+7+0+0+0+0+1+3 = 34

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

Длина маршрута равна F(Mk) = 38

Источник

Решаем задачу коммивояжёра простым перебором

Простое решение, но много кода.

Вчера мы рассказывали, что такое задача коммивояжёра. Если коротко — это класс задач на поиск кратчайшего маршрута среди нескольких городов. Или маршрута по городу. Или поиск оптимальной квартиры для аренды по нескольким параметрам. В общем — это задачи о том, как принимать решения в ситуациях со множеством переменных.

Сегодня мы попробуем решить классическую задачу коммивояжёра самым простым способом — простым полным перебором.

👉 Мы знаем, что решить задачу коммивояжёра полным перебором не получится, если у нас много городов. Но мы попробуем и посмотрим, какой получится код и как его можно оптимизировать.

Города и расстояния

Допустим, у нас есть 5 городов, каждый из которых соединён с другим:

Из-за рельефа местности близкие города не всегда соединены по прямой, но для простоты мы нарисовали так. Теперь проставим время, которое требуется для переезда из города в город:

Чтобы было удобно пользоваться расстояниями, сделаем табличку:

Нулевые ячейки означают, что здесь нет маршрута, потому что это путь из одного и того же города и обратно. Остальные числа — это расстояния между городами. Например, расстояние между первым и третьим городом — 6 километров, а между четвёртым и вторым — 10 километров.

На языке JavaScript это будет выглядеть так:

Логика работы

Наша задача — найти такой маршрут, в котором сумма километров будет минимальной.

Скрипт полного перебора будет работать так:

Скрипт

Для работы скрипта нам понадобятся такие переменные:

Соберём скрипт. Читайте комментарии:

Разбираем результат

Когда мы запустим скрипт в консоли браузера, то увидим такое:

Скрипт на каждом шаге выводил текущий маршрут, который он проверял, а в конце выдал результат. Если мы пролистаем наверх весь вывод маршрутов, то увидим, как скрипт постепенно находил маршруты всё короче и короче:

Но только ближе к концу он нашёл самый короткий путь, который и вошёл в итоговый результат:

Что здесь не так

С одной стороны, у нас получился простой и понятный алгоритм, который делает то, что нам нужно. С другой — у него есть серьёзные проблемы:

Попробуем исправить эти недостатки в следующих подходах к задаче. Следите за новыми статьями.

Источник

Решение задачи коммивояжера алгоритмом Литтла с визуализацией на плоскости

Известная как минимум с 19 века задача коммивояжера имеет множество способов решения и неоднократно описана. Ее оптимизационная версия является NP-трудной, поэтому оптимальное решение можно получить либо полным перебором, либо оптимизированным полным перебором — методом ветвей и границ.

Пытаясь запрограммировать алгоритм Литтла (частный случай метода ветвей и границ), я понял, что в рунете крайне трудно найти его правильное описание понятным языком и разобранную программную реализацию. Однако имеющиеся в изобилии описания обманчиво правдоподобны на данных малого размера и с трудом проверяются без визуализации.

Метод ветвей и границ

Алгоритм Литтла является частным случаем МВиГ, т.е. в худшем случае его сложность равна сложности полного перебора. Теоретическое описание выглядит следующим образом:

Имеется множетво S всех гамильтоновых циклов рафа. На каждом шаге в S ищется ребро (i, j), исключение которого из маршрута максимально увеличит оценку снизу. Далее происходит разбиение множества на два непересекающихся S1 и S2. S1 — все циклы, содержащие ребро (i, j) и не содержащие (j, i). S2 — все циклы, не содержащие (i, j). Далее вычисляется оценка снизу для длины пути каждого множества и, если она превышает длину уже найденного решения, множество отбрасывается. Если нет — множества S1 и S2 обрабатываются так же, как и S.

Алгоритмическое описание

Имеется матрица расстояний M. Диагональ заполняется бесконечными значениями, т.к. не должно возникать преждевременных циклов. Также имеется переменная, хранящая нижнюю границу.

Стоит оговориться, что нужно вести учет двух видов бесконечностей — одна добавляется после удаления строки и столбца из матрицы, чтобы не возникало преждевременных циклов, другая — при отбрасывании ребер. Случаи будут рассмотрены чуть позже. Первую бесконечность обозначим как inf1, вторую — inf2. Диагональ заполнена inf1.

Эвристика состоит в том, что у матрицы M1 нижняя граница не больше, чем у матрицы M2 и в первую очередь рассматривается ветвь, содержащая ребро (i, j).

Пример

Примеров в интернете огромное количество, но действительно интересный находится в этой статье с хорошо иллюстированными деревьями (единственная найденная мной статья, в которой также указано про распространенную ошибку, но, к сожалению, в ней недостаточно алгоритмическое описание алгоритма — сначала про матрицы, потом про множества). Интересен пример тем, что если рассматривать только ветки с ребрами с максимальным штрафом, будет получен неверный результат.

Так что приведу шаги поиска оптимального пути для этой матрицы.

Реализация

Шаг 1

Получение нулей в каждой строке и каждом столбце.

Источник