广州番禺建网站/今日武汉最新消息

问题描述：小明目前在做一份毕业旅行的规划。打算从北京出发，分别去若干个城市，然后再回到北京，每个城市之间均乘坐高铁，且每个城市只去一次。由于经费有限，希望能够通过合理的路线安排尽可能的省一些路上的花销。给定一组城市和每对城市之间的火车票的价钱，找到每个城市只访问一次并返回起点的最小车费花销。输入城市个数n，城市间的车票价钱，n行n列的矩阵。

思路扩展：通常解决tsp问题的办法就是动态规划DP，DP通常用于解决具有最优性质的问题，其基本思想是将待求解问题分解成若干个子问题，先求解子问题，然后由这些子问题的解再得到原问题的解。

补充：用二进制串表示集合，比如集合{1，3，5,6,7}表示成二进制串是1110101，其中集合里面有的数对应的位数写成1，没有的写成0.要判断第三位是不是1，就把1110101右移（3-1）位，得到11101，然后结果和00001进行&运算，如果结果是1说明第三位是1，否则说明第三位是0。所以，对于数字x，要看他的第i位是不是1，那么可以通过判断布尔表达式（（（x>>(i-1)））&1）==1的真值来实现。

解题思路：

实际上就是一个旅行商的问题，假设输入的n为3，那么将要去的城市写成集合{1,2,3}，表示经过【1,2,3】,将北京作为出发点0，那么最终的求解就是dp[0][{1,2,3}.]将{1,2,3}表示为二进制就是111,111对应的10进制是7,所以求解目标就是dp[0][7].

dp[0][{1,2,3}]=min{C01+dp[1][{2,3}],C02+dp[2][{1,3}},C03+dp[3][{1,2}]},其中C01表示从0出发到1的距离。

dp[1][{2,3}] = min{ C12+dp[2][{3}] ，C13+dp[3][{1}]}

dp[2][{3}] = C23+dp[3][{}]

dp[3][{}]就是从3出发，不经过任何城市，回到0的花费，所以dp[3][{}] = C30

dp表的大小，行数是n个城市，列数是集合n的子集个数2^（n-1）.

dp[2][5]，先将5转换为二进制101，则dp[2][5]表示从2出发，经过{1,3}，最后回到起点，那么：

dp[2][5]=min{C21+dp[1][{3}],C23+dp[3][{1}]},将dp中的城市转换为二进制表示再转换为十进制{3}-100-4，即

=min{C21+dp[1][4],C23+dp[3][1]}

从2出发，要去{1,3}，步骤：

　　1.先看去1的路，去了1集合{1,3}中只剩下{3} ,{3}对应4,所以要求的dp表就是dp[1][4],这个4可以通过(101) ^ (1)得到,(1) = 1<<(1-1)

　　2.再看去2的路，5 = 101的第二位是0，所以不能去2。判断第二位为1，用(5>>(2-1)) &1==1。而且也由于从2出发，就更不能去了。

　　3.最后看去3的路，去了3集合{1,3}中只剩下{1},{1}对应这1，所以要求的dp表就是dp[3][1],1通过(101) ^ (100)得到。(100) = 1<<(3-1)

python代码如下：

def tsp( matrix):m, n = len(matrix) * len(matrix), len(matrix)# 状态压缩DP,5表示0101,dp[i][j]表示从0出发,经过i中的几个到达j,要求i中有jdp = [[float('inf')] * n for _ in range(m)]dp[1][0] = 0for i in range(1, m):if not (i & 1):  # i中不能包括0,不能从0出发continuefor j in range(1, n):  # j是要加入的if i & (1 << j):  # 如果i中包括j就重复了continuefor k in range(n):if i & (1 << k):  # 如果i中包括k# i中加上j,0到j的最短距离可能为原来i中任何一个k到j的距离与剩余最短距离之和dp[(1 << j) | i][j] = min(dp[(1 << j) | i][j], dp[i][k] + matrix[k][j])res = float('inf')# 最后还要回到0for i in range(n):res = min(res, dp[m - 1][i] + matrix[i][0])return resn=int(input())
martix=[]
for i in range(n):arr=list(map(int,input().split()))martix.append(arr)
print(tsp(martix))