Comments 38
Хочу уточнить правильно ли я вас понял: если есть граф, который можно расположить на плоскости, при этом "веса рёбер" должны быть в точности равны расстояниям - то для такого случая задача коммивояжёра выродится в полиномиальную.
Если это так - то для читателей лучше если предварительыне условия применения метода будут прописаны в начале статьи в явном виде. А не стыдливые "*" (как будто читаешь договор где тебя хотят обмануть) расставлять.
Не совсем так, задача коммивояжера в общем виде остаётся NP-сложной, я это не оспариваю. Но в практических задачах с линейным программированием, нужно очень сильно постараться, чтобы заставить решатель уйти в экспоненту. И это не зависит от того, определена на плоскости она или нет. Это примерно, как свести QSort к O(n^2), а разбивая задачу на подзадачи мы очень сильно снижаем эту вероятность в целом.
Однако и полином полиному рознь. Мы за счёт дополнительных ухищрений значительно уменьшаем сложность задачи. Но если для Эвклидовой плоскости мне встречался алгоритм и с лучшей скоростью работы, то вот за асимметричную задачу такого сказать не могу.
Звёздочка как раз и говорит, что бывают исключения.
Извините чего-то не понимаию.
Вы предлагаете:
1. Провести триангуляцию Делоне (https://ru.wikipedia.org/wiki/Триангуляция_Делоне - работает для графов на плоскости).
2. Что-то сней сделать.
Как мне п.1 делать? Для произвольного графа этот алгоритм не определён.
Для симметричной задачи граф задаётся набором точек на плоскости, мы не задаём матрицу смежности. Затем для этих точек мы и строим триангуляцию Делоне. Расстояния рассчитывается только для нужных рёбер через Евклидову норму.
Вы можете не использовать предложенную мной эвристику и задать полносвязаную матрицу смежности, алгоритм съест и так, но выигрыша в скорости будет мало.
Для симметричной задачи граф задаётся набором точек на плоскости, мы не
задаём матрицу смежности. Затем для этих точек мы и строим триангуляцию
Делоне.
Это же и значит - вы рассматриваете графы которые можно расположить на плоскости, где "длина ребра = эвклидова метрика"? Так?
ПС
Я не понимаю, зачем на первый мой вопрос вы ответили "нет".
Класс графов представимых на плоскости - крайне узкий, в него не входят:
- дорожные сети
- электорехника \ микроэлектроника
- навигация (вообще всё, где можно двигаться с разной скорость)
- молекулярная структура
Да сложнее придумать что в ваш класс графов входит.
Это же и значит - вы рассматриваете графы которые можно расположить на плоскости, где "длина ребра = эвклидова метрика"? Так?
Да это правда, но не вся.
У меня сложилось впечатление, что вы невнимательно прочитали статью.
Для Эвклидовой плоскости, да, используется эвристика с триангуляцией Делоне. А для задач, что вы перечислили, используется другой алгоритм – ассиметричный. Вот уже этот алгоритм стравляется со всеми задачами, он так же описан в статье, хотя сильно медленнее.
Молекулярная структура-то каким образом представима на плоскости? То, что на бумажке рисуют - это проекция.
В работе описаны два алгоритма, первый для плоскости он быстрее, второй для общей задачи коммивояжера (в том числе для молекулярной структуры), он медленнее, но так же решается точно.
Это как если у вас был бы спортивный автомобиль для ровных дорог, и кроссовер для бездорожья.
Класс графов, представимых на плоскости крайне узкий, в него НЕ входят:
...
Как верно замечено выше, задача коммивояжёра формально ставится не для евклидовой плоскости (независимо от того, симметричная она или асимметричная). Она же в своих практических применениях не о реальных путешествиях по земной поверхности. Поэтому не выйдет укорачивать путь, соединяя несмежные вершины.
Да и даже на реальной Земле из условного Норильска в Омск может выйти быстрее добраться через Москву, чем напрямую. Так что триангуляция вам ничем не поможет.
Евклидова задача коммивояжера только частный случай общей задачи, который возможно решать значительно быстрее. На мой взгляд, глупо отказываться от возможности получить преимущество, в конкретной области применения.
И да, целочисленное линейное программирование по схеме в статье, переваривает точно дорожные графы на сотню – другую вершин.
Присоединяюсь к предыдущему оратору и прошу тогда описать область применения. Пока ваше описание выглядит так, как будто вы ищете самую короткую ломаную на плоскости, вершины которой могут находиться в заданном множестве точек. Что имеет смысл, но к задаче коммивояжёра относится примерно никак.
В задаче коммивояжёра вы в любой момент можете забрести в вершину с огромной нагрузкой на другие инцидентные рёбра, и весь ваш путь пойдёт прахом. Именно из-за отсутствия рекуррентно заданной меры.
Тут вся загвоздка как раз в том, что у многих читающих нет понимания, как работает линейное программирование. У меня самого ушло много времени на то, что осознать, как это функционирует. В статье через метафору мяча попробовал донести, но видимо неудачно.
Не может быть ни каких ‘забрести в вершину’, мы не перебираем комбинации. Работаем только с множествами, и соединяем множества, через линейные уравнения. В данном случае множества это найденные циклы в графе.
Когда вы оцениваете вычислительную сложность алгоритма, то нельзя просто так пользоваться эквивалентными преобразованиями представления графа. Чтобы построить такое эквивалентное представление, вам тоже потребуется вычислительная работа. Какова сложность построения вашего мяча? Она сама по себе экспоненциально зависит от размерности задачи. А обычные применения задачи коммивояжёра (например, в экономике) строятся в пространствах очень высоких размерностей.
Размерность многомерного пространства и правда будет очень высокой. Пример: для направленного графа на 200 вершин = 39800 мерное пространство. Но это уже сложность решателя линейных уравнений, его для этого и делают.
Тонкость в том, что надо сначала ещё эту матрицу 39800x39800 построить. Это какое O от 200?
Хотя и решить систему линейных уравнений такого порядка – тоже дело непростое. Очевидно, что такая матрица будет очень плохо обусловлена. А вычислительная сложность тоже нелинейно зависит от разрядности.
Нет, тут всё проще. 39800 переменных – это и есть n^2-n, от 200 вершин.
Изначально решается матрица 39800 x 400. На следующих шагах, она станет немного больше по высоте, но не так уж сильно (в 2-4 раза). Шагов за 15-30 (в худшем случае n/2) алгоритм находит решение такого размера. Так что всё не как уж и печально. Кроме того солверы обычно наделяют различными методами, ускоряющими решения.
Интересный материал, спасибо! Это уже не первая ваша статья по TSP и в большинстве случаев недостает сравнения. Когда речь идет об одном алгоритме, кажется, что эта наилучший метод решения и других не существует. Но так ли это? Даже сравнение с алгоритмами из предыдущих ваших статей добавило бы объективности, учитывая громкость названия текущей статьи.
По поводу сценария - https://math.uwaterloo.ca/tsp/data/ml/monalisa.html - может будет полезно на будущее. Кроме этого, localsolver делает заявку на лидерство по решению TSP: https://www.localsolver.com/benchmark/localsolver-vs-gurobi-traveling-salesman-problem-tsp Можно также взять данные из их benchmark'a. Конечно, сравнивать эвристический подход с точным это как бои без правил, но конкурентность предлагаемого подхода оценить можно.
У ortools есть собственный решатель задач vrp, в частном случае - это tsp. Можно так же сравнить с этой библиотекой.
Спасибо! С удовольствием читал ваши статьи, многое почерпнул для себя.
Возможно, мне не пока не достаёт лоска в изложении своих идей, но от этого они не становятся хуже. Придерживаюсь того, что человек, которому интересна освещённая тема обязательно проверит код на практике.
Соревноваться с эвристическими методами бессмысленно, тут вы правы.
Ну, что, ждём найденные суперперестановки для n > 5
Интересная статья, спасибо!
В результате получается граф, который точно содержит минимальное решение. Данный факт получен эмпирическим путём, а затем многократно подтверждён численным моделированием.
Самое интересное-то и не доказано. Скорее всего вам просто везло.
Конечно, мне повезло, только не в том смысле, что решение случайное. В статье про ветви и границе, лично Вы, предлагали мне поискать эвристику через эвклидово расстояние. И вот, спустя год, я предлагаю вам решение, код для проверки, а вы ещё требуете доказательства.
Моё понимание математики находится не на том уровне, чтобы вывести доказательство в виде формул. Однако, определённые основания утверждать, что граф содержит точное решение у меня есть. Хотелось бы получить контрпример со стороны сообщества или хотя бы выкладку, почему я не прав.
Нет, я имел ввиду, что вы, возможно, просто не нашли тот тест, на котором оптимальное решение проходит вот через эти оставленные ребра.
Вы даете некоторое неочевидное и серъезное утверждение. Это вы должны приводить веские доказательства этого факта.
Кажется, что тест вроде вот этого ломает ваше решение:
Серым покаазан пердположительный оптимальный путь. Вот там вторая сверху горизонтальная линия проходит через 4 треугольнкиа - по ребру, которое вы удаляете.
Чтобы именно этот путь был оптимален можно на предполагаемых ребрах в пути (кроме удаленноего, естественно) понатыкать много-много вершин. Меняя пропорции можно добиться примерно такого пути.
В том то и дело, что такое поведение как вы нарисовали, невозможно. Как только вы приводите алгоритм к граничному состоянию, весь маршрут перестраивается полностью. Ещё в прошлой статье с окружностями подметил эту тенденцию, но там подход был не совсем верным. Я очень долго моделировал общее решение, в том числе и с триангуляциями. И только триангуляция Делоне даёт нужный результат. С остовыми деревьями такого эффекта нет.
Как только вы приводите алгоритм к граничному состоянию, весь маршрут перестраивается полностью.
Всмысле? Добавляя точки на ребрах мы можем заставить кратчайший путь быть как нам хочется.
Вот тест (триангуляция из какого-то online триангулятора):
Какой тут, по вашему, кратчайший путь? Куда он тут перестроится?
Я утверждаю, что кратчайший путь проходит по коротким ребрам, где красные точки кучно идут и по одному почти горизонтальному ребру.
Или вот:
Опять же, путь пройдет по густо натыканным вершинам и сделает только одно длинное ребро между двумя краями. Но вы это ребро в граф не добавляете.
обводил по точкам.
Триангуляция правильная, то главное, что путь неверный. В этом тесте тоже - взять прямую линию вместо трех красных сегментов будет короче:
Там чуть-чуть подругому еще снизу от черной линии будет путь, чтобы вот те 2 точки взять - но оно длину пути почти не изменит, ибо там все точки почти на прямой лежат.
Да, это эпичный феил! На простых кейсах такого не наблюдалось, а вот когда точки как забор и легли улиткой.
Если интересно, то до таких тестов я додумался так: Посмотрел, какие ребра вы удаляете (те, которые через несколько треугольников проходят насквозь). Дальше прикинул как может выглядеть путь с таким ребром. А потом трюк в том, чтобы длинную колбасу из точек понатыкать там, где мы хотим, чтобы путь точно проходил. Если их достаточно плотно натыкать, то выгоднее будет идти по пути вдоль прямой из колбасы.
Иногда даже удивительно как выбираются рёбра
Коммивояжёр за полином*