旅行商问题 & TSP问题：有n个城市从起点 0 开始游历每一个城市，只访问每个城市一次最后回到起点，所需要的最短路径是多少
这个属于NP完全问题。最直接的方法就是枚举法解空间为n个元素的所有排列组合，为(n?1)!n稍微一大就无法在有限的时间内做出。还有一些模拟退火算法什么的这个不太了解，有空洅去了解下
在acm中，对于此问题n一般都不大，可以运用floyd + 状压dp来做
对于集合的dp 被称为状态压缩dp。对于一个集合来说我们可以把每一个元素是否选取对应到一个二进制数位里从而将状态压缩成一个整数。
s表示已经经过的城市的集合v表示现在正处在的城市。定义dp[s][v]为从v出发訪问所有剩余的城市再返回起点所需要的最短的路径。mp[i][j] 表示 i 到 j 的最短路
可以运用上面说的状压dp的方法来做。
比如 5 个城市表示成5位二進制数， 对于每一位来说（也就是每一个城市来说）0表示没有访问过1表示已经访问过。 00000就表示都没有访问过
求出mp[i][j] 即任意两点的最短路： 直接 floyd就好了。
poj 3311 记忆化搜索。记忆化搜索好久没写过了有点手生。