1

问题：如何在旅行商问题中对所有城市子集 {1,2,...,n} 进行正确的迭代顺序？

在我的解决方案中，子集由位掩码（现在只是一个整数）表示。所有结果都存储在二维数组 C 中，其中第一维 S 类似于城市子集（即位掩码）。第 2 个维度 j，包含 S 中所有城市之间的旅行成本，其中 j 是结束城市。

每个子集都包含城市 0（起始城市），算法从设置最短路线开始：

C[{0}][0] = 0;

但是，要使该算法起作用，所有子集都应按子集大小的顺序进行迭代。

这是一个简单的代码片段，它以递增的值打印所有子集：

#include <cstdio>

const int n = 5; // number of cities
const int s = 1 << n; // number of subsets

void printb(int x)
{
    for (int i = n-1; i >= 0; i--) {
        printf("%d", (x >> i) & 1);
    }
}

int main()
{
    for (int i = 0; i < s; i++) {
        printb(i); printf("\n");
    }

    return 0;
}

我的目标是按子集大小（位数）的顺序枚举子集。

我正在使用的算法描述：算法、S. Dasgupta、CH Papadimitriou 和 UV Vazirani (p188)

4

1 回答 1

2

为了正确求解 TSP，您实际上不需要在遍历大小为 2 的子集之前遍历所有大小为 1 的子集。在遍历集合 X 之前，您只需要遍历给定集合 X 的所有子集。使用集合的标准编码按数字顺序进行迭代可以满足此属性。

于 2013-01-04T03:19:09.680 回答