旅行商问题，即TSP问题（Traveling Salesman Problem）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。
环境：程序使用语言java，jdk版本1.8，程序中用到的jar包：poi-3.17
jar包下载地址：https://www.apache.org/dyn/closer.lua/poi/release/bin/poi-bin-3.17-20170915.tar.gz



程序中使用的数据：下载地址：https://download.csdn.net/download/qq_35685675/10487174


项目导入：


3.实验主要源代码
City.java//城市类，结构体
package TSP;
publicclass city {
   privateintname;
   privatedoubleX;
   privatedoubleY;
   public city(intname, doublex, doubley) {
      super();
      this.name = name-1;
      X = x;
      Y = y;
   }
   publicint getName() {
      returnname;
   }
   publicvoid setName(intname) {
      this.name = name;
   }
   publicdouble getX() {
      returnX;
   }
   publicvoid setX(doublex) {
      X = x;
   }
   publicdouble getY() {
      returnY;
   }
   publicvoid setY(doubley) {
      Y = y;
   }
   @Override
   public String toString() {
      return"city [name=" + name + ",X=" + X + ", Y=" + Y + "]";
   }
  
}
 
inputData.Java//导入数据类
package TSP;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
 
import org.apache.poi.hssf.usermodel.HSSFRow;
import org.apache.poi.hssf.usermodel.HSSFSheet;
import org.apache.poi.hssf.usermodel.HSSFWorkbook;
 
publicclass inputData {
   @SuppressWarnings("resource")
   publicstatic List<city> input_att48(File file){
      List<city> cityList = new ArrayList<city>();
      try {
          HSSFWorkbook wookbook = new HSSFWorkbook(new FileInputStream(file));
          HSSFSheet sheet = wookbook.getSheet("Sheet1");
          introws = sheet.getPhysicalNumberOfRows();
          for(inti=1; i<rows; i++){
             HSSFRow row = sheet.getRow(i);
             if(row!=null){
                city cy = new city(i, row.getCell(1).getNumericCellValue(), row.getCell(2).getNumericCellValue());
                cityList.add(cy);
             }
          }
         
      } catch (FileNotFoundException e) {
          System.out.println("File not fount!");
      } catch (IOException e) {
          System.out.println("IO exception!");
      }
      returncityList;
   }
}
 
DP.Java//核心代码
package TSP;





import java.io.File;

import java.util.List;

import java.util.Scanner;





public class DP {


 //V集合表示已经旅行后的点的集合。


 //n点经过集合V中所有点到达起始点的最短距离；1<<(n-1)代表一个二进制串，


 //1代表该位置的城市在V集合例，反之不在。


 static double INF = Double.MAX_VALUE;


 static double[][] DT = null;


 static double[][] DP = null;

//
 static int n = 0;


 static void init(int n) {


 File file = new File("E:\\Java\\arithmetic\\src\\resource\\att48.xls");


 List<city> cityList = inputData.input_att48(file);


 System.out.println("city [城市编号   城市X坐标    城市Y坐标]");


 for(int i=0; i<n; i++) {


 System.out.println(cityList.get(i).toString());


 }


 DT = new double[n][n];


 DP = new double[n][1<<(n-1)];


 for(int i=0; i<n; i++) {


 for(int j=i; j<n; j++) {


 if(i==j) DT[i][j] = 0;


 else {


 double dertX = cityList.get(i).getX()-cityList.get(j).getX();


 double dertY = cityList.get(i).getY()-cityList.get(j).getY();


 DT[i][j] = Math.sqrt(dertX*dertX + dertY*dertY);


 DT[j][i] = DT[i][j];


 }


 }


 }


 

//
 for(int i=0; i<n; i++) {

//
 for(int j=0; j<n; j++) {

//
 System.out.print(DT[i][j]);

//
 System.out.print(" ");

//
 }

//
 System.out.println();

//
 }


 


 //V集合为空的情况，初始化第i点直接回到起点s的距离


 for(int i=1; i<n; i++) {


 DP[i][0] = DT[i][0];


 }


 }


 


 static void solve(int n) {


 double minDt = INF;


 double temp = 0;


 for(int j=1; j<1<<(n-1); j++){//j的二进制表示V集合。


         for(int i=1; i<n; i++){//n个点减去起点还有n-1个点，遍历n-1个点选一个不在集合V中的点。


             if((1<<(i-1)&j)==0){//(1<<(i-1))&j==0表示i不在集合v中


                 minDt = INF;


                 for(int k=1; k<n; k++){


                     if(((1<<(k-1))&j)!=0){//(1<<(k-1))&j==1表示k在集合V中


                         temp = DT[i][k] + DP[k][j-(1<<(k-1))];


                         if(temp < minDt) minDt = temp;


                     }


                 }


             }


             DP[i][j] = minDt;


         }


     }


 minDt = INF;


     for(int k=1; k<n; k++){//1<<(9)=1000000000，((1<<(n-1))-1)=111111111111...


         temp = DT[0][k] + DP[k][((1<<(n-1))-1)-(1<<(k-1))];


         if(temp < minDt){


             minDt = temp;


         }


     }


     System.out.print("最短路径长：");


     System.out.println(minDt);


 }


 


 @SuppressWarnings("resource")


 public static void main(String[] args) {


 // TODO Auto-generated method stub


 System.out.println("----------------动态规划解决TSP问题----------------");


 Scanner in = new Scanner(System.in);


 while(true) {


 System.out.println();


 System.out.println("请输入城市数：");


 int n = in.nextInt();


 if(n>24) {


 System.out.println("城市数过多，请使用其他算法！");


 return;


 }


 init(n);


 solve(n);


 }


 }

}


输入输出：

 
您可以将集合编码为整数：整数的第i位表示第i个城市的状态(即，我们是否将其放入子集中)。
 
例如，3510=1000112将表示城市{1，2，6}。这里我从最右边的一位开始计数，代表城市1。在
 
为了使用子集的这种表示来索引列表，您应该创建长度为2n的二维数组：# Assuming n is given.
 
A = [[0 for i in xrange(n)] for j in xrange(2 ** n)]
 
这是因为使用n位整数可以表示{1，2，…，n}的每一个子集(请记住，每一位正好对应于一个城市)。在
 
此表示为您提供了许多不错的可能性：
 
^{pr2}$
 
这是我如何实现您的伪代码(警告：没有进行测试)：# INFINITY and n are defined somewhere above.
 
A = [[INFINITY for i in xrange(n)] for j in xrange(2 ** n)]
 
# Base case (I guess it should read "if S = {1}, then A[S, 1] = 0",
 
because otherwise S = {0} is not a valid index to A, according to line #1)
 
A[1][1] = 0
 
# Iterate over all subsets:
 
subsets = range(1, 2 ** n)
 
for subset in sorted(subsets, key=lambda x: bin(x).count('1')):
 
if not subset & 1:
 
# City #1 is not presented.
 
continue
 
for j in xrange(2, n + 1):
 
if not (1 << (j - 1)) & subset:
 
# City #j is not presented.
 
continue
 
for k in xrange(1, n + 1):
 
if k == j or not (1 << (k - 1)) & subset:
 
continue
 
A[subset][j] = min(A[subset][j], A[subset ^ (1 << (j - 1))][k] + get_dist(j, k))
 
除了拥有实现伪代码所需的所有功能外，这种方法比tuples\dicts更快。在

    TSP问题是指旅行家要旅行n个城市，要求各个城市经历且仅经历一次然后回到出发城市，并要求所走的路程最短。各个城市间的距离可以用代价矩阵来表示。
    假设从顶点i出发，令d(i, V')表示从顶点i出发经过V'中各个顶点一次且仅一次，最后回到出发点i的最短路径长度，开始时，V'＝V－{i}，于是，TSP问题的动态规划函数为：
d(i,V')=min{cik+d(k,V－{k})}(k∈V')
d(k,{})=cki(k≠i)

    伪代码：
for (i=1; i<n; i++)     //初始化第0列
	d[i][0]=c[i][0]; 
 for (j=1; j<2n-1-1; j++)  
 	for (i=1; i<n; i++)   //依次进行第i次迭代
		if (子集V[j]中不包含i) 
 			对V[j]中的每个元素k，计算[i][j]=min(c[i][k]+d[k][j-1]);
对V[2n-1-1]中的每一个元素k，计算d[0][2n-1-1]=min(c[0][k]+d[k][2n-1-2]);
输出最短路径长度d[0][2n-1-1];

    笔者在写此程序时卡在了如何判断：子集V[j]中不包含i。解决方法是对n个顶点分别用0~n-1的数字编号，按个数为1,2,……,n-1的顺序生成1~n-1个元素的子集存放在数组V[2^n-1]中。这样，在判断时就可以将当前点与数组编号按位与运算（如下图所示），为0则为需要进行计算（这时才能品味按位与运算的美）。


    完整代码：
#include<iostream.h>
#include<math.h>
int main()
{
	int i,j,k,min,brief,n;
	int D[20][20];
	cout<<"顶点个数：";
	cin>>n;
	int b=(int)pow(2,n-1);
  	for(i=0;i<n;i++)
    	for(j=0;j<n;j++)
      		cin>>D[i][j];
  	int ** Route = (int **)calloc(n, sizeof(int *));
  	int ** Mat = (int **)calloc(n, sizeof(int *));
  	for(i=0;i<n;i++)
  	{
    	Route[i] = (int *)calloc(b*b, sizeof(int))+i*b;
    	Mat[i] = (int *)calloc(b*b, sizeof(int))+i*b;
  	}
  	for(i=0;i<b;i++)
   		for(j=0;j<n;j++)
	    {
			Route[j][i] = -1;
   			Mat[j][i] = -1;
	    }
  	for(i=0;i<n;i++)//初始化第0列 
    	Route[i][0] = D[i][0];    
  	for(i=1;i<b-1;i++)
	    for(j=1;j<n;j++)//依次进行第i次迭代 
			if( ((int)pow(2,j-1) & i) == 0)//子集V[j不包含i 
			{
				min=999;
				for(k=1;k<n;k++)
				if( (int)pow(2,k-1) & i )
				{
					brief = D[j][k] + Route[k][i-(int)pow(2,k-1)]; 
					if(brief < min)
					{
						min = brief;
						Route[j][i] = min;
						Mat[j][i] = k;//局部最优决策
					}
				}    
			}
	min=999;
  	for(k=1;k<n;k++)
	{
		brief = D[0][k] + Route[k][b-1 - (int)pow(2,k-1)];
		if(brief < min)
		{
			min = brief;
			Route[0][b-1] = min;//最优解
			Mat[0][b-1] = k;
		}
	}
	cout<<"最短路径长度："<<Route[0][b-1]<<endl;//最短路径长度
	cout<<"最短路径："<<"1";
	for(i=b-1,j=0; i>0; )
	{
		j = Mat[j][i];
		i = i - (int)pow(2,j-1);
		cout<<"->"<<j+1;
	}
	cout<<"->1"<<endl;
	for(i=0;i<n;i++)
	{
		for(j=0;j<b;j++)
  			cout<<Route[i][j]<<" ";
		cout<<endl;
	}
	free(Route);
	free(Mat);
	return 0;
}

 
本介绍用python解决TSP问题的第二个方法——动态规划法
 
算法介绍
 
动态规划算法根据的原理是，可以将原问题细分为规模更小的子问题，并且原问题的最优解中包含了子问题的最优解。也就是说，动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。
 
我使用DP求解TSP问题的主要分为三个主要部分：
 
1)     假定我们从城市0出发，经过了所有城市，并返回到城市0。那么我们需要记录的信息有：当前所在城市location，当前未遍历的城市集合s。
 
2)     状态转移方程，状态转移方程是DP算法的核心部分，它代表了子问题和原问题的关系，通过状态转移方程可以将原问题不断细分为各个子问题。我们状态转移方程的定义如下所示：
 

 
T(s,init)代表的意思是从init点出发经过s中全部的点回到init的距离。
 
3)     构建T表记录T的值，如果不去记录每次递归的T值，那么以后每次搜索都要重新计算，就成了暴力搜索。所以我们构建一个T表dp[s][init]，记录每次求出来的T函数值，即将T(s,init)的值记录在dp[s][init]位置。
 
程序
 
输入：
 
1 2066 2333
 
2 935 1304
 
3 1270 200
 
4 1389 700
 
5 984 2810
 
6 2253 478
 
7 949 3025
 
8 87 2483
 
9 3094 1883
 
10 2706 3130
 
代码：
 
"""
 
动态规划法
 
name:xxx
 
date:6.8
 
"""
 
import pandas as pd
 
import numpy as np
 
import math
 
import time
 
dataframe = pd.read_csv("./data/TSP10cities.tsp",sep=" ",header=None)
 
v = dataframe.iloc[:,1:3]
 
train_v= np.array(v)
 
train_d=train_v
 
dist = np.zeros((train_v.shape[0],train_d.shape[0]))
 
#计算距离矩阵
 
for i in range(train_v.shape[0]):
 
for j in range(train_d.shape[0]):
 
dist[i,j] = math.sqrt(np.sum((train_v[i,:]-train_d[j,:])**2))
 
"""
 
N:城市数
 
s:二进制表示，遍历过得城市对应位为1，未遍历为0
 
dp:动态规划的距离数组
 
dist：城市间距离矩阵
 
sumpath:目前的最小路径总长度
 
Dtemp：当前最小距离
 
path:记录下一个应该到达的城市
 
"""
 
N=train_v.shape[0]
 
path = np.ones((2**(N+1),N))
 
dp = np.ones((2**(train_v.shape[0]+1),train_d.shape[0]))*-1
 
def TSP(s,init,num):
 
if dp[s][init] !=-1 :
 
return dp[s][init]
 
if s==(1<
 
return dist[0][init]
 
sumpath=1000000000
 
for i in range(N):
 
if s&(1<
 
m=TSP(s&(~(1<
 
if m
 
sumpath=m
 
path[s][init]=i
 
dp[s][init]=sumpath
 
return dp[s][init]
 
if __name__ == "__main__":
 
init_point=0
 
s=0
 
for i in range(1,N+1):
 
s=s|(1<
 
start = time.clock()
 
distance=TSP(s,init_point,0)
 
end = time.clock()
 
s=0b11111111110
 
init=0
 
num=0
 
print(distance)
 
while True:
 
print(path[s][init])
 
init=int(path[s][init])
 
s=s&(~(1<
 
num+=1
 
if num>9:
 
break
 
print("程序的运行时间是：%s"%(end-start))
 
结果：