问题分析：
旅行售货员问题是一个经典的组合优化问题，其目标是找到一条访问所有城市并返回起点的最短路径。回溯法是一种基于试错的算法，通过系统地搜索所有可能的解来找到问题的最优解。
问题求解：
初始化：
确定城市数量，路径数量以及路径矩阵。
设定两个变量来存储当前找到的最短路径长度和此次遍历的路径长度。
初始化两个一维数组来存储最短路径对应的城市顺序以及此次遍历对应的城市顺序。
初始化计数器来将数组改造成动态数组，增删时更加方便，删除时只需要计数器减一。
初始化布尔数组，来记录遍历过程中城市是否已经走过。
public static int cityNum; // 城市总数
public static int disNum; // 路径总数
public static int[][] disArray; // 存储城市间距离
public static int shortDis = Integer.MAX_VALUE; // 记录最短路径长度
public static int nowDis = 0; // 记录这次遍历过程中的路径长度
public static int[] shortDisArray; // 最短路径经过的城市顺序
public static int[] nowDisArray; // 记录这次遍历过程中的经过的城市顺序
public static int cout = 0; // 计数器，表示现在走了几个城市
public static boolean[] isPass; // 表示是否遍历过
表示城市不可达：
由于距离都为正，因此我们可以对不存在的路径距初始化为-1，这样只要判断一下就能知道城市是否可达。
// 城市间距离初始化为 -1，表示不可达
for (int i = 0;i < cityNum;i++) {
for (int j = 0;j < cityNum;j++) {
disArray[i][j] = -1;
}
}
for (int i = 0;i < cityNum;i++) {
shortDisArray[i] = -1;
nowDisArray[i] = -1;
}
录入路径：
设定一个循环，条件是当前录入的城市间距离数量nowDisNum小于总需录入的距离数量disNum。提示用户输入城市的编号，编号范围在0到cityNum-1之间。如果输入的编如果输入的编号不合法，提示用户重新输入，并继续下一次循环。校验两次输入的城市是否相同，提示用户不能输入同个城市，并重新输入。如果这两个城市间的距离在二维数组disArray中已存在（即不是-1），提示用户距离已存在，并重新输入。如果输入的距离不是正整数（即小于0），提示用户重新输入。将输入的距离值保存在二维数组disArray的对应位置，同时考虑到距离的无向性，也保存对称位置的值。
// 循环录入城市间距离
while (nowDisNum < disNum) {
// 输入第一个城市时只要判断编号是否正常就行
System.out.println("请输入第一个城市的编号（0 - " + (cityNum-1) + ")");
a = scan.nextInt();
if (a < 0 || a >= cityNum) {
System.out.println("输入参数有误，请重新输入");
continue;
}
// 第二个城市需要判断编号是否正常，是否是不同城市，是否已经录入过
System.out.println("请输入第二个城市的编号（0 - " + (cityNum-1) + ")");
b = scan.nextInt();
if (b < 0 || b >= cityNum) {
System.out.println("输入参数有误，请重新输入");
continue;
}else if (a == b) {
System.out.println("不能输入同个城市，请重新输入");
continue;
}else if (disArray[a][b] != -1) {
System.out.println("这两个城市间的距离已存在，请重新输入");
continue;
}
// 录入距离时判断距离是否为正整数
System.out.println("请输入这两个城市间的距离：");
d = scan.nextInt();
if (d < 0) {
System.out.println("输入参数有误，请重新输入");
continue;
}
// 录入数据到二维数组中
disArray[a][b] = disArray[b][a] = d;
System.out.println("输入成功");
nowDisNum++;
}
回溯：
当递归函数返回时，表示当前路径的所有可能性都已探索完毕，此时需要将最后一个添加的城市从路径中移除，以便尝试其他可能性。这就是“回溯”的过程，即撤销上一步的选择，尝试其他选择。
public static void huisu(int now) {
//开始遍历
for (int j = 0;j < cityNum;j++) {
// 下一个打算走的城市为-1，不可达，不选这个
if (disArray[now][j] == -1) continue;
// 如果城市已经走过了，不选这个
if (isPass[j]) continue;
// 满足条件，可以选择走
isPass[j] = true; // 将这个暂时设定为走过
nowDis+= disArray[now][j]; // 添加距离到总路径长度
nowDisArray[cout++] = j; // 将经过城市记录到顺序中
huisu(j); // 进入下一个选择
isPass[j] = false; // 回溯，改回未走过
nowDis-= disArray[now][j]; // 回溯，减掉这段路径
cout--; // 回溯，减掉这段路径
}
}
终止条件：
当所有可能的路径都被探索过，且最短路径和距离已被确定时，算法终止。
// 如果全部城市走完
if (cout == cityNum) {
int start = nowDisArray[0]; // 找出初始城镇
// 如果最后一个城镇能否回到初始城镇
if (disArray[now][start] != -1) {
nowDis+= disArray[now][start]; // 添加最后城镇回初始城镇的路程
// 如果比记录的最短路径短
if (nowDis <= shortDis) {
shortDis = nowDis;
System.arraycopy(nowDisArray, 0, shortDisArray, 0, nowDisArray.length);
}
}
}
优化：
虽然回溯法可以找到TSP问题的精确解，但其时间复杂度非常高。因此，我们可以在生成路径的过程中，通过比较部分路径的当前距离与已知的最短距离来提前终止一些显然不可能得到更优解的搜索分支，减少搜索空间，提高算法效率。
// 如果还没走完路径已经比记录的最短路径长了，那就没必要继续走了
if (nowDis > shortDis) return;
总代码：
import java.util.Scanner;
public class huisu {
public static int cityNum; // 城市总数
public static int disNum; // 路径总数
public static int[][] disArray; // 存储城市间距离
public static int shortDis = Integer.MAX_VALUE; // 记录最短路径长度
public static int nowDis = 0; // 记录这次遍历过程中的路径长度
public static int[] shortDisArray; // 最短路径经过的城市顺序
public static int[] nowDisArray; // 记录这次遍历过程中的经过的城市顺序
public static int cout = 0; // 计数器，表示现在走了几个城市
public static boolean[] isPass; // 表示是否遍历过
public static void huisu(int now) {
// 如果全部城市走完
if (cout == cityNum) {
int start = nowDisArray[0]; // 找出初始城镇
// 如果最后一个城镇能否回到初始城镇
if (disArray[now][start] != -1) {
nowDis+= disArray[now][start]; // 添加最后城镇回初始城镇的路程
// 如果比记录的最短路径短
if (nowDis <= shortDis) {
shortDis = nowDis;
System.arraycopy(nowDisArray, 0, shortDisArray, 0, nowDisArray.length);
}
}
}
// 如果还没走完路径已经比记录的最短路径长了，那就没必要继续走了
if (nowDis > shortDis) return;
// 没有走完就从现在的城市开始遍历
for (int j = 0;j < cityNum;j++) {
// 下一个打算走的城市为-1，不可达，不选这个
if (disArray[now][j] == -1) continue;
// 如果城市已经走过了，不选这个
if (isPass[j]) continue;
// 满足条件，可以选择走
isPass[j] = true; // 将这个暂时设定为走过
nowDis+= disArray[now][j]; // 添加距离到总路径长度
nowDisArray[cout++] = j; // 将经过城市记录到顺序中
huisu(j); // 进入下一个选择
isPass[j] = false; // 回溯，改回未走过
nowDis-= disArray[now][j]; // 回溯，减掉这段路径
cout--; // 回溯，减掉这段路径
}
}
public static void main(String[] args) {
// 初始化参数
Scanner scan = new Scanner(System.in);
System.out.println("请输入城市总数：");
cityNum = scan.nextInt(); // 城市总数
System.out.println("请输入路径总数：");
disNum = scan.nextInt(); // 路径总数
int nowDisNum = 0; // 现在已经输入的路径数
int a = -1; // 第一个城市的编号
int b = -1; // 第二个城市的编号
int d = -1; // 两城市间距离
disArray = new int[cityNum][cityNum]; // 存储城市间距离
shortDisArray = new int[cityNum]; //
nowDisArray = new int[cityNum];
isPass = new boolean[cityNum];
// 城市间距离初始化为 -1，表示不可达
for (int i = 0;i < cityNum;i++) {
for (int j = 0;j < cityNum;j++) {
disArray[i][j] = -1;
}
}
for (int i = 0;i < cityNum;i++) {
shortDisArray[i] = -1;
nowDisArray[i] = -1;
}
// 循环录入城市间距离
while (nowDisNum < disNum) {
// 输入第一个城市时只要判断编号是否正常就行
System.out.println("请输入第一个城市的编号（0 - " + (cityNum-1) + ")");
a = scan.nextInt();
if (a < 0 || a >= cityNum) {
System.out.println("输入参数有误，请重新输入");
continue;
}
// 第二个城市需要判断编号是否正常，是否是不同城市，是否已经录入过
System.out.println("请输入第二个城市的编号（0 - " + (cityNum-1) + ")");
b = scan.nextInt();
if (b < 0 || b >= cityNum) {
System.out.println("输入参数有误，请重新输入");
continue;
}else if (a == b) {
System.out.println("不能输入同个城市，请重新输入");
continue;
}else if (disArray[a][b] != -1) {
System.out.println("这两个城市间的距离已存在，请重新输入");
continue;
}
// 录入距离时判断距离是否为正整数
System.out.println("请输入这两个城市间的距离：");
d = scan.nextInt();
if (d < 0) {
System.out.println("输入参数有误，请重新输入");
continue;
}
// 录入数据到二维数组中
disArray[a][b] = disArray[b][a] = d;
System.out.println("输入成功");
nowDisNum++;
}
// 开始求解，假设每个城市作为起点
for (int i = 0;i < cityNum;i++) {
isPass[i] = true;
nowDisArray[cout++] = i;
huisu(i);
isPass[i] = false;
nowDisArray[--cout] = -1;
}
// 返回结果
if (shortDisArray[0] == -1) {
System.out.println("无法找到经过所有城市一次的最短路径");
}else {
System.out.println("最短路径长度：" + shortDis);
System.out.print("经过的城市编号为：");
for (int i = 0;i < cityNum;i++) {
System.out.print(shortDisArray[i] + " ");
}
System.out.print(shortDisArray[0]);
}
}
}
运行结果：
请输入城市总数：
5
请输入路径总数：
8
请输入第一个城市的编号（0 - 4)
0
请输入第二个城市的编号（0 - 4)
1
请输入这两个城市间的距离：
5
输入成功
请输入第一个城市的编号（0 - 4)
0
请输入第二个城市的编号（0 - 4)
3
请输入这两个城市间的距离：
7
输入成功
请输入第一个城市的编号（0 - 4)
0
请输入第二个城市的编号（0 - 4)
4
请输入这两个城市间的距离：
9
输入成功
请输入第一个城市的编号（0 - 4)
1
请输入第二个城市的编号（0 - 4)
2
请输入这两个城市间的距离：
10
输入成功
请输入第一个城市的编号（0 - 4)
1
请输入第二个城市的编号（0 - 4)
3
请输入这两个城市间的距离：
3
输入成功
请输入第一个城市的编号（0 - 4)
1
请输入第二个城市的编号（0 - 4)
4
请输入这两个城市间的距离：
6
输入成功
请输入第一个城市的编号（0 - 4)
2
请输入第二个城市的编号（0 - 4)
3
请输入这两个城市间的距离：
8
输入成功
请输入第一个城市的编号（0 - 4)
3
请输入第二个城市的编号（0 - 4)
4
请输入这两个城市间的距离：
4
输入成功
最短路径长度：36
经过的城市编号为：0 1 2 3 4 0