Алгоритм — Как реализовать TSP с динамикой в переполнении стека
Недавно я спросил вопрос по переполнению стека просить помощи, чтобы решить проблему. Это проблема коммивояжера, когда у меня до 40 000 городов, но мне нужно посетить только 15 из них.
Мне было предложено использовать Dijkstra с очередью приоритетов, чтобы создать матрицу соединений для 15 городов, которые мне нужно посетить, а затем провести TSP на этой матрице с DP. Ранее я использовал только Дейкстру с O (n ^ 2). После попытки выяснить, как реализовать Dijkstra, я наконец-то это сделал (этого достаточно для оптимизации с 240 секунд до 0,6 для 40 000 городов). Но теперь я застрял в части TSP.
Вот материалы, которые я использовал для изучения TSP:
Я вроде понимаю алгоритм (но не полностью), но у меня возникают проблемы с его реализацией. До этого я занимался динамическим программированием с массивами, которые были бы dp [int] или dp [int] [int]. Но теперь, когда моя матрица dp должна быть dp [subset] [int], я понятия не имею, как мне это сделать.
Мои вопросы:
Как мне обрабатывать подмножества с помощью динамического программирования? (пример в C ++ был бы оценен)- Могут ли алгоритмы, которые я привел, разрешить посещение городов более одного раза, а если нет, что мне следует изменить?
- Должен ли я использовать другой алгоритм TSP вместо этого? (Я заметил, что есть несколько способов сделать это). Имейте в виду, что я должен получить точное значение, а не приблизительное.
Редактировать:
После еще одного исследования я наткнулся на несколько конкурсных лекций по программированию в Стэнфорде и смог найти TSP Вот (слайды 26-30). Ключ должен представлять подмножество как битовую маску. Это все еще оставляет мои другие вопросы без ответа, хотя.
Можно ли внести какие-либо изменения в этот алгоритм, чтобы разрешить посещение города более одного раза. Если это можно сделать, каковы эти изменения? В противном случае, что я должен попробовать?
Решение
Я думаю, что вы можете использовать динамическое решение и добавить к каждой паре узлов второе ребро с кратчайшим путем. Смотрите также этот вопрос:Вариация TSP, которая посещает несколько городов.
Другие решения
Вот ТСП реализация, Вы найдете ссылку на реализованную проблему в посте.
Алгоритмы, которые вы связали, не позволяют посещать города более одного раза.
На ваш третий вопрос, я думаю, Phpdna ответ был хорошим.
Можно ли посетить города более одного раза? И да и нет. На первом этапе вы сводите проблему к 15 соответствующим городам. В результате получается полный граф, то есть тот, где каждый узел связан с каждым другим узлом. Связь между двумя такими узлами может включать несколько городов на исходной карте, включая некоторые из соответствующих, но это не должно относиться к вашему алгоритму на втором шаге.
Независимо от того, использовать ли другой алгоритм, я бы, возможно, сделал поиск в глубину по графику. Используя минимальное связующее дерево, вы можете задать верхнюю и нижнюю границу для оставшихся городов и использовать ее для выбора многообещающих решений и отказа от безнадежных (иначе говоря, обрезка). Была также куча исследований по этой теме, просто поиск в Интернете. Например, в случаях, когда карта на самом деле является картезианской (т. Е. Путевые расходы — это расстояние между двумя точками на плоскости), вы можете использовать эту информацию, чтобы немного улучшить алгоритмы.
Наконец, если вы действительно намереваетесь увеличить количество посещаемых городов, вы обнаружите, что время для его вычисления значительно увеличивается, поэтому вам придется отказаться от вашего требования для точного решения.