这次作业题要求实现25个点的TSP问题
TSP的非递归动规解法本身就有一定的难度，但本题的重点却是内存优化，因为25点的 TSP 动规解法需要的内存较多
为了优化空间复杂度，这里引入了两个技巧：
2. Combinadic
首先，还是要清楚了解TSP解法的状态转移方程，这里对状态转移方程做了详细的介绍，且带有伪代码
1. 我们用二进制来表示集合 S ,比如5个点的TSP问题，00111 表示集合S中有第1,2,3个点，00111 就表示大小为 3 的一个集合。
2. 从伪代码中，可以看出，我们需要枚举大小为 n 的集合 S,然后计算 C(S,k)
Gosper’s hack 能够以 o(1) 的时间计算出大小为 n 的下一个集合S，比如从 00111 -> 01011。
3. 对于 C(S,k)，假如使用二进制来表示集合S，我们需要的空间是 int dp[x][y], 其中 x 为2^25, y 为 25，每一个int类型还需要4字节的空间，需要的总空间超过1G，这太高了
因此，我们需要引入另一种保存状态的机制：Combinatorial number system
用一个例子来说明组合数系统：假设对于5个点的TSP问题，我们要描述大小为 3 的所有集合(比如，00111)，用朴素的二进制表示方法总是需要(2^5)的空间，但组合数系统用index来描述集合，如下表：
Index 表示的集合
0 {0, 1, 2} 1 {0, 1, 3} 2 {0, 1, 4} 3 {0, 2, 3} 4 {0, 2, 4} 5 {0, 3, 4} 6 {1, 2, 3} 7 {1, 2, 4} 8 {1, 3, 4} 9 {2, 3, 4}
从上面的表中可以看出，我们仅需要 10 个数就能表示所有的集合，这样，对于5个点的TSP问题用 （2^4）即可完成大小为3的所有集合的标注。
那么，对于大小为 25 的TSP问题，我们可以节省多少空间呢？
朴素二进制表示方法 (2^25)*25*4，这个上面已经计算过了，大于1G
压缩后的方法 (c(25,13))*25*4, 其中 c(25,13)是从25个点中选取13 个点，这是使用压缩方法后需要内存大小的极值，经计算，不会超过300MB
我们已经看到状态压缩的内存优势，但不禁要问，如何从 01110 这样任意一个集合转化成对应的 index 呢？是时候让 Combinadic 登场了，这里链接提供了index, 集合的转换例子，比如10个点的TSP问题，0101001011对应的index是72， 计算公式是 C(8,5) + C(6,4) + C(3,3) + C(1,2) + C(0,1)，第二个参数递减，第一个参数是不为0的那些位数
72 C(8,5) + C(6,4) + C(3,3) + C(1,2) + C(0,1) 0101001011 (8,6,3,1,0)
有了这两个技巧，25个点的TSP 问题就不用担心内存的问题了。
对于几百个点的TSP问题，用 local search 随机算法比较合适， youtube 上有一个视频，动态的展现出 local search 求解几百个点的tsp问题，很是震撼。