题目
TSP问题，潜台词：任何一个城市出发都一样，其实是个无向图，但是无向图可以理解为互相有方向的有向图！
暴力过程存在大量重复解
做到记忆化搜索就可以了，本来可变参数的复杂程度超出整型范围就是挺难了，这种题也比较少。这种题的可变参数就是线性结构，表示某个数字存在或者不存在，即非黑即白；可以用位信息来表示线性结构。
但是，TSP问题比这还要复杂，每一个位信息上表达的信息并不是非黑即白的；每一个位信息上的信息是某一个范围上的数字！！！。所以
做到记忆化搜索就可以了。。。
package com.harrison.class32;
import java.util.ArrayList;
import java.util.List;
/**
* @author Harrison
* @create 2022-04-13-9:26
* @motto 众里寻他千百度，蓦然回首，那人却在灯火阑珊处。
*/
public class Code02_TSP {
public static int t1(int[][] matrix){
int N=matrix.length;// 0...N-1
// set
// set.get(i) != null i这座城市在集合里
// set.get(i) == null i这座城市不在集合里
List<Integer> set=new ArrayList<>();
for(int i=0; i<N; i++){
set.add(1);
}
return func1(matrix,set,0);
}
// 任何两座城市之间的距离，可以在matrix里面拿到
// set中表示着哪些城市的集合，
// start这座城一定在set里，
// 从start出发，要把set中所有的城市过一遍，最终回到0这座城市，最小距离是多少
public static int func1(int[][] matrix,List<Integer> set,int start){
int cityNum=0;
for(int i=0; i<set.size(); i++){
if(set.get(i)!=null){
cityNum++;
}
}
if(cityNum==1){
return matrix[start][0];
}
// cityNum > 1 不只start这一座城
set.set(start,null);
int min=Integer.MAX_VALUE;
for(int i=0; i<set.size(); i++){
if(set.get(i)!=null){
// start -> i i... -> 0
int cur=matrix[start][i]+func1(matrix,set,i);
min=Math.min(min,cur);
}
}
// 恢复现场
set.set(start,1);
return min;
}
// 方法2：没有用缓存，用整型位信息替换了线性结构
public static int t2(int[][] matrix){
int N=matrix.length;// 0...N-1
// 7座城 1111111
int allCity=(1<<N)-1;
return f2(matrix,allCity,0);
}
// 任何两座城市之间的距离，可以在matrix里面拿到
// set中表示着哪些城市的集合，
// start这座城一定在set里，
// 从start出发，要把set中所有的城市过一遍，最终回到0这座城市，最小距离是多少
public static int f2(int[][] matrix,int cityStatus,int start){
// cityStatus == cityStatux & (~cityStaus + 1)
// 如果二进制信息中只有一个1了，那这座城市一定是start自己
if(cityStatus==(cityStatus&(~cityStatus+1))){
return matrix[start][0];
}
// 把start位的1去掉，
cityStatus &= (~(1<<start));
int min=Integer.MAX_VALUE;
// 枚举所有城市
for(int move=0; move<matrix.length; move++){
if((cityStatus & (1<<move))!=0){
int cur=matrix[start][move]+f2(matrix,cityStatus,move);
min=Math.min(min,cur);
}
}
cityStatus |= (1<<start);
return min;
}
// 方法3：用了缓存，记忆化搜索
public static int t3(int[][] matrix){
int N=matrix.length;// 0...N-1
// 7座城 1111111
int allCity=(1<<N)-1;
int[][] dp=new int[1<<N][N];
for(int i=0; i<(1<<N); i++){
for(int j=0; j<N; j++){
dp[i][j]=-1;
}
}
return f3(matrix,allCity,0,dp);
}
// 任何两座城市之间的距离，可以在matrix里面拿到
// set中表示着哪些城市的集合，
// start这座城一定在set里，
// 从start出发，要把set中所有的城市过一遍，最终回到0这座城市，最小距离是多少
// 为啥是二维的动态规划？因为是由两个参数决定返回值的
public static int f3(int[][] matrix,int cityStatus,int start,int[][] dp){
if(dp[cityStatus][start]!=-1){
return dp[cityStatus][start];
}
// cityStatus == cityStatux & (~cityStaus + 1)
// 如果二进制信息中只有一个1了，那这座城市一定是start自己
if(cityStatus==(cityStatus&(~cityStatus+1))){
return matrix[start][0];
}else{
// 把start位的1去掉，
cityStatus &= (~(1<<start));
int min=Integer.MAX_VALUE;
// 枚举所有城市
for(int move=0; move<matrix.length; move++){
if((cityStatus & (1<<move))!=0){
int cur=matrix[start][move]+f3(matrix,cityStatus,move,dp);
min=Math.min(min,cur);
}
}
cityStatus |= (1<<start);
dp[cityStatus][start]=min;
}
return dp[cityStatus][start];
}
public static int[][] generateGraph(int maxSize, int maxValue) {
int len = (int) (Math.random() * maxSize) + 1;
int[][] matrix = new int[len][len];
for (int i = 0; i < len; i++) {
for (int j = 0; j < len; j++) {
matrix[i][j] = (int) (Math.random() * maxValue) + 1;
}
}
for (int i = 0; i < len; i++) {
matrix[i][i] = 0;
}
return matrix;
}
public static void main(String[] args) {
int len = 10;
int value = 100;
System.out.println("功能测试开始");
for (int i = 0; i < 1000; i++) {
int[][] matrix = generateGraph(len, value);
int origin = (int) (Math.random() * matrix.length);
int ans1 = t1(matrix);
int ans2 = t2(matrix);
int ans3 = t3(matrix);
if (ans1 != ans2 || ans2!=ans3) {
System.out.println("fuck");
}
}
System.out.println("功能测试结束");
}
}
