То, что задача NP - полна коллега вроде и не оспаривал. Видимо он хотел указать, что сложность задачи зависит не только от числа элементов (N), но и от точности (P) и это не имеет отношение к NP-полноте. Я не верно понял?
В том то и дело, что такое поведение как вы нарисовали, невозможно. Как только вы приводите алгоритм к граничному состоянию, весь маршрут перестраивается полностью. Ещё в прошлой статье с окружностями подметил эту тенденцию, но там подход был не совсем верным. Я очень долго моделировал общее решение, в том числе и с триангуляциями. И только триангуляция Делоне даёт нужный результат. С остовыми деревьями такого эффекта нет.
Конечно, мне повезло, только не в том смысле, что решение случайное. В статье про ветви и границе, лично Вы, предлагали мне поискать эвристику через эвклидово расстояние. И вот, спустя год, я предлагаю вам решение, код для проверки, а вы ещё требуете доказательства.
Моё понимание математики находится не на том уровне, чтобы вывести доказательство в виде формул. Однако, определённые основания утверждать, что граф содержит точное решение у меня есть. Хотелось бы получить контрпример со стороны сообщества или хотя бы выкладку, почему я не прав.
В работе описаны два алгоритма, первый для плоскости он быстрее, второй для общей задачи коммивояжера (в том числе для молекулярной структуры), он медленнее, но так же решается точно.
Это как если у вас был бы спортивный автомобиль для ровных дорог, и кроссовер для бездорожья.
Нет, тут всё проще. 39800 переменных – это и есть n^2-n, от 200 вершин.
Изначально решается матрица 39800 x 400. На следующих шагах, она станет немного больше по высоте, но не так уж сильно (в 2-4 раза). Шагов за 15-30 (в худшем случае n/2) алгоритм находит решение такого размера. Так что всё не как уж и печально. Кроме того солверы обычно наделяют различными методами, ускоряющими решения.
Размерность многомерного пространства и правда будет очень высокой. Пример: для направленного графа на 200 вершин = 39800 мерное пространство. Но это уже сложность решателя линейных уравнений, его для этого и делают.
Тут вся загвоздка как раз в том, что у многих читающих нет понимания, как работает линейное программирование. У меня самого ушло много времени на то, что осознать, как это функционирует. В статье через метафору мяча попробовал донести, но видимо неудачно.
Не может быть ни каких ‘забрести в вершину’, мы не перебираем комбинации. Работаем только с множествами, и соединяем множества, через линейные уравнения. В данном случае множества это найденные циклы в графе.
Спасибо! С удовольствием читал ваши статьи, многое почерпнул для себя.
Возможно, мне не пока не достаёт лоска в изложении своих идей, но от этого они не становятся хуже. Придерживаюсь того, что человек, которому интересна освещённая тема обязательно проверит код на практике.
Соревноваться с эвристическими методами бессмысленно, тут вы правы.
Евклидова задача коммивояжера только частный случай общей задачи, который возможно решать значительно быстрее. На мой взгляд, глупо отказываться от возможности получить преимущество, в конкретной области применения.
И да, целочисленное линейное программирование по схеме в статье, переваривает точно дорожные графы на сотню – другую вершин.
Это же и значит - вы рассматриваете графы которые можно расположить на плоскости, где "длина ребра = эвклидова метрика"? Так?
Да это правда, но не вся.
У меня сложилось впечатление, что вы невнимательно прочитали статью.
Для Эвклидовой плоскости, да, используется эвристика с триангуляцией Делоне. А для задач, что вы перечислили, используется другой алгоритм – ассиметричный. Вот уже этот алгоритм стравляется со всеми задачами, он так же описан в статье, хотя сильно медленнее.
Для симметричной задачи граф задаётся набором точек на плоскости, мы не задаём матрицу смежности. Затем для этих точек мы и строим триангуляцию Делоне. Расстояния рассчитывается только для нужных рёбер через Евклидову норму.
Вы можете не использовать предложенную мной эвристику и задать полносвязаную матрицу смежности, алгоритм съест и так, но выигрыша в скорости будет мало.
Не совсем так, задача коммивояжера в общем виде остаётся NP-сложной, я это не оспариваю. Но в практических задачах с линейным программированием, нужно очень сильно постараться, чтобы заставить решатель уйти в экспоненту. И это не зависит от того, определена на плоскости она или нет. Это примерно, как свести QSort к O(n^2), а разбивая задачу на подзадачи мы очень сильно снижаем эту вероятность в целом.
Однако и полином полиному рознь. Мы за счёт дополнительных ухищрений значительно уменьшаем сложность задачи. Но если для Эвклидовой плоскости мне встречался алгоритм и с лучшей скоростью работы, то вот за асимметричную задачу такого сказать не могу.
Звёздочка как раз и говорит, что бывают исключения.
То, что задача NP - полна коллега вроде и не оспаривал. Видимо он хотел указать, что сложность задачи зависит не только от числа элементов (N), но и от точности (P) и это не имеет отношение к NP-полноте. Я не верно понял?
Вы правы. Мне не хотелось излишне усложнять текст.
Так как для чисел порядка миллиарда, число двоичных разрядов практически не имеет значения, то я несколько упростил повествование.
Скорее забэкапить крайний дамп... в облако?
Да, это эпичный феил! На простых кейсах такого не наблюдалось, а вот когда точки как забор и легли улиткой.
Спасибо! Осознал, признаю ошибку! Вам + в карму, буду думать. Хорошие кейсы.
обводил по точкам.
Иногда даже удивительно как выбираются рёбра
В том то и дело, что такое поведение как вы нарисовали, невозможно. Как только вы приводите алгоритм к граничному состоянию, весь маршрут перестраивается полностью. Ещё в прошлой статье с окружностями подметил эту тенденцию, но там подход был не совсем верным. Я очень долго моделировал общее решение, в том числе и с триангуляциями. И только триангуляция Делоне даёт нужный результат. С остовыми деревьями такого эффекта нет.
Конечно, мне повезло, только не в том смысле, что решение случайное. В статье про ветви и границе, лично Вы, предлагали мне поискать эвристику через эвклидово расстояние. И вот, спустя год, я предлагаю вам решение, код для проверки, а вы ещё требуете доказательства.
Моё понимание математики находится не на том уровне, чтобы вывести доказательство в виде формул. Однако, определённые основания утверждать, что граф содержит точное решение у меня есть. Хотелось бы получить контрпример со стороны сообщества или хотя бы выкладку, почему я не прав.
В работе описаны два алгоритма, первый для плоскости он быстрее, второй для общей задачи коммивояжера (в том числе для молекулярной структуры), он медленнее, но так же решается точно.
Это как если у вас был бы спортивный автомобиль для ровных дорог, и кроссовер для бездорожья.
Звучит как вызов. Теоретически наверно можно замахнуться на n = 6, но это уже на грани.
Нет, тут всё проще. 39800 переменных – это и есть n^2-n, от 200 вершин.
Изначально решается матрица 39800 x 400. На следующих шагах, она станет немного больше по высоте, но не так уж сильно (в 2-4 раза). Шагов за 15-30 (в худшем случае n/2) алгоритм находит решение такого размера. Так что всё не как уж и печально. Кроме того солверы обычно наделяют различными методами, ускоряющими решения.
Размерность многомерного пространства и правда будет очень высокой. Пример: для направленного графа на 200 вершин = 39800 мерное пространство. Но это уже сложность решателя линейных уравнений, его для этого и делают.
Тут вся загвоздка как раз в том, что у многих читающих нет понимания, как работает линейное программирование. У меня самого ушло много времени на то, что осознать, как это функционирует. В статье через метафору мяча попробовал донести, но видимо неудачно.
Не может быть ни каких ‘забрести в вершину’, мы не перебираем комбинации. Работаем только с множествами, и соединяем множества, через линейные уравнения. В данном случае множества это найденные циклы в графе.
Спасибо! С удовольствием читал ваши статьи, многое почерпнул для себя.
Возможно, мне не пока не достаёт лоска в изложении своих идей, но от этого они не становятся хуже. Придерживаюсь того, что человек, которому интересна освещённая тема обязательно проверит код на практике.
Соревноваться с эвристическими методами бессмысленно, тут вы правы.
Евклидова задача коммивояжера только частный случай общей задачи, который возможно решать значительно быстрее. На мой взгляд, глупо отказываться от возможности получить преимущество, в конкретной области применения.
И да, целочисленное линейное программирование по схеме в статье, переваривает точно дорожные графы на сотню – другую вершин.
Да это правда, но не вся.
У меня сложилось впечатление, что вы невнимательно прочитали статью.
Для Эвклидовой плоскости, да, используется эвристика с триангуляцией Делоне. А для задач, что вы перечислили, используется другой алгоритм – ассиметричный. Вот уже этот алгоритм стравляется со всеми задачами, он так же описан в статье, хотя сильно медленнее.
Для симметричной задачи граф задаётся набором точек на плоскости, мы не задаём матрицу смежности. Затем для этих точек мы и строим триангуляцию Делоне. Расстояния рассчитывается только для нужных рёбер через Евклидову норму.
Вы можете не использовать предложенную мной эвристику и задать полносвязаную матрицу смежности, алгоритм съест и так, но выигрыша в скорости будет мало.
Не совсем так, задача коммивояжера в общем виде остаётся NP-сложной, я это не оспариваю. Но в практических задачах с линейным программированием, нужно очень сильно постараться, чтобы заставить решатель уйти в экспоненту. И это не зависит от того, определена на плоскости она или нет. Это примерно, как свести QSort к O(n^2), а разбивая задачу на подзадачи мы очень сильно снижаем эту вероятность в целом.
Однако и полином полиному рознь. Мы за счёт дополнительных ухищрений значительно уменьшаем сложность задачи. Но если для Эвклидовой плоскости мне встречался алгоритм и с лучшей скоростью работы, то вот за асимметричную задачу такого сказать не могу.
Звёздочка как раз и говорит, что бывают исключения.