最近我问了一个question on Stack Overflow寻求帮助以解决问题。这是一个旅行商问题，我有多达 40,000 个城市，但我只需要访问其中的 15 个。
有人指出我使用带有优先级队列的 Dijkstra 为我需要访问的 15 个城市制作连接矩阵，然后使用 DP 在该矩阵上执行 TSP。我以前只使用 O(n^2) 的 Dijkstra。在尝试弄清楚如何实现 Dijkstra 之后，我终于做到了(足以将 40,000 个城市从 240 秒优化到 0.6)。但现在我卡在了 TSP 部分。
以下是我学习TSP时使用的资料:
我有点理解该算法(但不完全理解)，但我在实现它时遇到了麻烦。在此之前，我已经使用 dp[int] 或 dp[int][int] 数组进行了动态编程。但是现在当我的 dp 矩阵必须是 dp[subset][int] 时，我不知道该怎么做。
我的问题是:
如何使用动态规划处理子集？ (C++ 中的示例将不胜感激)- 我链接的算法是否允许多次访问城市？如果不允许，我应该更改什么？
- 我是否应该改用另一种 TSP 算法？ (我注意到有几种方法可以做到)。请记住，我必须获得准确的值，而不是近似值。
编辑:
经过更多研究后，我偶然发现了斯坦福大学的一些竞争性编程竞赛讲座，并设法找到了 TSP here (幻灯片 26-30)。关键是将子集表示为位掩码。不过，这仍然没有回答我的其他问题。
是否可以对该算法进行任何更改以允许多次访问一个城市。如果可以做到，那些变化是什么？否则，我应该尝试什么？
最佳答案
我认为您可以使用动态解决方案并向每对节点添加具有最短路径的第二条边。另见这个问题:Variation of TSP which visits multiple cities .
关于c++ - 如何在C++中动态实现TSP，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/24252964/