Вы не учли то условие, что прямой и обратный путь между двумя вершинами симметричной матрицы смежности считается одним ребром. А ребер для каждой вершины должно быть точно два.
Долго думал, как вам ответить. Сам я не на ангстрем не математик, скорее практик. Мне очень сложно играть на чужом научном поле. Попробую в двух словах пояснить почему решение точное.
Представление формулировки задачи коммивояжёра как задачи дискретной оптимизации позволяет всегда получать решение как набор циклов, минимум из трёх вершин, охватывающих все узлы графа. А решение решателем оптимизационной задачи однозначно гарантирует, что суммарная длина всех этих циклов будет минимальна для графа. Минимальное же значение суммы циклов запрещает графу перекручиваться. Такое поведение не означает, что минимальное решение будет единственным, но нас по большому счёту устоит любое из минимальных если их несколько. Создавая дополнительные ограничения, мы запрещаем графу распадаться на уже обнаруженные множества, циклы которых в сумме короче минимального Гамильтонова пути. Повторяя поиск и добавляя дополнительные ограничения мы рано или поздно приходим к оптимальному решению задачи.
Возможно кто-то из молодого поколения возьмёт данную работу как курсовой/дипломный проект и всё хорошо разложит по полочкам.
Вопрос очень актуальный, тоже ищу на него ответ, при миллионе переменных (а там используется переменные типа double), матрица перестаёт влезать в оперативную память. Нужен какой-то солвер который умеет расчёты или по частям, или эффективной подгрузкой с HDD, или эффективно сжимать данные. Разряженный матрицы SciPy проявили себя не очень.
Признаю код не самый простой, есть грешок. Самые сложные места постарался прокомментировать по ходу. Вложенные циклы можно спокойно развернуть и добавить точки отладчика чтобы посмотреть сложные места. Непонятные переменные только для циклов, для краткости, не люблю, знаете, длинные строки.
Если есть конкретные вопросы спрашивайте отвечу. Так долго варился в этом коде что не могу критически оценить его сложность.
Попробовал, множества всё равно связываются хоть и одной связью. За счёт повторов связывания, рано или поздно стягивает всю конструкцию в монолит. Но получается медленнее чем с двумя связями.
Только если вы расскажете, как это прочитать. В архиве что угодно, но только не симметричная матрица смежности.
По поводу дискуссии на форуме, как мне показалось, там речь шла про точность самой вводимой матрицы.
В тексте статьи был обозначен худший случай, требующий (n/2+1) вызовов решателя. В своих изысканиях специально искал примеры, которые являются адом для решателя, но и там он справлялся не плохо. Хоть и нелегко, но вдвое бил динамическое программирование по размеру матрицы. Если у динамического программирования сложность O(n^2*2^n), то тут я предполагаю она упирается в худшем случае в O(n*2^n) но это прикидочная величина.
Благодарю вас за наводку на солвер Concorde, он лучший. Однако после ознакомления с их описание задачи у меня сложилось чёткое убеждение, что они не используют именно целочисленное линейное программирование, скорее там обычное линейное программирование. А так же я не увидел именно точного решения. Возможно, вы мне поможете с этим разобраться?
Всё так, но ведь и операции могут быть разными. Например, монтажный пистолет работает достаточно шустро, прозвонка дорожек мультиметром то же весьма скоростная операция. К сожалению, не владею реальными кейсами.
Тут я не совсем корректно выразился. Выше названные исследователи, конечно же, перебирали комбинации. Если выразить эти комбинации в виде линейных неравенств и отдать их целочисленному решателю, то будет слишком много уравнений.
О! Я так рад, что вы заинтересовались и начали копать. Вы абсолютно правы, за основу была выбрана именно эта формулировка. Но если посмотреть работы Данцига, Фалкерсона и Джонсона, а так же Миллера, Такера и Землина (ссылки на эти работы есть там же в википедии), то можно прийти к следующему выводу:
Эти авторы пытались засунуть все ограничения в систему уравнений сразу, а так их получается очень много и решатель захлёбывается. Я же предлагаю добавлять только те ограничения, которые нужны по факту в конкретной задаче.
Надеюсь так яснее. Я думал код приведённый выше сам за себя скажет.
Понимаете коллега, где вы тут увидели дискретную оптимизацию? В ней я разочаровался еще, когда делал ветви и границы. Как раз линейное целочисленное программирование, основанное на симплекс методе и алгоритме Гомори, как раз и даёт эти чудесные результаты.
КДПВ для статьи сформирована SciPy и для неё потребовалось 280875 переменных, нормально справился. Обратите внимание, что в последних версиях scipy.optimize.linprog завезли классные быстрые решатели. Особенно меня порадовал метод глубинной точки, для нецелочисленных задач.
Очень не хватает формального описания подхода для понимания сути происходящего.
Теоретическое обоснование разжевано десятилетия назад. Читать не математику это будет не интересно, а тот к то в теме поймёт опираясь на свой опыт работы с TSP.
Всё что я сделал, это применил новый подход к выбору ограничивающих условий.
А если не использовать углы близкие к 180 градусам? Для своей работы использую триангуляцию Делоне, как понимаю она позволяет избегать острые углы.
Вы не учли то условие, что прямой и обратный путь между двумя вершинами симметричной матрицы смежности считается одним ребром. А ребер для каждой вершины должно быть точно два.
Долго думал, как вам ответить. Сам я не на ангстрем не математик, скорее практик. Мне очень сложно играть на чужом научном поле. Попробую в двух словах пояснить почему решение точное.
Представление формулировки задачи коммивояжёра как задачи дискретной оптимизации позволяет всегда получать решение как набор циклов, минимум из трёх вершин, охватывающих все узлы графа. А решение решателем оптимизационной задачи однозначно гарантирует, что суммарная длина всех этих циклов будет минимальна для графа. Минимальное же значение суммы циклов запрещает графу перекручиваться. Такое поведение не означает, что минимальное решение будет единственным, но нас по большому счёту устоит любое из минимальных если их несколько. Создавая дополнительные ограничения, мы запрещаем графу распадаться на уже обнаруженные множества, циклы которых в сумме короче минимального Гамильтонова пути. Повторяя поиск и добавляя дополнительные ограничения мы рано или поздно приходим к оптимальному решению задачи.
Возможно кто-то из молодого поколения возьмёт данную работу как курсовой/дипломный проект и всё хорошо разложит по полочкам.
Вопрос очень актуальный, тоже ищу на него ответ, при миллионе переменных (а там используется переменные типа double), матрица перестаёт влезать в оперативную память. Нужен какой-то солвер который умеет расчёты или по частям, или эффективной подгрузкой с HDD, или эффективно сжимать данные. Разряженный матрицы SciPy проявили себя не очень.
Признаю код не самый простой, есть грешок. Самые сложные места постарался прокомментировать по ходу. Вложенные циклы можно спокойно развернуть и добавить точки отладчика чтобы посмотреть сложные места. Непонятные переменные только для циклов, для краткости, не люблю, знаете, длинные строки.
Если есть конкретные вопросы спрашивайте отвечу. Так долго варился в этом коде что не могу критически оценить его сложность.
Стандартный решатель OR-Tools, меня совсем не порадовал, по скорости он на последнем месте.
Попробовал, множества всё равно связываются хоть и одной связью. За счёт повторов связывания, рано или поздно стягивает всю конструкцию в монолит. Но получается медленнее чем с двумя связями.
Решение всё равно найдётся но, большим числом неравенств
Только если вы расскажете, как это прочитать. В архиве что угодно, но только не симметричная матрица смежности.
По поводу дискуссии на форуме, как мне показалось, там речь шла про точность самой вводимой матрицы.
В тексте статьи был обозначен худший случай, требующий (n/2+1) вызовов решателя. В своих изысканиях специально искал примеры, которые являются адом для решателя, но и там он справлялся не плохо. Хоть и нелегко, но вдвое бил динамическое программирование по размеру матрицы. Если у динамического программирования сложность O(n^2*2^n), то тут я предполагаю она упирается в худшем случае в O(n*2^n) но это прикидочная величина.
Благодарю вас за наводку на солвер Concorde, он лучший. Однако после ознакомления с их описание задачи у меня сложилось чёткое убеждение, что они не используют именно целочисленное линейное программирование, скорее там обычное линейное программирование. А так же я не увидел именно точного решения. Возможно, вы мне поможете с этим разобраться?
Да не, мы тут все люди простые, вот автор статьи обычный разраб. Просто у него хобби искать решения не решаемых задач.
Всё так, но ведь и операции могут быть разными. Например, монтажный пистолет работает достаточно шустро, прозвонка дорожек мультиметром то же весьма скоростная операция. К сожалению, не владею реальными кейсами.
Тут я не совсем корректно выразился. Выше названные исследователи, конечно же, перебирали комбинации. Если выразить эти комбинации в виде линейных неравенств и отдать их целочисленному решателю, то будет слишком много уравнений.
О! Я так рад, что вы заинтересовались и начали копать. Вы абсолютно правы, за основу была выбрана именно эта формулировка. Но если посмотреть работы Данцига, Фалкерсона и Джонсона, а так же Миллера, Такера и Землина (ссылки на эти работы есть там же в википедии), то можно прийти к следующему выводу:
Эти авторы пытались засунуть все ограничения в систему уравнений сразу, а так их получается очень много и решатель захлёбывается. Я же предлагаю добавлять только те ограничения, которые нужны по факту в конкретной задаче.
Надеюсь так яснее. Я думал код приведённый выше сам за себя скажет.
Понимаете коллега, где вы тут увидели дискретную оптимизацию? В ней я разочаровался еще, когда делал ветви и границы. Как раз линейное целочисленное программирование, основанное на симплекс методе и алгоритме Гомори, как раз и даёт эти чудесные результаты.
КДПВ для статьи сформирована SciPy и для неё потребовалось 280875 переменных, нормально справился. Обратите внимание, что в последних версиях scipy.optimize.linprog завезли классные быстрые решатели. Особенно меня порадовал метод глубинной точки, для нецелочисленных задач.
Теоретическое обоснование разжевано десятилетия назад. Читать не математику это будет не интересно, а тот к то в теме поймёт опираясь на свой опыт работы с TSP.
Всё что я сделал, это применил новый подход к выбору ограничивающих условий.
GLPK у меня не захотел решать целочисленную задачу, пришлось забраковать.
А какой решатель встроен OR-Tools, по умолчанию?
Почитал подробнее, это прорывной метод для огромных матриц с заранее известной метрикой пространства, я в восхищении!
Забавно, что в нём так же используется алгоритм ветвления и границ, для выбора лучшего решения.
Ну почему же, выскажитесь, с каким тезисом вы не согласны?