浅谈可重复访问城市的TSP问题(最短距离 + 具体走法)

小伙伴们，你们好。今天我来浅显的讲一下这个可重复访问城市的TSP问题，所谓的可重复就是城市和路线都随便走，只要最后它的路径总和是最小的就行。

要用到的知识点是 状态压缩dp 和 Floyd算法

一、Floyd算法

Floyd算法：floyd算法学习视频
这个小姐姐会用手算的方式带你了解floyd算法的整个过程，相信看完你就有一种恍然大悟的感觉了

我下面floyd算法的主要作用是让我们得到一个距离二维数组，路径二维数组

1.distance[][]

例子:distance[i][j] 表示点i到点j的最短距离
有了这个数组，我们第一步就完成了

2.path[][]

例子：path[i][j]表示点i到点j中间经过了什么点

	public void floyd(Double[][] distance,int[][] path,Double[][] edge) {
        int n = edge.length;//edge数组是一个邻接矩阵
        //初始化一下传进来距离数组
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                path[i][j] = -1;
                if (i!=j) {
                    distance[i][j]  = edge[i][j];
                }else {
                    distance[i][j] = 0.0;
                }
            }
        }
        //核心算法
        for (int k=0;kdistance[i][k]+distance[k][j]) {
                        distance[i][j] = distance[i][k]+distance[k][j];
                        path[i][j] = k;//记录路径的数组
                    }
                }
            }
        }
    }

通过调用函数jointPath(…)我们就可以找到v0=>v的完整路径了，这对我们求TSP的路径也是至关重要的

//int[][] path:由floyd得到
//v0:起点，v:终点
//idx[0]:因为我要记住p数组的有效长度，所以用了idx[0]来保证它可以当指针用
//ps:我有点菜，写得不是很好
    public void jointPath(int[][] path,int v0,int v,int[] p,int[] idx) {
        getPath(path,v0,v,p,idx);
        p[idx[0]++] = v;
    }
    //好好用纸来模拟一下这个递归函数，你就悟了
	public void getPath(int[][] path,int v0,int v,int[] p,int[] idx) {
        if (path[v0][v]==-1) {
            p[idx[0]++] = v0;
            return;
        }
        getPath(path,v0,path[v0][v],p,idx);//左边
        getPath(path,path[v0][v],v,p,idx);//右边
    }

写完博客，我会录制视频在b站，你们可以关注一下我，看一下我的视频讲解 : 随风的叶子(我的账号名称) 二、状态压缩dp

视频学习连接，看前33分钟就行
这个视频里面，他会教你dp的概念还有怎么使用与、或、非和异或
这老师讲得还是十分详细的，里面讲解的题目：最短Hamilton路径
这道题和我们要解决的问题有着异曲同工之妙，能够解决上面的这道题，相信下面你们快速的掌握。

欢迎回来，相信你对dp有一定了解了. 下面，我们要有这样一种思维：就是我们只注重点i到点j的最短距离，就是我们把心放在distance[][]数组上面，我们无需关系i到j之间通过了什么点，所以我们dp集合加入了i和j,那么i和j之间包含1了什么点我们不管，也不会加入到dp集合中，我们关心的只有最短，因为点和边是可以重复的

你应该get到我的点了吧

接下来，我就和你讲讲这道题的具体思路：

首先我们开一个dp[1<

因为我们要表示每个集合的状态，而状态有0~111…111(2^n-1)

当我们成功的将我们的状态搞到111…111(2^n-1)就是我们胜利的时刻了

下面，我来上代码来说话(要认真看我的注释噢)

dp[s][i] = Math.min(dp[s][i],dp[s^(1<

然后，我还是想和大家说一下
ps: 以下从第0位开始

• s&(1<
• s^(1<

 //==================状态压缩DP
        Double[][] dp = new Double[1< dp[(1< 
下面有必要声明一下：
 @Autowired
 private FloydUtil floydUtil;（这玩意是因为我写springboot项目用了，你们看到函数名知道我在放什么屁就行了，抱拳了）
 
public void TSP_can_repeat_path(Double[][] dp,Double[][] dis,int[] path,int end,int n)
public void completePath(int[][] path,int[] p,int[] initP,int[] idx)
 
ps:参数具体什么含义，看我注解就知道了
 
我先说一下我第一个算法的作用，现有状态s就是不断的回退状态t，然后找到状态t到状态s的最短路径来确定点（再重复一遍：我这里i->j，可能里面还包含了别的点，只是我们通过两点的最短路路径看成它们相通罢了）
 

 
 
看这张图：箭头右边的数组表示第i位变位0了，当最后集合变成0就是我们胜利的时刻了（重复一次：从第0位开始）
 
if (index==-1) break;//结束条件，你也可以自己优化一下，反正我就爱这么写[哈哈],当下标没有变化的时候就结束了
 
这个时候，我们只是成功了一半，
 
0   1   2   3   13   14   15   12   4   11   16   11   5   6   5   10   17   18   9   19   8   7 0
 
再再再重复一遍：0=>1或者 10=>7,表示的只是最短路径，我们还要将他们中间存在的点找出来，这个时候的找我们就回到floyd算法里面涉及的找路径，我们通过一个for就能全部找出来了，
 
floydUtil.getPath(…)：我这里这个函数不会将它最后一个元素加入数组中 
认真看下面的代码就理解整个过程了，期待我在b站把视频肝出来吧 
//求出路径
	
    public void TSP_can_repeat_path(Double[][] dp,Double[][] dis,int[] path,int end,int n) {//end从0开始
        int s = (1<"+end);
            Double min = Double.MAX_VALUE;
            int index = -1;
            for (int i = 0; i < n; i++) {
                if ( (s&(1< dp[s][i]+dis[i][end]) {
                    min = dp[s][i]+dis[i][end];
                    index = i;
                }
            }
            if (index==-1) break;
            path[idx] = index;
            end = index;
            idx ++;
        }
        for (int i = 0; i < (n / 2) - 1; i++) {
            int tmp = path[i];
            path[i] = path[n-1-i];
            path[n-1-i] = tmp;
        }
    }

    
    public void completePath(int[][] path,int[] p,int[] initP,int[] idx) {
        int n = initP.length;
        for (int i = 0; i < n-1; i++) {
            int[] res =  new int[n];
            int[] index = new int[1];
            floydUtil.getPath(path,initP[i],initP[i+1],res,index);
            for (int j = 0; j < index[0]; j++) {
                p[idx[0]++] = res[j];
            }
        }
        p[idx[0]++] = initP[n-1];//最后一个点放进来

    }
 
下面是我写的完整代码
 
package com.lin.utils;

import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.stereotype.Component;

@Component
public class FloydDPUtil {

    @Autowired
    private FloydUtil floydUtil;


    
    public Double TSP_can_repeat(int[] p,int[] iii,int n) {
        //==================floyd
        Double[][] distance = new Double[n][n];
        int[][] path = new int[n][n];
        floydUtil.floyd(distance,path);
        //==================状态压缩DP
        Double[][] dp = new Double[1< dp[(1<"+end);
            Double min = Double.MAX_VALUE;
            int index = -1;
            for (int i = 0; i < n; i++) {
                if ( (s&(1< dp[s][i]+dis[i][end]) {
                    min = dp[s][i]+dis[i][end];
                    index = i;
                }
            }
            if (index==-1) break;
            path[idx] = index;
            end = index;
            idx ++;
        }
        for (int i = 0; i < (n / 2) - 1; i++) {
            int tmp = path[i];
            path[i] = path[n-1-i];
            path[n-1-i] = tmp;
        }
    }

    
    public void completePath(int[][] path,int[] p,int[] initP,int[] idx) {
        int n = initP.length;
        for (int i = 0; i < n-1; i++) {
            int[] res =  new int[n];
            int[] index = new int[1];
            floydUtil.getPath(path,initP[i],initP[i+1],res,index);
            for (int j = 0; j < index[0]; j++) {
                p[idx[0]++] = res[j];
            }
        }
        p[idx[0]++] = initP[n-1];//最后一个点放进来

    }

}
 
作者：随风
 
有什么问题可以私聊我qq:2338244917
 
你们可以关注我的b站账号：随风的叶子 跳转=>随风的叶子
 
我写完已经凌晨两点半了，还请给我点个赞
 
 csdn粉丝数快突破300了，谢谢你们的支持