旅行商问题是一个著名的NP问题，不能找到多项式解。不过可以用动态规划的方法把时间复杂度从O(N!)降低到O
(2^N)。对于解决小规模的旅行商还是可以实现的。
http://icpc.ahu.edu.cn/OJ/Problem.aspx?id=420
发现枚举过程中还是有很多重复计算的，所以可以存贮一下状态，避免了重复计算。
开辟N+1维数组，dp[N][2][2]..[2]
dp[cur][p1][p2]..[pn]表示，当前人在cur位置,并且p1--pn走过的为1，未走过的为0。
可见空间复杂度为N*2^N。
状态转移方程为dp[cur][p1]..[1]..[pn]=min{dp[i][p1]..[0]..[n]+Dis[cur][i]};其中i为1--N地点中已经走过的
地点。因为当前状态只能从已经走过的那些地方走过来，所以只要选一个最短的，就表示走完以上地点，并且停在
当前点需要的最短路程就是这么多。
由于回路必然包含每一个点，所以从任何点出发，得到的最短路径都是一定的。所以我的程序假设就从第一个点出
发。边界条件就是,dp[0][1]。dp[0][1]=0，表示在第0个地点(我是用0--N-1表示N个地点的)，1的二级制是
00000001，表示只有第一个可以走过。
要注意:既然假设从第一个地点出发，所以在递归自顶向下搜索的时候，只有最后一次才能回出发点！
即dp[cur][p1]..[1]..[pn]中，在p1--pn中只有2个为1的时候，也就是只有出发点和第二个地点的时候，才能从第
二个地点回到出发点。
最终的结果只要取min{dp[i][1]..[1]..[1]+Dis[0][i]}就好了，表示回到出发点0。构成完整回路。
当然如果N比较大，开那么多维的数组比较麻烦，而且可能编译不能通过。所以我们用一个数的不同位分别表示一个
城市是否走过。于是将N维压缩到一维。
dp[N][2]..[2]变成了 dp[N][2^N]
本文链接：https://my.lmcjl.com/post/6592.html
4 评论