Комментарии 29
А нельзя ли сформулировать эту задачу как weighted max sat ?
Все NP-полные задачи полиноминально сводятся друг к другу.
Как я понимаю вы хотели узнать можно ли похожим способом ускорить решение задачи выполнимости булевых формул? Возможно, пока не задавался данным вопросом.
Как могут быть связаны булевы формулы и задача коммивояжёра?
Тем, что обе задачи обладают NP-полнотой. И подходы применимые к одной из задач теоретически могут быть применены для решения другой.
Математически доказывается, что задачи сводятся друг к другу. Если найдете алгоритм полиномиального решения одной из них, то им же можно будет решить все остальные. Это собственно и есть доказательство принадлежности задачи к классу NP, если я правильно помню университетскую дискретную математику - сведение задачи к какой-то из уже известных задач этого класса. Иногда очень нетривиальные подходы применяются. Вот навскидку нашел какую-то статью, где SAT сводится к TSP через кучу промежуточных шагов.
https://fse.studenttheses.ub.rug.nl/11906/1/Masja_Bronts_2014_WB.pdf
Первый шаг, например, сведение задачи булевых формул к задаче поиска клики (множества вершин, порождающих полный подграф) графа. Там предполагается хитрый метод построения графа на основании формулы таким образом, что если формула выполнима - граф будет иметь клику определенного размера. То есть если мы можем решить одну задачу (поиск клики или определение выполнимости формулы) то автоматически решим и другую.
Ну и дальше еще несколько шагов по алгоритмам на графах, сводящих поиск клики к поиску наименьшего вершинного покрытия, а его в свою очередь - к поиску гамильтонова цикла в графе, а уже его - к задаче коммивояжера. На каждом шаге описывается преобразование графа, в итоге зная как решить одну задачу цепочки, мы можем свести к ней наш граф и получить связанное решение любой другой задачи.
Ничего не скажу об алгоритме, так как информации о нем очень мало, но даже некоммерческая версия Gurobi легко справляется с 60 вершинами, а коммерческая, на практике, вполне удовлетворительно ведет себя на сотнях вершин. Так что ТС есть к чему стремиться )
Gurobi легко справляется с 60 вершинами...
За какой алгоритм мы говорим?
Кстати, авторский алгоритм ЦЛП успешно реализовывал и с помощью солвера Gurobi. Но так как он проприетарный финальный вариант работает через cbc от coin-or.
Если бы не «Простой» уровень сложности статьи, я бы не стал читать. NP-полные задачи, динамическое (да и линейное) программирование, а тем более эксклюзивные авторские методы требуют большой самоотдачи для понимания)
Но в данном случае, вроде все просто написано:
Основной посыл состоит в том, что мы разбиваем одну большую экспоненциальную задачу на ряд более простых экспоненциальных задач. Но общее время работы последовательности мелких задач значительно меньше, чем решение одной большой задачи.
В голове сразу: 2^3N >> 2^N + 2^N + 2^N. Вау! Но как же он смог разбить большую задачу? А точно сумма решений мелких задач равна решению большой? Такое ведь надо доказывать...
Очень хочется получить ответы на эти вопросы! Читаем дальше:
Кратко повторю суть метода: Начало такое же, как у моделей MTZ и DFJ.
Первое отличие состоит в том, что мы не будем указывать верхнюю границу для x. (…) Так мы уменьшаем число ограничений линейного решателя на x неравенств.
Ещё одна оптимизация, которая не учитывалась в прошлых работах: мы добавляем ограничения только для тех подмножеств, размер которых не превышает половины n
и это всё)
не утверждаю, что метод не рабочий, и даже что он не «наибыстрейший», но его суть осталась для меня не раскрыта.
Это же не первая статья цикла, я по ходу повествования оставлял ссылки на предыдущие работы. Повторять из раза в раз сложное пояснение только затруднит понимание материала.
Основа метода была обозначена в работе (правда для симметричной задачи, но там мало отличий). А тут можно увидеть реализацию алгоритма в коде python.
Но общее время работы последовательности мелких задач значительно меньше, чем решение одной большой задачи.
Тут наверно стоило бы выделить, что именно для этого подхода решения с ЦЛП (имеет экспоненциальную сложность решения в худшем случае, но в среднем то полином, за счёт этого и выигрыш), а не для все математической теории.
23 года назад некий энтузиаст решил, что способен решать NP-полные задачи. В ходе возникшего обсуждения
https://forum.ixbt.com/topic.cgi?id=40:1887
было выяснено, что:
он не знает, что такое NP-полнота
не понимает, что оптимальность, да и вообще работоспособность алгоритма не демонстрируются на примерах, а доказываются
не различает точное и приближённое решения
абсолютно уверен в том, что разработал метод решения задачи коммивояжёра
Дискуссия переросла в смесь троллинга с ликбезом, дав участникам возможность продемонстрировать кому остроумие, кому терпение и талант педагога, но и умение программировать.
В ходе обсуждения пришлось мне восстановить свой курсовой 25-летней давности, реализовывавший (к настоящему времени уже 60-летней давности) алгоритм Литтла, Мурти, Суини и Кэрел (ветвей и границ), задачу 45х45 на очень скромном даже для тех дет офисном компьютере решавший за секунды, и вполне справлявшийся с 300х300 (а поиск по литературе показал, что рекорд для этой задачи превысил к тому времени 15 тысяч вершин).
Вынужден задать вопрос - как соотносятся результаты автора с нынешним состоянием вопроса, учитывая, что если не 60, то 20 лет назад вполне решались задачи более чем его "500 в лучшем случае".
Ваших словах я ощущаю скрытый подтекст, в котором вы намекаете на эквивалентность обсуждения двадцатилетней давности и моей статьёй. Я никого ни в чём не убеждаю, только лишь описываю то, что получил на собственном опыте.
По поводу ветвей и границ с полным перебором 45х45, могу сказать больше, мне удавалось находить решение и для случайных матриц размером на 55х55, но это был столь редкий процент удачных случаев, что его не рассматривать как типовой.
Теперь по поводу симметричных матриц размером более 15 тысяч элементов, то вы видимо невнимательно читали преамбулу к повествованию. Существуют методы для специальных условий входных данных, которые дают решение для очень больших размерностей. Но это особые, специальные условия, для ассиметричной задачи коммивояжёра в общем виде не применимы!
Давайте для начала заметим, что ветви и границы это не полный перебор, а перебор с отсечением. Затем, что симметричность в этом методе никак не используется. Что до расчёта с 15 тысячами, сделанного более 20 лет назад - по-видимому, там действительно симметрическая матрица расстояний, поскольку это расстояния между городами Германии. В настоящее время рекорд для точного решения составляет 85900 точек (программа Concorde).
Возможно, Вам стоит поискать какие-либо недоработки в программе, не позволяющие решать более крупные задачи? Насколько мне известно, размер 300х300 обрабатывался ещё в 1960е.
О, помнится, была эта же тема в ru.mathematics или в ru.cryptography.
Серьёзная практическая работа. Такой вот вопрос у меня, от противного.
А задача "поиск максимального пути с заходом в каждый город по 1-му разу" быстрее решается?
Этот же алгоритм способен решать задачу коммивояжёра на максимум без переделки.
Достаточно поменять знак у элементов входной матрицы смежности. И да, задача на максимум решается медленнее.
Странно. По моим первоначальным прикидкам это сводится к следующей задаче
Составление таблицы максимальных путей из произвольно выбранного города до других городов. ("Отжигом" например)
2. Дальше я предполагал, что достаточно выбрать из этой таблицы путь с максимальным значением "путь + возврат в исходный город"
т.е. я предполагал, что максимальный путь из одного города в другой захватит все города.
Это у вас вариант жадного поиска вырисовывается. Он редко выдаёт оптимальный результат.
Подождите
задача поиска максимального пути выхода и возврата из города однозначно решается отжигом - максимальную цену и путь мы получим
Проблема в том, что при этом может не захватится какой-то город, то это говорит о том, что где-то нарушается правило треугольника для трёх точек a + b < c
Такую ситуацию можно легко свести к равнозначной задаче без нарушения правила треугольника, просто добавив к каждому ценнику максимальный ценник перехода (dr)
и тогда неравенство треугольника будет соблюдаться всегда a + b > c и для этой задачи мы получим максимальный путь включающий все города
3. получить решение первоначальной задачи тогда можно просто уменьшив путь на добавку n * dr
Т.е. задача решаема, и очень быстро
хм, точно, не прокатит из-за несимметричности цены пути
Вчера просмотрел выпуск Топлес на Ютубе "Разум РОЯ" советую всем посмотреть. Выпуск был о том, как насекомые, беспозвоночные, бактерии решают задачу коммивояжёра без знаний математики. Удачно наткнулся на вашу статью и прочитал ее дважды )
Как вы отметили, биологические системы хорошо находят решение задачи коммивояжёра. Однако есть одно существенное замечание, они делаю это приближённо!
Имитация отжига и муравьиный алгоритм, делают это не хуже.
Мы же говорили за точное решение.
А для обратной задачи алгоритмы есть?
Построить граф из n вершин, с заданным распределением длин маршрутов коммивояжёра в нём? Допустим один длины L, 2 - (L+1), 3 - (L+2) ну и т.д.
Чтобы тестировать приближённые методы, например. Или чувствительность точных ко всяким особенностям графа.
Есть ли какие-то быстрые оценки распределения длин искомых маршрутов?
Что на счет генетического алгоритма?)
В данный алгоритм можно учесть параметры весов на точки, чтобы добавить учет ограничения по времени ?
часто требуется решение задачи коммивояжера с временными окнами ...
Линейное программирование позволяет добавлять дополнительные ограничения в модель, так что вполне возможно. Правда, не совсем представляю, как звучит задача с временными окнами.
Задача с временными окнами обеспечение того, чтобы все узлы посещались в пределах заданных временных окон
Имеем:
Диапазон временных окон 10:00-12:00, 13:00-14:00, 16:00-18:00 и 00:00-23:59(в любое время)
Точка_1 - 00:00-23:59
Точка_2 - 16:00-18:00
Точка_3 - 10:00-12:00
Точка_4 - 00:00-23:59
Точка_5 - 00:00-23:59
на выходе должно упорядочить по хронологии времени а потом уже по короткому маршруту
Точка_3 - 10:00-12:00
Точка_1 - 00:00-23:59
Точка_5 - 00:00-23:59
Точка_2 - 16:00-18:00
Точка_4 - 00:00-23:59
В вашей интерпретации больше походит не на задачу оптимизации пути, а на поиск согласованного расписания. Для такой задачи мне представляется нужно использовать не целочисленное программирование, а программирование в ограничениях. Мне приходилось использовать решатель CP-SAT из OR-Tools для похожих задач, возможно и вам поможет.
Задача коммивояжёра в общем виде. Наибыстрейшее точное решение