c++ - 旅行商的递归动态规划方法

Question

我希望有人能解释这个页面上的代码是如何工作的：TSP-Recursive

伪代码难以解释，动态编程方法使其特别难以理解。为什么需要移位？如何推广这种方法（例如，给定位置坐标，我们能否采用这种方法来解决该问题）？

Answer 1

该变量graph是一个映射（在数学意义上）。给定两个城市，A 和 B，graph[A][B]是从 A 到 B 的距离。

变量dp是另一个映射。给定一组城市 S和一个城市 A，是访问S中每个城市并在 A 结束dp[S][A]的最短旅程。

一旦graph填写完毕并选择了最终城市，该函数init将填写 中的一些距离dp：对于每个城市 A，从 A 开始并仅访问 B 的最短路程显然只是graph[A][B]。

该函数给出了访问STSP( S, X )中的每个城市并在 X 结束的最短旅程的长度。如果该距离已在 中列出，则返回该距离。否则，对于 S 中的每个城市 A ，计算访问S中的每个其他城市的最短旅程的长度，然后是 A，然后是 X。其中最短的是答案，因此该函数将其记录并返回它。dpdp

Answer 2

位移是因为代码使用 int 来表示一个集合，特别是访问城市的集合。如果您有 32 位整数，则一个 int 可以表示一组最多 32 个项目。

基本操作是

// add n to set
set |= 1 << n;

// remove n from set
set &= ~(1 << n);

// test set for n
if ((set&(1 << n)) != 0)
    ...