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