Алгоритм ДП, что я рассматривал, очень неэффективен по сравнению с тем, что предоставили Вы.
Беру свои слова назад, в такой реализации ДП на многих наборах обходит мою версию ЛП.
Любопытно, на некоторых наборах сильно лидирует ЛП, но если проигрывает, то часто значительно, тогда как ДП более стабилен. Как вариант интересно устраивать гонку алгоритмов, какой финиширует первым.
Однако меня огорчил тот факт, что на больших наборах входных данных, памяти ДП всё же не хватает, и он не выполняется с ошибкой:
MemoryError: Unable to allocate 14.2 GiB for an array with shape (15207959671,) and data type bool.
И ещё проблема, что решение должно быть точным, а любая микро-погрешность не найдёт решение Xi in {0,1}, посчитается какой-нибудь Xi=0.99999 и всё, вариант отсечётся. То есть, я думаю, тщательное тестирование на очень сложных случаях покажет, что этот метод не всегда даёт правильный результат.
Это зависит от качества решателя. Если под капотом используются float64, так и бывает у большинства решателей.
Однако, как я считаю хороший решатель должен работать с натуральными дробями, и тогда погрешность не возникает совсем.
ДП больше пары десятков элементов у меня не тянет. Тот алгоритм что я использовал сжирает всю память для кэша.
Возможно алгоритм что не хранит всё кэше и вывезет. Но если предположить, что по скорости алгоритм с меморизацией и без равны, то навряд ли сравняется с ЛП.
Выигрыш есть, именно для этого пост и писался. Только что бы это показать нужно смотреть на практике. Выигрыш очень велик, когда количество чисел превалирует над размером.
Динамическое программирование требует очень много память на больших N и P. Линейное в этом смысле сильно выигрывает, но у него плохо со стабильностью результатов, уже больно оно зависит от набора входных данных. На некоторых наборах выигрыш феноменален, не некоторых экспонента всё портит. Но по моим наблюдениям в среднем разы рвёт ДП.
На случайных наборах результат очень хороший, особенно когда допустимых решений много.
Если вы приложите набор тестовых данных, то могу протестировать.
То, что задача NP - полна коллега вроде и не оспаривал. Видимо он хотел указать, что сложность задачи зависит не только от числа элементов (N), но и от точности (P) и это не имеет отношение к NP-полноте. Я не верно понял?
В том то и дело, что такое поведение как вы нарисовали, невозможно. Как только вы приводите алгоритм к граничному состоянию, весь маршрут перестраивается полностью. Ещё в прошлой статье с окружностями подметил эту тенденцию, но там подход был не совсем верным. Я очень долго моделировал общее решение, в том числе и с триангуляциями. И только триангуляция Делоне даёт нужный результат. С остовыми деревьями такого эффекта нет.
Конечно, мне повезло, только не в том смысле, что решение случайное. В статье про ветви и границе, лично Вы, предлагали мне поискать эвристику через эвклидово расстояние. И вот, спустя год, я предлагаю вам решение, код для проверки, а вы ещё требуете доказательства.
Моё понимание математики находится не на том уровне, чтобы вывести доказательство в виде формул. Однако, определённые основания утверждать, что граф содержит точное решение у меня есть. Хотелось бы получить контрпример со стороны сообщества или хотя бы выкладку, почему я не прав.
В работе описаны два алгоритма, первый для плоскости он быстрее, второй для общей задачи коммивояжера (в том числе для молекулярной структуры), он медленнее, но так же решается точно.
Это как если у вас был бы спортивный автомобиль для ровных дорог, и кроссовер для бездорожья.
Нет, тут всё проще. 39800 переменных – это и есть n^2-n, от 200 вершин.
Изначально решается матрица 39800 x 400. На следующих шагах, она станет немного больше по высоте, но не так уж сильно (в 2-4 раза). Шагов за 15-30 (в худшем случае n/2) алгоритм находит решение такого размера. Так что всё не как уж и печально. Кроме того солверы обычно наделяют различными методами, ускоряющими решения.
Размерность многомерного пространства и правда будет очень высокой. Пример: для направленного графа на 200 вершин = 39800 мерное пространство. Но это уже сложность решателя линейных уравнений, его для этого и делают.
Не утверждаю, что решение с ЦЛП - серебряная пуля.
Возможно, решение находится не всегда быстро, но по памяти более гуманно факт.
Алгоритм ДП, что я рассматривал, очень неэффективен по сравнению с тем, что предоставили Вы.
Беру свои слова назад, в такой реализации ДП на многих наборах обходит мою версию ЛП.
Любопытно, на некоторых наборах сильно лидирует ЛП, но если проигрывает, то часто значительно, тогда как ДП более стабилен. Как вариант интересно устраивать гонку алгоритмов, какой финиширует первым.
Однако меня огорчил тот факт, что на больших наборах входных данных, памяти ДП всё же не хватает, и он не выполняется с ошибкой:
MemoryError: Unable to allocate 14.2 GiB for an array with shape (15207959671,) and data type bool.
Это зависит от качества решателя. Если под капотом используются float64, так и бывает у большинства решателей.
Однако, как я считаю хороший решатель должен работать с натуральными дробями, и тогда погрешность не возникает совсем.
ДП больше пары десятков элементов у меня не тянет. Тот алгоритм что я использовал сжирает всю память для кэша.
Возможно алгоритм что не хранит всё кэше и вывезет. Но если предположить, что по скорости алгоритм с меморизацией и без равны, то навряд ли сравняется с ЛП.
Выигрыш есть, именно для этого пост и писался. Только что бы это показать нужно смотреть на практике. Выигрыш очень велик, когда количество чисел превалирует над размером.
Динамическое программирование требует очень много память на больших N и P. Линейное в этом смысле сильно выигрывает, но у него плохо со стабильностью результатов, уже больно оно зависит от набора входных данных. На некоторых наборах выигрыш феноменален, не некоторых экспонента всё портит. Но по моим наблюдениям в среднем разы рвёт ДП.
На случайных наборах результат очень хороший, особенно когда допустимых решений много.
Если вы приложите набор тестовых данных, то могу протестировать.
То, что задача NP - полна коллега вроде и не оспаривал. Видимо он хотел указать, что сложность задачи зависит не только от числа элементов (N), но и от точности (P) и это не имеет отношение к NP-полноте. Я не верно понял?
Вы правы. Мне не хотелось излишне усложнять текст.
Так как для чисел порядка миллиарда, число двоичных разрядов практически не имеет значения, то я несколько упростил повествование.
Скорее забэкапить крайний дамп... в облако?
Да, это эпичный феил! На простых кейсах такого не наблюдалось, а вот когда точки как забор и легли улиткой.
Спасибо! Осознал, признаю ошибку! Вам + в карму, буду думать. Хорошие кейсы.
обводил по точкам.
Иногда даже удивительно как выбираются рёбра
В том то и дело, что такое поведение как вы нарисовали, невозможно. Как только вы приводите алгоритм к граничному состоянию, весь маршрут перестраивается полностью. Ещё в прошлой статье с окружностями подметил эту тенденцию, но там подход был не совсем верным. Я очень долго моделировал общее решение, в том числе и с триангуляциями. И только триангуляция Делоне даёт нужный результат. С остовыми деревьями такого эффекта нет.
Конечно, мне повезло, только не в том смысле, что решение случайное. В статье про ветви и границе, лично Вы, предлагали мне поискать эвристику через эвклидово расстояние. И вот, спустя год, я предлагаю вам решение, код для проверки, а вы ещё требуете доказательства.
Моё понимание математики находится не на том уровне, чтобы вывести доказательство в виде формул. Однако, определённые основания утверждать, что граф содержит точное решение у меня есть. Хотелось бы получить контрпример со стороны сообщества или хотя бы выкладку, почему я не прав.
В работе описаны два алгоритма, первый для плоскости он быстрее, второй для общей задачи коммивояжера (в том числе для молекулярной структуры), он медленнее, но так же решается точно.
Это как если у вас был бы спортивный автомобиль для ровных дорог, и кроссовер для бездорожья.
Звучит как вызов. Теоретически наверно можно замахнуться на n = 6, но это уже на грани.
Нет, тут всё проще. 39800 переменных – это и есть n^2-n, от 200 вершин.
Изначально решается матрица 39800 x 400. На следующих шагах, она станет немного больше по высоте, но не так уж сильно (в 2-4 раза). Шагов за 15-30 (в худшем случае n/2) алгоритм находит решение такого размера. Так что всё не как уж и печально. Кроме того солверы обычно наделяют различными методами, ускоряющими решения.
Размерность многомерного пространства и правда будет очень высокой. Пример: для направленного графа на 200 вершин = 39800 мерное пространство. Но это уже сложность решателя линейных уравнений, его для этого и делают.