用回溯算法解决TSP问题

旅行商问题，即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;

   }

}

 

backtrack.Java//核心代码

package TSP;

import java.io.File;
import java.util.List;
import java.util.Scanner;


public class backtrack {

static double INF = Double.MAX_VALUE;
static double[][] DT = null;
static int[] mark = null;
static int[] bestPath = null;
static int[] curPath = null;
static double bestPathLength = INF;
static double curPathLength = 0;
static int n = 0;
static void init() {
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];
mark = new int[n];
bestPath = new int[n+1];
curPath = new int[n+1];
bestPathLength = INF;
curPathLength = 0;
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];
}
}
}
}

static void solve(int i) {
if(i >= n) {
if(DT[curPath[i-1]][0]<INF && (curPathLength+DT[curPath[i-1]][0]<bestPathLength)) {
bestPathLength = curPathLength+DT[curPath[i-1]][0];
for(int j=0; j<n; j++) {
bestPath[j] = curPath[j];
}
}
}
else {
for(int j=0; j<n; j++) {
if(mark[j]==0 && DT[curPath[i-1]][j]<INF && curPathLength+DT[curPath[i-1]][j]<bestPathLength) {
curPath[i] = j;
curPathLength += DT[curPath[i-1]][j];
mark[j] = 1;
solve(i+1);
curPathLength -= DT[curPath[i-1]][j];
mark[j] = 0;
}
}
}
}

@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("请输入城市数：");
n = in.nextInt();
if(n>48) {
System.out.println("样例有限，城市数不能超过48！");
return;
}
init();
curPath[0] = 0;
mark[0] = 1;
solve(1);
System.out.println("旅行路线：");
System.out.print(bestPath[0]);
for(int i=1; i<=n; i++) {
System.out.print("->");
System.out.print(bestPath[i]);
}
System.out.println();
System.out.print("路线长度：");
System.out.println(bestPathLength);
}
}


}

输入输出：