public class TSP {
private double[][] dArray; // 距离矩阵
private int length; // 距离矩阵的长度
public double[][] getdArray() {
return dArray;
}
public int getLength() {
return length;
}
public TSP(double[][] dArray) {
if (this.check(dArray)) {
this.dArray = dArray;
this.length = dArray.length;
}
}
private void dynamic() {
double[][] D = this.dArray;// 原图的邻接矩阵
int n = this.length;
if (this.check(D)) {
int m = (int) Math.pow(2, n - 1);// 列长度，每行有2的n-1次方列
double[][] F = new double[n][m];// 存储阶段最优值，指标
int[][] M = new int[n][m];// 存放阶段最优策略
// 初始化F[][]和M[][]
for (int j = 0; j < m; j++) {
for (int i = 0; i < n; i++) {
F[i][j] = -1;
M[i][j] = -1;
}
}
// 给F的第0列赋初值
for (int i = 0; i < n; i++) {
F[i][0] = D[i][0];
}
// 遍历并填表,除最后一列外，i：行，j：列
double min = 0;
for (int j = 1; j < m - 1; j++) {
for (int i = 1; i < n; i++) {
if (((int) Math.pow(2, i - 1) & j) == 0) {
// 城市i不在j所代表的二进制集合中，可以填表
min = 0;
for (int k = 1; k < n; k++) {
if (((int) Math.pow(2, k - 1) & j) != 0) {
// 对于j集合中所有的k城市，都要存储,j-(int)Math.pow(2, k-1)表示去掉k城市节点后剩下的集合
double temp = D[i][k] + F[k][j - (int) Math.pow(2, k - 1)];
if (min == 0) {
//第一次循环，直接给最小值赋初值
min = temp;
F[i][j] = min;// 保存阶段最优值
M[i][j] = k;// 保存最优决策
}else {
if (temp < min) {
//取小
min = temp;
F[i][j] = min;// 保存阶段最优值
M[i][j] = k;// 保存最优决策
}
}
}
}
}
}
}
// 最后一列，即总最优值的计算，且只有第一行有值，且为最优
min = 0;
for (int k = 1; k < n; k++) {
// 二进制全1，表示集合{1,2,3,4,5}，从中去掉k结点即将k对应的二进制位置0
double temp = D[0][k] + F[k][m-1-(int) Math.pow(2, k - 1)];
if (min == 0) {
//第一次循环，直接给最小值赋初值
min = temp;
F[0][m-1] = min;// 总最优解
M[0][m-1] = k;
}else {
if (temp < min) {
//取小
min = temp;
F[0][m-1] = min;// 总最优解
M[0][m-1] = k;
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
System.out.print(F[j][i]+",");
}
System.out.println();
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
System.out.print(M[j][i]+",");
}
System.out.println();
}
//输出结果，回溯查表M
System.out.println("最短距离为："+ F[0][m-1]);
System.out.print("最短路径顺序为："+"0");
for (int j = m-1,i = 0; j > 0; ) {
i = M[i][j];//下一步去往哪个城市结点
j = j-(int)Math.pow(2, i-1);//从j中去掉i节点
System.out.print("-->"+i);
}
System.out.println("-->0");
}
}
private boolean check(double[][] dArray) {
// 城市少于三个
if (dArray.length < 3) {
System.out.println("错误信息：距离矩阵长度过小");
return false;
}
// 不是方阵
for (int i = 0; i < dArray.length; i++) {
if (dArray.length != dArray[i].length) {
System.out.println("错误信息：距离数组长度不合法");
return false;
}
}
for (int i = 0; i < dArray.length; i++) {
if (!oneZero(dArray[i], i)) {
System.out.println("错误信息：城市间距离设置不合法");
return false;
}
}
return true;
}
// 对于一个doulbe类型的数组， 当且仅有对角元素为0
private boolean oneZero(double[] dArray, int i) {
int numOfZero = 0;
for (double d : dArray) {
if (d == 0.0) {
numOfZero++;
}
}
if (numOfZero == 1 && (dArray[i] == 0)) {
return true;
} else {
return false;
}
}
//主函数
public static void main(String[] args) {
double[][] D = { // 各个节点之间路径长度的二维数组
{ 0, 10, 20, 30, 40, 50 },
{ 12, 0, 18, 30, 25, 21 },
{ 23, 9, 0, 5, 10, 15 },
{ 34, 32, 4, 0, 8, 16 },
{ 45, 27, 11, 10, 0, 18 },
{ 56, 22, 16, 20, 12, 0 }
};
long start = System.currentTimeMillis();
TSP ff = new TSP(D);
ff.dynamic();
long end = System.currentTimeMillis();
long between = end - start;
System.out.println("java环境下用动态规划思想求解TSP问题的运行时间为："+between+"ms");
}
}
查看30道真题和解析
