Задача коммивояжера

Задача коммивояжера: имеется n городов, задана матрица расстояний между городами. Коммивояжер должен побывать в каждом городе только один раз и вернуться в начальный город. Требуется найти маршрут, имеющий минимальную длину

Евклидова метрика - симметричная - выполняется неравенство треугольника Формирование матрицы

Манхэттенская метрика - симметричная Аффинная метрика - симметричная Формирование матрицы

Чебышевская метрика - симметричная Несимметричная псевдометрическая матрица

Методы решения 1. Точные методы метод полного перебора метод ветвей и границ 2. Приближенные и эвристические методы жадные методы алгоритм Карга-Томпсона методы локальных улучшений алгоритм Метрополиса (имитации отжига)

Алгоритм имитации отжига Основывается на имитации физического процесса, который происходит при кристаллизации вещества из жидкого состояния в твёрдое, в том числе при отжиге металлов Предполагается, что атомы выстроились в кристаллическую решётку, но переходы отдельных атомов из одной ячейки в другую ещё допустимы

Алгоритм имитации отжига Процесс протекает при постепенно понижающейся температуре, переход атома из одной ячейки в другую происходит с некоторой вероятностью, которая уменьшается с понижением температуры Устойчивая кристаллическая решётка соответствует минимуму энергии атомов, поэтому атом либо переходит в состояние с меньшим уровнем энергии, либо остаётся на месте

Методы решения 1. Точные методы метод полного перебора метод ветвей и границ 2. Приближенные и эвристические методы жадные методы алгоритм Карга-Томпсона методы локальных улучшений алгоритм Метрополиса (имитации отжига) 3. Интеллектуальные методы (приближенные) использование нейронных сетей использование генетических алгоритмов метод муравьиных колоний

Метод муравьиных колоний В основе муравьиного алгоритма лежит поведение муравьиной колонии – маркировка более удачных путей большим количеством феромона Муравей проходит случайным образом от колонии Если он находит источник пищи, то возвращается в гнездо, оставляя за собой след из феромона Эти феромоны привлекают других муравьёв находящихся вблизи, которые вероятнее всего пойдут по этому маршруту

Метод муравьиных колоний Вернувшись в гнездо они укрепят феромонную тропу Если существует 2 маршрута, то по более короткому, за то же время, успеют пройти больше муравьёв, чем по длинному Короткий маршрут станет более привлекательным Длинные пути, в конечном итоге, исчезнут из-за испарения феромонов

Жадные методы Алгоритм ближайшего соседа На первом шаге выбираем город (вершину), из которого выходит дорога (ребро) наименьшей длины На каждом шаге выбираем ближайший непосещенный город

4 – 2: 3 2 – 1: 6 1 – 7: 13 7 – 3: 17 3 – 6: 6 6 – 5: 18 5 – 4: 38 L = 101

(Эвристика ближайшей точки) На первом шаге выбираем две ближайшие в обе стороны вершины Для каждого ребра построенного пути выбираем вершину (из свободных), добавление которой приводит к наименьшему ухудшению: Алгоритм Карга-Томпсона

Методы локальных улучшений На первом шаге выбираем любое решение Для улучшения текущего решения применяем к нему какое-либо преобразование из заданной совокупности преобразований. Это улучшенное решение становится текущим решением Повторяем до тех пор, пока ни одно из преобразований в заданной совокупности не позволит улучшить текущее решение Если заданная совокупность преобразований включает все возможные преобразования, то получим точное решение, но трудоемкость такого алгоритма будет не лучше, чем у перебора всех решений

Алгоритм локальных улучшений Преобразование 1: два последовательно идущих города меняются местами (вычисление длины каждого маршрута требует не n, а 6 сложений) Преобразование 2: маршрут меняется на обратный (для несимметричных задач)

Алгоритм локальных улучшений На первом шаге задаем любой маршрут На каждом шаге рассматриваем все маршруты, которые могут быть получены из текущего маршрута следующим образом: - два последовательно идущих города меняются местами - маршрут меняется на обратный Из полученных маршрутов выбирается наименьший, если он лучше предыдущего

1 – 2 – 3 – 4 – 5 – 6 – 7 – 1 = 157

1 – 3 – 2 – 4 – 5 – 6 – 7 – 1 = – 2 – 4 – 3 – 5 – 6 – 7 – 1 = – 2 – 3 – 5 – 4 – 6 – 7 – 1 = – 2 – 3 – 4 – 6 – 5 – 7 – 1 = – 2 – 3 – 4 – 5 – 7 – 6 – 1 = – 2 – 3 – 4 – 5 – 6 – 1 – 7 = – 6 – 5 – 4 – 3 – 2 – 1 – 7 = 135

1 – 2 – 4 – 3 – 5 – 6 – 7 – 1 = – 4 – 2 – 3 – 5 – 6 – 7 – 1 = – 2 – 3 – 4 – 5 – 6 – 7 – 1 = – 2 – 4 – 5 – 3 – 6 – 7 – 1 = – 2 – 4 – 3 – 6 – 5 – 7 – 1 = – 2 – 4 – 3 – 5 – 7 – 6 – 1 = – 2 – 4 – 3 – 5 – 6 – 1 – 7 = – 6 – 5 – 3 – 4 – 2 – 1 – 7 = 101

7 – 5 – 6 – 3 – 4 – 2 – 1 – 7 = – 6 – 3 – 5 – 4 – 2 – 1 – 7 = – 6 – 5 – 4 – 3 – 2 – 1 – 7 = – 6 – 5 – 3 – 2 – 4 – 1 – 7 = – 6 – 5 – 3 – 4 – 1 – 2 – 7 = – 6 – 5 – 3 – 4 – 2 – 7 – 1 = – 2 – 4 – 3 – 5 – 6 – 7 – 1 = 119

7 – 6 – 5 – 3 – 4 – 1 – 2 – 7 = – 5 – 6 – 3 – 4 – 1 – 2 – 7 = – 6 – 3 – 5 – 4 – 1 – 2 – 7 = – 6 – 5 – 4 – 3 – 1 – 2 – 7 = – 6 – 5 – 3 – 1 – 4 – 2 – 7 = – 6 – 5 – 3 – 4 – 2 – 1 – 7 = – 6 – 5 – 3 – 4 – 1 – 7 – 2 = – 1 – 4 – 3 – 5 – 6 – 7 – 2 = 120

Алгоритм ближайшего соседа + Алгоритм локальных улучшений 4 – 2 – 1 – 7 – 3 – 6 – 5 – 4 = – 1 – 2 – 7 – 3 – 6 – 5 – 4 = 100

АБС из города 1: 1–2–4–7–3–6–5–1 = 98 АБС из города 1 + АЛУ: 1–2–4–7–3–6–5–1 = 98 АБС из 2: = 111, +АЛУ: = 101 АБС из 3: = 101, +АЛУ: = 100 АБС из 4: = 101, +АЛУ: = 100 АБС из 5: = 107, +АЛУ: = 106 АБС из 6: = 119, +АЛУ: = 98 АБС из 7: = 113, +АЛУ: = 102

Жадный алгоритм ближайшего соседа: 4 – 2 – 1 – 7 – 3 – 6 – 5 – 4 = 101 Минимальный путь: 5 – 3 – 1 – 2 – 4 – 7 – 6 – 5 = 96 Алгоритм Карга-Томпсона: 4–7–6–5–3–1–2–4 = 96 Алгоритм локальных улучшений: 7 – 6 – 5 – 3 – 4 – 1 – 2 – 7 = 100 Жадный алгоритм + алгоритм локальных улучшений: 4 – 1 – 2 – 7 – 3 – 6 – 5 – 4 = 100 Наилучший из жадных алгоритмов ближайшего соседа из разных городов: 1 – 2 – 4 – 7 – 3 – 6 – 5 – 1 = 98

Пример Жадный алгоритм БС: 5 – 3 – 1 – 4 – 2 – 5 = 116 Алгоритм Карга-Томпсона: 5 – 1 – 3 – 4 – 2 – 5 = 122 Алгоритм К-Т + АЛУ: 5 – 2 – 4 – 1 – 3 – 5 = 115 Жадный алгоритм + АЛУ: 2 – 4 – 1 – 3 – 5 – 2 = 115

Метод полного перебора маршрута

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

Ветвление: Оценка второго подмножества ( ):

Метод ветвей и границ. Шаг 1 Оценка первого подмножества ( ): - вычеркнем k=1 строку и l=3 столбец - удаляем циклы: заменяем на элементы, используя которые можно получить контуры длиной меньше n

Метод ветвей и границ. Шаг 1 Оценка первого подмножества ( ): - приведем матрицу

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

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

Метод ветвей и границ. Шаг 3 Ветвление множества : - запрещаем переход 1-3: заменяем на элемент (1,3)

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

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

Метод ветвей и границ. Шаг 5 4 – 1 5 – 2 1 – 3 3 – 5 2 – 4 1 – 3 – 5 – 2 – 4 – 1 L = 115

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

Пример

Маршрут из города 1 Маршрут из города 1: 1 – 3 – 5 – 2 – 4 = 77

Маршрут из города 2 Маршрут из города 2: 2 – 4 – 3 – 5 – 1 = 86

Маршрут из города 3 Маршрут из города 3: 3 – 5 – 2 – 4 – 1 = 93

Маршрут из города 4 Маршрут из города 4: 4 – 2 – 5 – 3 – 1 = 70

Маршрут из города 5 Маршрут из города 5: 5 – 2 – 4 – 3 – 1 = 90

Маршрут из города 4: 4 – 2 – 5 – 3 – 1 = 70 Маршрут из города 3: 3 – 5 – 2 – 4 – 1 = 93 Маршрут из города 2: 2 – 4 – 3 – 5 – 1 = 86 Маршрут из города 1: 1 – 3 – 5 – 2 – 4 = 77 Замкнутый маршрут: 1 – 3 – 5 – 2 – 4 – 1 = 115