Traveling Salesman Problem (TSP)

https://habr.com/ru/articles/708072/

Задача коммивояжера (TSP) точное решение — метод ветвей и границ

/592454ca03b8381d59084d2e72685653.png)

Путешествие в тысячу ли начинается с одного шага. (Лао-Цзы)

Что делает код хорошим? Большинство программистов ответят: хороший код должен быть структурирован, легко читаем и понятен. Но так ли важно качество кода, если он медленный? В большинстве задач производительность кода не критична, хотя и желательна. Но есть задачи, время выполнения которых столь огромно, что выигрыш в производительности доминирует над всем остальным.

Я говорю про NP-трудные задачи (NP-трудность - недетерминированная полиномиальная трудность по времени) и на одной из данного класса хочу акцентировать ваше внимание. Задаче коммивояжера.

Мы не будем рассматривать эвристические алгоритмы, нам нужно точное решение.

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

В прошлой работе мы ознакомились с решением задачи коммивояжера на минимум методом динамического программирования. Метод конечно замечательный, но он ограничен объёмом памяти системы. Уже при n = 28 вершин, 16 Гб оперативной памяти недостаточно, а использовать память жёсткого диска очень неэффективно. Возможно, используя хитроумные подходы структурирования и сжатия памяти можно несколько улучшить алгоритм, но ненамного. Нужен иной подход, если мы хотим рассчитывать матрицы большего размера.

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

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

Хочу обозначить одну тонкость метода ветвей и границ, которую мало кто освещает:

На этапе выбора элемента ветвления и разделения решения на два подмножества M1 (содержащие ребро с максимальным штрафом) и M2 (не содержит ребро с максимальным штрафом), при рассмотрении множества M1 вычеркиваем относящиеся к выбранной клетке строку и столбец, а также заменяем значение ячейки соответствующей обратному пути на бесконечность.

Но вот что скрывается под понятием обратного элемента? Во многих реализациях, что я видел, смысл определения выражен не верно, проиллюстрируем.

/7fa7aeed65e29fd94eff360455c91d34.png)

Есть некий граф, для которого на предыдущих этапах мы уже нашли рёбра [0, 3], [3, 5], [6, 7], [7, 1] и на текущем шаге рассматриваем ребро [5, 6] множества M1.

Так вот обратным элементом для ребра [5, 6], будет не ребро [6, 5] (как можно было подумать), а ребро [1, 0]. И вычёркиваем данное ребро затем, чтобы избежать в графе подцикл. Естественно, мы так же вычёркиваем все дуги, исходящие из [5] (вычеркивание строки) и входящие в [6] (вычеркивание столбца).

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

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

Далее по ходу текста я буду выдвигать утверждения, которые кому-то могут показаться спорными, просто примите за факт.

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

Авторский подход заключается в том, чтобы рассматривать задачу коммивояжёра не как академическую, а как инженерную.

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

Алгоритм состоит в применении трёх мета шагов:

1. Производим приведение матрицы (редукция строк, столбцов), выбираем нулевой элемент с максимальной оценкой для разбиения.

2. На каждом ветвлении между выбором множества M1 или M2, всегда двигаться в M1, пока мы не достигнем дна. В матрице останется только один элемент, не предусматривающий ветвления, так мы получаем опорное решение. Сравниваем лучшее с текущим решением и запоминаем его, если оно короче.

3. Далее мы возвращаемся на уровень выше, проверяем для него множество M2 и вычёркиваем клетку. Переходим к шагу 1.

   Отдельно остановлюсь на условиях, при которых мы можем досрочно прекратить дальнейшее обследование ветви дерева ветвлений, тем самым сократив объём вычислений.

   • На первом шаге, если мы понимаем, что в какую-либо вершину или из неё больше невозможно проложить ни одного маршрута;

   • На втором шаге, если видим, что лучший из найденных пока маршрутов меньше нижней текущей границы;

   • На третьем шаге, если лучший из найденных пока маршрутов меньше суммы нижней текущей границы и максимальной оценки на шаге;

/0ae6231387f7330b104eb5e4a4dd208a.png)

Пример расчёта множества M1

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

Вы можете спросить, к чему эти сложности? Именно так мы избавляемся от хвостовой рекурсии при расчёте множества М2 и гарантируем, что глубина рекурсии для множества M1 никогда не превысит n.

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

Например, при n = 33 программе требуется не более 63КБ стека, при любых входных данных.

Из прочих неочевидных оптимизаций:

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

• Использовать только 32 битные переменные для всего, нужно для выравнивания обращений в памяти (выровненные обращения происходят быстрее);

• Использовать максимальное число для расчётов inf = 2147483647 (0x7fffffff), для того чтобы при сложении двух бесконечностей не получать переполнение регистра (не нужно проверять);

• Умышленный отказ от операций деления (очень дорогая инструкция);

• Переменные по возможности высвобождаются сразу, как перестают быть нужными;

• Объединить этап редукции с выбором нулевого элемента для разбиения, для уменьшения количества обращений к матрице;

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

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

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

Была проведена серия испытаний на случайном наборе точек на плоскости для оценки производительности алгоритма от количества вершин графа. Каждая серия состояла из тысячи случайно сгенерированных наборов.

/b6dcb70c2319753e6708e38e25bd7ce4.png)

Зависимость времени выполнения (сек) от размера матрицы - логарифмическая шкала

Графики были построены по 99, 98, 95 и 90 перцентилям от размера графа и времени в секундах. 99 перцентиль говорит о том, что мы найдём решение задачи в среднем в 99 случаях из ста, за указанное время для похожего набора входных данных.

Как вы можете заметить подход не панацея, но при определённых условиях даёт весьма неплохие результаты.

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

/6a2bb4f37ac9653e7afcfb6d3cbb1b0f.png)

Задача коммивояжёра на минимум и максимум

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

/9a9eb6e6ef50791e30e8b335268405ac.png)

Задача коммивояжёра на максимум

Хоть я и обожаю Python, но для ресурсоёмких задач он не подходит совершенно, даже с numpy. Привожу пример ранней наивной реализации с использование pandas чисто в целях ознакомления для новичков, но возможно кого-то подвигнет на изучение.

Я работал над данным алгоритмом более трёх лет наездами. Проект, для которого предназначался этот алгоритм, остался в далёком прошлом, но мне думается, что общественности будут любопытны мои наработки на данном поприще.

Буду рад откликам, замечаниям, предложениям, возражениям.

Код, приведённый к статье, разработан вашим покорным слугой и может быть использован вами под лицензией GNU GPL.

P.S. C Наступающим Новым годом!