描述
小明目前在做一份毕业旅行的规划。打算从北京出发，分别去若干个城市，然后再回到北京，每个城市之间均乘坐高铁，且每个城市只去一次。由于经费有限，希望能够通过合理的路线安排尽可能的省一些路上的花销。给定一组城市和每对城市之间的火车票的价钱，找到每个城市只访问一次并返回起点的最小车费花销。
输入描述：
城市个数n（1<n≤20，包括北京）
城市间的车票价钱 n行n列的矩阵 m[n][n]
输出描述：
最小车费花销 s
示例1
输入：
4 0 2 6 5 2 0 4 4 6 4 0 2 5 4 2 0
输出：
13
说明：
共 4 个城市，城市 1 和城市 1 的车费为0，城市 1 和城市 2 之间的车费为 2，城市 1 和城市 3 之间的车费为 6，城市 1 和城市 4 之间的车费为 5，依次类推。假设任意两个城市之间均有单程票可购买，且票价在1000元以内，无需考虑极端情况。
数字表示旅行商问题
参考：https://youtu.be/-JjA4BLQyqE?feature=shared
<iframe width="560" height="315" src="https://www.youtube.com/embed/-JjA4BLQyqE?si=-Nx2lX82IHFRnnjl" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" referrerpolicy="strict-origin-when-cross-origin" allowfullscreen></iframe>
比如 [1,[]]表示就是从1到0的路费也就是 第一行的1到0的费用就是1.
[2,{1,3}]表示就是从2到经过1和3到0的费用就是2到1的费用加上[1,{3}]，与2到3的费用加上[3,{1}]的费用的最小值。
分析： 假设有0,1,2,3四个城市，起点不会影响结果，因此选城市0为起点，创建一个二维数组dp[][]，用二维数组元素的值代表最低花费，用行坐标代表起点城市，列坐标代表接下来要去的城市（注列坐标用二进制表示，如接下来去1,3城市，则使二进制数第一三位为1，即用101表示）。 因此以0为起点的最低花费可表示为dp[0][111]; 以0为起点三种情况： 以0为起点，再进一步选定3为起点，最低花费可表示为cost[0][3]+dp[3][011]; 以0为起点，再进一步选定2为起点，最低花费可表示为cost[0][2]+dp[2][101]; 以0为起点，再进一步选定1为起点，最低花费可表示为cost[0][1]+dp[1][110]; 取上面三个式子最小值，假设第一种最小，即cost[0][3]+dp[3][011]最小 以0为起点，再进一步选定3为起点两种情况： 以0为起点，再进一步选定3为起点，再进一步选定2为起点，最低花费可表示为cost[0][3]+cost[3][2]+dp[2][001]; 以0为起点，再进一步选定3为起点，再进一步选定1为起点，最低花费可表示为cost[0][3]+cost[3][1]+dp[1][010]; 取上面两个式子最小值，假设第一种最小，即cost[0][3]+cost[3][2]+dp[2][001]最小 最低花费可表示为cost[0][3]+cost[3][2]+cost[2][1]+dp[1][000]
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextInt()) { // 注意 while 处理多个 case
int n = in.nextInt();
int[][] m = new int[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
m[i][j]=in.nextInt();
}
}
int min_cost = tsp(m,n);
System.out.println(min_cost);
}
}
public static int tsp(int[][] map,int N){
int[][] dp = new int[N][(int)Math.pow(2, N-1)];
//旅行商问题，就是表示初始点到i位置，需要经过集合V的的可能性。
//动态规划公式 d(i,V) 表示从顶点 i 出发经过 V(是一个点的集合)
// 中各个顶点一次且仅一次，最后回到出发点 s 的最短路径长度。
//根据上述给的测试用例有 5 个城市编号 0,1,2,3,4。那么访问 n 个城市
//，恰好访问每个城市一次，并最终回到出发城市的嘴短距离可表示为
// d(0,{1,2,3,4}),
//集合 {1,3} 表示为二进制为 0101是从右边到左边 4321
for (int j = 0; j < dp[0].length; j++) {
// 四个城市 0 1 2 3，
//外层遍历：j = 000,001,010,100,101,110,111
for (int i = 0; i < dp.length; i++) {
//外层循环遍历所有可能的集合 V，内层循环遍历所有可能的终点城市 i。
// 内层是：i=0 1 2 3,i = 0;
dp[i][j]=Integer.MAX_VALUE;
//如果当前状态 V 为空（即 j == 0），j=0000,且当前城市不是起始城市，
//则将 dp[i][j] 设置为从当前城市到起始城市的距离。
if(j==0&&i!=0) dp[i][j]=map[i][0];
//i!=0就是不是当前城市，比如 2 6 5 块钱存进去
//就是空集的时候，1，2，3城市初始化位价格。
else{
//1 << (i-1) 表示将第 i 位设置为1，其他位都是0。
//对于 i = 3，1 << (i-1) 就是 100。j=1XX都直接跳过，不允许走
if((j&(1<<(i-1)))!=0) continue;//因为路径不允许经过自身城市。
//如果当前遍历的j的二进制数值《110》包含了自身的城市就直接跳过，只遍历正常的城市。
for(int k=1;k<N;k++){
if((j>>(k-1)&1)==1){//j右边移动就是遍历从右往左第k个元素，
//j=110 往右边移动k-1，比如k=2，移动1位为11，第一位就是1，等于1
//j=110，就是经过了2和3城市，当前城市位k=2城市
int newState = j^(1<<(k-1));//110 ^ 10 = 100
//将状态 j 中对应 k 的二进制位取反，从而移除了城市 k 的状态
dp[i][j]=Math.min(dp[i][j], map[i][k]+dp[k][newState]);
//比如 j=001，也就是集合是第一个城市，那么i=2开始了
//那就是只有k=1才能和1与操作等于1，就是第一个城市，就是2要经过1，1回到0，
//dp[2][001] = Math.min(map[2][1]+dp[1][000])
//比如 j=011，也就是集合是{1,2}城市，i=3开始了
//那就是有k=1,k=2,才能和1与操作等于1，就是3要经过{1,2}回到0，
//dp[3][011] = Math.min(dp[3][011],dp[1][010]+map[3][1]);
//也就是3->1->2->0的花费，也就是dp[1][010]就是1到2到0的花费加上map[3][1]，
//3到1的花费之和。
}
}
}
}
}
return dp[0][dp[0].length-1];//dp[0][15];15 = 1111
}
}
当我们在动态规划解决旅行商问题时，我们需要定义状态以及状态之间的转移关系。在这段代码中，dp[i][j] 表示从起始城市到达城市 i 并经过集合 V 中的每个点（集合 V 用二进制位表示）只经过一次的最短路径长度。
让我们用一个简单的例子来说明这个概念。假设我们有四个城市（0，1，2，3），其中城市0是起始城市。我们用一个二维数组 map 来表示城市之间的距离。例如，map[1][2] 表示从城市1到城市2的距离。
城市之间的距离： 0 1 2 3 0 0 10 15 20 1 10 0 35 25 2 15 35 0 30 3 20 25 30 0
在这个例子中，我们需要计算 dp 数组。dp[i][j] 表示从城市0出发，经过集合 V 中的城市到达城市 i 的最短路径长度。在这里，集合 V 是用二进制位表示的。例如，如果 V 为 1100，表示路径经过城市1和城市2，不经过城市0和城市3。
我们来具体看看 dp[2][6] 的含义：
dp[2][6],dp[2][110]表示从城市0出发，经过集合{1,2}中的每个点到达城市2的最短路径长度。- 集合
{1,2}用二进制位表示为 110，其中第一位表示是否经过城市1，第二位表示是否经过城市2。 - 因此，
dp[2][6]表示从城市0出发，经过城市1和城市2，到达城市2的最短路径长度。
在这个例子中，我们可以计算 dp 数组的其他值，以获得从起始城市出发，经过所有城市一次后回到起始城市的最短路径长度。
if( (j & 1<<(i-1)) !=0 ) continue; 这行代码的作用是检查当前状态 j 是否包含当前城市 i。
让我们通过一个例子来解释这行代码：
假设 i = 3，表示当前考虑的城市是第三个城市，即城市编号从1开始。假设 j = 5，表示当前的状态 j 用二进制表示为 101，即表示路径经过第一和第三个城市，而不经过第二个城市。
现在，我们想要检查当前状态 j 是否包含城市 i，即第三个城市。我们可以通过按位与运算来实现。按位与运算可以用来检查某一位是否为1。
- 首先，我们需要将第
i个城市对应的二进制位置为1，其他位置为0，这样我们可以用它来与j进行按位与运算。 1 << (i-1) 表示将第 i 位设置为1，其他位都是0。对于 i = 3，1 << (i-1) 就是 100。 - 然后，我们将这个二进制数与
j进行按位与运算，如果结果不为0，则表示当前状态j中包含城市i。 j & (1 << (i-1))，在我们的例子中，就是 101 & 100，结果是 100，不为0。
因此，如果 j 中包含城市 i，即 (j & (1 << (i-1))) != 0 成立，那么 continue 语句会跳过当前循环，不进行后续的计算，因为路径不允许经过自身城市。
京公网安备 11010502036488号