旅行商问题回溯法用java代码实现

//定义TSP类
public class TSP {
    private int n; //城市数量
    private int[][] distance; //城市之间的距离矩阵
    private boolean[] visited; //记录城市是否被访问过
    private int minDistance = Integer.MAX_VALUE; //最小距离
    private int[] bestPath; //最优路径

    //构造函数
    public TSP(int n, int[][] distance) {
        this.n = n;
        this.distance = distance;
        this.visited = new boolean[n];
        this.bestPath = new int[n];
    }

    //回溯法求解旅行商问题
    public void solve(int startCity) {
        visited[startCity] = true; //标记起点城市已经被访问
        bestPath[0] = startCity; //将起点城市加入最优路径
        backtrack(1, 0, startCity); //从第二个城市开始搜索
    }

    //回溯方法
    private void backtrack(int step, int currentDistance, int currentCity) {
        if (step == n) { //已经访问完所有城市
            currentDistance += distance[currentCity][bestPath[0]]; //计算回到起点城市的距离
            if (currentDistance < minDistance) { //更新最小距离和最优路径
                minDistance = currentDistance;
                System.arraycopy(bestPath, 0, bestPath, 0, n);
            }
            return;
        }
        for (int i = 0; i < n; i++) {
            if (!visited[i]) { //如果城市没有被访问过
                int newDistance = currentDistance + distance[currentCity][i]; //计算到这个城市的距离
                if (newDistance < minDistance) { //如果新的距离小于最小距离
                    visited[i] = true; //标记城市已经被访问
                    bestPath[step] = i; //将城市加入最优路径
                    backtrack(step + 1, newDistance, i); //继续搜索下一个城市
                    visited[i] = false; //回溯，将城市标记为未访问
                }
            }
        }
    }
}

--相关问题--:
1. 什么是旅行商问题？
2. 除了回溯法，还有哪些方法