1

我想用 C 实现旅行商问题（动态编程）。我有以下伪代码：

** Ignoring the base cases**
** C[i][j] is cost of the edge from i to j**
for m = 2,3,4..n:
    for each set S of size m which is subset of {1,2,3...n}:
        for each J in S, j ≠ 1:
            A[S][j] = min  of { A[S-{j}][k] + C[k][j] } for all k is in S and k ≠ j: 

 return min of { A[{1,2,3...n},j] + C[j][1] } for all j from 2 to n

A[S][j] 存储从 1 到 j 的最短路径，该路径恰好访问 S 中的所有顶点一次。（S 包括 1 和 j）。

时间复杂度为 O(n 2 2 n )。

我的问题是，在这个伪代码中，他们使用集合作为数组索引，时间复杂度表明查找没有元素 j ( S - {j}) 的集合需要恒定时间。

我想到的是使用由 m、i 和 j 索引的 3D 数组。其中“i”指向存储在由 m,i 索引的不同集合数组中的集合。

但问题是我无法A[S-{j}[k]]在恒定时间内进行查找。

我的问题是，如何在不改变原始算法的时间复杂度的情况下实现由“集合”索引的数组。

4

1 回答 1

3

让每条路径由一个二进制字符串表示，其中每个位表示是否访问了一个城市。

所以

(123456)
 011001

表示访问了城市 2、3 和 6。

您将上述内容用作数组索引。

当您想查找没有城市的路径时，只需将该位设置为 0 并将输出用作索引。

第一个城市总是会被访问，所以你真的不需要那个城市。

于 2013-02-22T07:15:49.007 回答