c++ - 如何在 C++ 中使用动态实现 TSP

最近我问了一个 question on Stack Overflow 寻求帮助解决一个问题。这是一个旅行商问题，我有多达 40,000 个城市，但我只需要访问其中的 15 个。

有人指出我使用带有优先级队列的 Dijkstra 为我需要访问的 15 个城市制作连接矩阵，然后使用 DP 在该矩阵上执行 TSP。我之前只使用了 O(n^2) 的 Dijkstra。在试图弄清楚如何实现 Dijkstra 之后，我终于做到了(足以将 40,000 个城市的 240 秒优化到 0.6)。但现在我被困在 TSP 部分。

以下是我用于学习 TSP 的 Material :

Quora

GeeksForGeeks

我有点理解算法(但不完全)，但我在实现它时遇到了麻烦。在此之前，我已经对 dp[int] 或 dp[int][int] 数组进行了动态编程。但是现在当我的 dp 矩阵必须是 dp[subset][int] 时，我不知道该怎么做。

我的问题是:

如何使用动态规划处理子集？ (在 C++ 中的一个例子将不胜感激)

我链接的算法是否允许多次访问城市，如果不允许我应该更改什么？

我应该改用另一种 TSP 算法吗？ (我注意到有几种方法可以做到)。请记住，我必须得到确切的值，而不是近似值。

编辑:

经过更多研究，我偶然发现了斯坦福大学的一些竞争性编程竞赛讲座，并设法找到了 TSP here(幻灯片 26-30)。关键是将子集表示为位掩码。尽管如此，这仍然使我的其他问题没有得到解答。

是否可以对该算法进行任何更改以允许多次访问一个城市。如果可以做到，这些变化是什么？否则，我应该尝试什么？

最佳答案

我认为您可以使用动态解决方案并向每对节点添加具有最短路径的第二条边。另见这个问题: Variation of TSP which visits multiple cities 。