К величию есть только один путь, и этот путь проходит через страдания.
- Альберт Эйнштейн
Эта работа является заключением пятилетнего марафона по поиску самого быстрого способа нахождения минимального точного решения для задачи коммивояжёра в общем виде.
Тут хочу подытожить все опробованные подходы и выбрать лучший по моему мнению.
Мне известны четыре доказанных способа нахождения точного решения ассиметричной задачи коммивояжёра.
1. Метод грубой силы;
2. Метод динамического программирования с меморизацией;
3. Метод ветвей и границ с полным перебором;
4. Методы, основанные на линейном программировании.
Тут мы не будем рассматривать алгоритмы, которые не гарантируют именно точное решение. Хотя многие подходы, основанные на приближённых эвристиках, дают замечательные быстрые результаты, но нет гарантии, что мы получили именно минимальный результат. Так же мы не будем считать расстояние между точками как евклидово пространство. Для евклидова пространства есть алгоритмы, значительно сокращающие область решений. Вдобавок предлагаю считать задачу ассиметричной, даже если это не так. То есть, мы вообще не имеем представления о входной матрице ничего, кроме того, что граф ею образованный не содержит петель, но и это обстоятельство можно игнорировать. Только полный хардкор!
Приступим!
Метод грубой силы
Заключается в циклическом переборе всех возможных комбинаций решения задачи с сохранением кратчайшего решения. Метод практически бесполезен в силу неимоверной вычислительной сложности. Для задачи коммивояжёра в общем виде вычислительная сложность метода составляет:
(n-1)! – Количество комбинаций как факториал от числа городов.
Уже при n = 20, нам понадобится перебрать 19! = 121645100408832000 вариантов. Если перебирать по миллиарду комбинаций в секунду у нас уйдёт несколько лет.
Грубо оценим возможность метода как способного решать задачу на не более полтора - два десятка городов.
Метод динамического программирования с меморизацией.
Очень крутой метод для решения задачи коммивояжёра. Основное его достоинство состоит в том, что он очень устойчив от входных данных по скорости решения, к тому же неплохо параллелится. В прошлой статье приведена реализация, подходящая для GPU.
Но у данного метода есть ахиллесова пята: требуется экспоненциально большее число памяти для хранения промежуточных вычислений, а именно (n-1)*2^(n-2). Каждое увеличение массива на единицу требует более чем двукратного увеличения объёма памяти.
Для задачи размером n = 30, потребуется 29 * 268435456 * 4 бита - около 29 GB памяти.
Оцениваю способность метода решать задачи до трёх десятков городов.
Метод ветвей и границ с полным перебором;
От предыдущих двух подходов метод ветвей и границ отличается тем, что позволяет отбрасывать решения, которые уже на этапе расчёта хуже лучшего найденного. Так мы можем отбросить огромные области дерева решений, значительно сократив время. Однако данный метод очень неустойчив по скорости от набора входных данных. Разные решения на матрице одного размера могут отличаться по времени в десятки тысяч раз и более по скорости расчётов.
В зависимости от реализации метода можно получить значительное превосходство над динамическим программированием, но нет гарантии, что мы сможем дождаться результата для конкретной задачи. В статье я описал собственный вариант алгоритма на C, с которым мне удавалось найди точное решения задачи коммивояжёра в 90% случаях для случайных наборов данных до n = 40.
Приблизительно оцениваю метод как способный решать некоторые задачи размером до n ~ 40 городов.
Методы, основанные на линейном программировании.
Задачу коммивояжёра можно сформулировать, как задачу целочисленного линейного программирования. Известно несколько формулировок. Наиболее известные две из них:
Миллера–Таккера–Землина (MTZ)
Данцига–Фалкерсона–Джонсона (DFJ)
В обоих формулировках мы перечисляем все возможные пути между городами целочисленной линейной переменной x = {0, 1}, где x принимает значение 1, если путь выбирается в результирующее решение, 0 в обратном случае.
a) Формулировка Миллера–Таккера–Землина (MTZ)
Описывается следующей схемой:
Из всех моделей, что встречаются как решение задачи коммивояжёра с ЦЛП на просторах сети, эта формулировка самая популярная. Решение находится в один шаг. Мы ищем минимальный цикл, проходящий через все вершины ровно по одному разу. Нижний блок условий запрещает появление циклов меньшего размера.
На тестах MTZ иногда выигрывает у динамического программирования по времени решения, но совсем не устойчивый к разбросу исходных данных. Однако алгоритм не очень требователен к оперативной памяти в отличие от ДП.
Предлагаю считать его не слишком практичным, но всё же способным решать задачи до трёх десятков вершин, иногда немного более.
b) Формулировка Данцига–Фалкерсона–Джонсона (DFJ)
Данная формулировка ещё меньше подходит для нахождения решения задачи коммивояжёра посредством ЦЛП, так как условие исключения подтура создаёт экспоненциально большее число ограничивающих условий. В чистом виде это практически полный перебор. Только мы перебираем не комбинации, а ограничения, а их очень, очень много: (n-1)*2^(n-2).
Оцениваю подход как способный решать задачи до двух десятков городов с натягом.
с) Авторский подход
Если взять за основу модель Данцига–Фалкерсона–Джонсона, а затем несколько изменить подход к выбору ограничивающих условий, то можно получить просто гигантский прирост к скорости решения.
Об этом писал в работах раз, два и три. Возможно мой литературный талант несколько далёк от совершенства и мне не всегда удаётся доносить до читателей основную мысль. Тут мне же хотелось подытожить всё описанное выше и отобразить самый лучший из подходов известных мне.
Основной посыл состоит в том, что мы разбиваем одну большую экспоненциальную задачу на ряд более простых экспоненциальных задач. Но общее время работы последовательности мелких задач значительно меньше, чем решение одной большой задачи.
Чтобы понять насколько значительнее, скажу, что мне удавалось решать точно задачи до полутысячи вершин. Правда это получалось на хороших входных данных, однако и в худшем случае метод бьёт все другие методы, приведённые выше с огромным запасом.
Кратко повторю суть метода: Начало такое же, как у моделей MTZ и DFJ.
Хотя я предпочитаю нумерацию индексов с нуля, а не единицы, но не суть.
Первое отличие состоит в том, что мы не будем указывать верхнюю границу для x.
x = {0, 1} превращается в: x ≥ 0, где x – целое.
Так мы уменьшаем число ограничений линейного решателя на x неравенств. Верхнее ограничение неявно получается из того условия, что число входящих рёбер в каждую вершину и исходящих из неё строго равно одной. Так зачем нам дополнительно ограничивать переменную хij сверху, если сумма всегда не более одного?
Далее мы просто решим систему линейных уравнений и получим опорное решение. Затем проверим, не распалось ли решение на несколько подмножеств, если в результате подмножеств получилось более одного, добавим ограничение в модель и повторим шаг.
Если в результате осталось только одно множество, то считаем его искомым, мы нашли минимальное решение.
Ещё одна оптимизация, которая не учитывалась в прошлых работах: мы добавляем ограничения только для тех подмножеств, размер которых не превышает половины n. Это решение исходит из того, что при получении подмножества размером больше n / 2, должно обязательно существовать иное подмножество размером меньше n / 2, а все такие ограничения мы вносим в модель. Так мы можем слегка уменьшить число ограничений, убрав избыточные условия.
Поскольку мы берём только подмножества размером меньше половины n, нам всегда будет выгоднее выбирать следующую формулировку условия для создания ограничения:
Для каждого подмножества число связей в нём должно быть, как минимум на одно меньше количества вершин в данном подмножестве.
Метод отлично себя чувствует на случайных данных, хуже на симметричных или однородных наборах.
Для объективности приведу одну из худших для метода задачу. Это ряд точек в метрическом пространстве на одинаковом расстоянии друг от друга. Матрица смежности рассчитана через эвклидову норму.
Так как данный пример имеет очень много решений, решателю линейных уравнений нужно перебрать их все.
Реализация метода на Python: github.
Сравнивать модели ЦЛП можно посредством следующей метафоры:
DFJ – всё равно что насыпать огромный террикон ограничений. Ограничений будет очень много, практически нереально получить результат, для этого нужно обработать все условия.
MTZ – как башня - крепость. С наружи каменная кладка условий, что не даёт расползтись множествам. Такую башню проще соорудить чем насыпать просто гору земли аналогичной высоты, но всё же достаточно много работы.
Авторский подход – Можно сравнить с железобетонным каркасом современного здания. Мы поэтажно заливаем слой за слоем, добавляя всё новые ограничения, которые соответствуют уже найденным решениям. Благодаря такому подходу мы можем строить очень высокие строения, считай находить решения большего размера за то же время.
Резюме:
Мы прошлись по методам получения точного решения задачи коммивояжёра в общем виде.
Все рассмотренные подходы являются экспоненциальными по времени от размера исходных данных! Однако время необходимое на решение может быть очень разным в зависимости от метода.
Грубо оцениваю возможности методов, как способных решать задачи размерности n от числа вершин графа.
1. Метод грубой силы не более 15 - 20
2. Метод динамического программирования с меморизацией не более 30
3. Метод ветвей и границ с полным перебором не более 30 - 40
4. Методы, основанные на линейном программировании:
a) DFJ не более 20
b) MTZ не более 30 - 35
c) Авторский подход от 50 в худшем случае и более 500 в лучшем.
Выводы предлагаю сделать самим.
Благодарю за внимание!
Комментарии (24)
ptr128
05.09.2024 05:51Ничего не скажу об алгоритме, так как информации о нем очень мало, но даже некоммерческая версия Gurobi легко справляется с 60 вершинами, а коммерческая, на практике, вполне удовлетворительно ведет себя на сотнях вершин. Так что ТС есть к чему стремиться )
rebuilder Автор
05.09.2024 05:51Gurobi легко справляется с 60 вершинами...
За какой алгоритм мы говорим?
Кстати, авторский алгоритм ЦЛП успешно реализовывал и с помощью солвера Gurobi. Но так как он проприетарный финальный вариант работает через cbc от coin-or.
ptr128
05.09.2024 05:51Я же честно признался, что об алгоритме почти ничего знаю, так как информации о нем очень мало. Точно могу сказать, что идет послойка. Сначала MILP, а уже потом дискретка. Подробности реализации River Logic не раскрывает.
santanico
05.09.2024 05:51+1Если бы не «Простой» уровень сложности статьи, я бы не стал читать. NP-полные задачи, динамическое (да и линейное) программирование, а тем более эксклюзивные авторские методы требуют большой самоотдачи для понимания)
Но в данном случае, вроде все просто написано:
Основной посыл состоит в том, что мы разбиваем одну большую экспоненциальную задачу на ряд более простых экспоненциальных задач. Но общее время работы последовательности мелких задач значительно меньше, чем решение одной большой задачи.
В голове сразу: 2^3N >> 2^N + 2^N + 2^N. Вау! Но как же он смог разбить большую задачу? А точно сумма решений мелких задач равна решению большой? Такое ведь надо доказывать...
Очень хочется получить ответы на эти вопросы! Читаем дальше:
Кратко повторю суть метода: Начало такое же, как у моделей MTZ и DFJ.
Первое отличие состоит в том, что мы не будем указывать верхнюю границу для x. (…) Так мы уменьшаем число ограничений линейного решателя на x неравенств.
Ещё одна оптимизация, которая не учитывалась в прошлых работах: мы добавляем ограничения только для тех подмножеств, размер которых не превышает половины n
и это всё)
не утверждаю, что метод не рабочий, и даже что он не «наибыстрейший», но его суть осталась для меня не раскрыта.
rebuilder Автор
05.09.2024 05:51Это же не первая статья цикла, я по ходу повествования оставлял ссылки на предыдущие работы. Повторять из раза в раз сложное пояснение только затруднит понимание материала.
Основа метода была обозначена в работе (правда для симметричной задачи, но там мало отличий). А тут можно увидеть реализацию алгоритма в коде python.
Но общее время работы последовательности мелких задач значительно меньше, чем решение одной большой задачи.
Тут наверно стоило бы выделить, что именно для этого подхода решения с ЦЛП (имеет экспоненциальную сложность решения в худшем случае, но в среднем то полином, за счёт этого и выигрыш), а не для все математической теории.
sanitareugen
05.09.2024 05:51+323 года назад некий энтузиаст решил, что способен решать NP-полные задачи. В ходе возникшего обсуждения
https://forum.ixbt.com/topic.cgi?id=40:1887
было выяснено, что:
он не знает, что такое NP-полнота
не понимает, что оптимальность, да и вообще работоспособность алгоритма не демонстрируются на примерах, а доказываются
не различает точное и приближённое решения
абсолютно уверен в том, что разработал метод решения задачи коммивояжёра
Дискуссия переросла в смесь троллинга с ликбезом, дав участникам возможность продемонстрировать кому остроумие, кому терпение и талант педагога, но и умение программировать.
В ходе обсуждения пришлось мне восстановить свой курсовой 25-летней давности, реализовывавший (к настоящему времени уже 60-летней давности) алгоритм Литтла, Мурти, Суини и Кэрел (ветвей и границ), задачу 45х45 на очень скромном даже для тех дет офисном компьютере решавший за секунды, и вполне справлявшийся с 300х300 (а поиск по литературе показал, что рекорд для этой задачи превысил к тому времени 15 тысяч вершин).
Вынужден задать вопрос - как соотносятся результаты автора с нынешним состоянием вопроса, учитывая, что если не 60, то 20 лет назад вполне решались задачи более чем его "500 в лучшем случае".
rebuilder Автор
05.09.2024 05:51Ваших словах я ощущаю скрытый подтекст, в котором вы намекаете на эквивалентность обсуждения двадцатилетней давности и моей статьёй. Я никого ни в чём не убеждаю, только лишь описываю то, что получил на собственном опыте.
По поводу ветвей и границ с полным перебором 45х45, могу сказать больше, мне удавалось находить решение и для случайных матриц размером на 55х55, но это был столь редкий процент удачных случаев, что его не рассматривать как типовой.
Теперь по поводу симметричных матриц размером более 15 тысяч элементов, то вы видимо невнимательно читали преамбулу к повествованию. Существуют методы для специальных условий входных данных, которые дают решение для очень больших размерностей. Но это особые, специальные условия, для ассиметричной задачи коммивояжёра в общем виде не применимы!
sanitareugen
05.09.2024 05:51Давайте для начала заметим, что ветви и границы это не полный перебор, а перебор с отсечением. Затем, что симметричность в этом методе никак не используется. Что до расчёта с 15 тысячами, сделанного более 20 лет назад - по-видимому, там действительно симметрическая матрица расстояний, поскольку это расстояния между городами Германии. В настоящее время рекорд для точного решения составляет 85900 точек (программа Concorde).
Возможно, Вам стоит поискать какие-либо недоработки в программе, не позволяющие решать более крупные задачи? Насколько мне известно, размер 300х300 обрабатывался ещё в 1960е.
Kealon
05.09.2024 05:51Серьёзная практическая работа. Такой вот вопрос у меня, от противного.
А задача "поиск максимального пути с заходом в каждый город по 1-му разу" быстрее решается?
rebuilder Автор
05.09.2024 05:51Этот же алгоритм способен решать задачу коммивояжёра на максимум без переделки.
Достаточно поменять знак у элементов входной матрицы смежности. И да, задача на максимум решается медленнее.
Kealon
05.09.2024 05:51Странно. По моим первоначальным прикидкам это сводится к следующей задаче
Составление таблицы максимальных путей из произвольно выбранного города до других городов. ("Отжигом" например)
2. Дальше я предполагал, что достаточно выбрать из этой таблицы путь с максимальным значением "путь + возврат в исходный город"
т.е. я предполагал, что максимальный путь из одного города в другой захватит все города.
rebuilder Автор
05.09.2024 05:51Это у вас вариант жадного поиска вырисовывается. Он редко выдаёт оптимальный результат.
Kealon
05.09.2024 05:51Подождите
задача поиска максимального пути выхода и возврата из города однозначно решается отжигом - максимальную цену и путь мы получим
Проблема в том, что при этом может не захватится какой-то город, то это говорит о том, что где-то нарушается правило треугольника для трёх точек a + b < c
Такую ситуацию можно легко свести к равнозначной задаче без нарушения правила треугольника, просто добавив к каждому ценнику максимальный ценник перехода (dr)
и тогда неравенство треугольника будет соблюдаться всегда a + b > c и для этой задачи мы получим максимальный путь включающий все города
3. получить решение первоначальной задачи тогда можно просто уменьшив путь на добавку n * drТ.е. задача решаема, и очень быстро
fllipy
05.09.2024 05:51Вчера просмотрел выпуск Топлес на Ютубе "Разум РОЯ" советую всем посмотреть. Выпуск был о том, как насекомые, беспозвоночные, бактерии решают задачу коммивояжёра без знаний математики. Удачно наткнулся на вашу статью и прочитал ее дважды )
rebuilder Автор
05.09.2024 05:51Как вы отметили, биологические системы хорошо находят решение задачи коммивояжёра. Однако есть одно существенное замечание, они делаю это приближённо!
Имитация отжига и муравьиный алгоритм, делают это не хуже.
Мы же говорили за точное решение.
niktor_mpt
05.09.2024 05:51А для обратной задачи алгоритмы есть?
Построить граф из n вершин, с заданным распределением длин маршрутов коммивояжёра в нём? Допустим один длины L, 2 - (L+1), 3 - (L+2) ну и т.д.
Чтобы тестировать приближённые методы, например. Или чувствительность точных ко всяким особенностям графа.
Есть ли какие-то быстрые оценки распределения длин искомых маршрутов?
andy_p
А нельзя ли сформулировать эту задачу как weighted max sat ?
rebuilder Автор
Все NP-полные задачи полиноминально сводятся друг к другу.
Как я понимаю вы хотели узнать можно ли похожим способом ускорить решение задачи выполнимости булевых формул? Возможно, пока не задавался данным вопросом.
inetstar
Как могут быть связаны булевы формулы и задача коммивояжёра?
rebuilder Автор
Тем, что обе задачи обладают NP-полнотой. И подходы применимые к одной из задач теоретически могут быть применены для решения другой.
JediPhilosopher
Математически доказывается, что задачи сводятся друг к другу. Если найдете алгоритм полиномиального решения одной из них, то им же можно будет решить все остальные. Это собственно и есть доказательство принадлежности задачи к классу NP, если я правильно помню университетскую дискретную математику - сведение задачи к какой-то из уже известных задач этого класса. Иногда очень нетривиальные подходы применяются. Вот навскидку нашел какую-то статью, где SAT сводится к TSP через кучу промежуточных шагов.
https://fse.studenttheses.ub.rug.nl/11906/1/Masja_Bronts_2014_WB.pdf
Первый шаг, например, сведение задачи булевых формул к задаче поиска клики (множества вершин, порождающих полный подграф) графа. Там предполагается хитрый метод построения графа на основании формулы таким образом, что если формула выполнима - граф будет иметь клику определенного размера. То есть если мы можем решить одну задачу (поиск клики или определение выполнимости формулы) то автоматически решим и другую.
Ну и дальше еще несколько шагов по алгоритмам на графах, сводящих поиск клики к поиску наименьшего вершинного покрытия, а его в свою очередь - к поиску гамильтонова цикла в графе, а уже его - к задаче коммивояжера. На каждом шаге описывается преобразование графа, в итоге зная как решить одну задачу цепочки, мы можем свести к ней наш граф и получить связанное решение любой другой задачи.