回溯法货郎问题java实现

以下是Java实现回溯法解决货郎问题的代码：

public class TSPBacktracking {
    private int n; // 城市数量
    private int[][] distance; // 城市距离矩阵
    private boolean[] visited; // 标记城市是否被访问
    private int minDistance = Integer.MAX_VALUE; // 最小距离
    private int[] path; // 记录路径

    public TSPBacktracking(int[][] distance) {
        this.distance = distance;
        this.n = distance.length;
        this.visited = new boolean[n];
        this.path = new int[n];
    }

    public void tsp(int start, int depth, int curDistance) {
        if (depth == n) { // 所有城市都已经访问过
            curDistance += distance[path[n-1]][start]; // 加上回到起点的距离
            if (curDistance < minDistance) {
                minDistance = curDistance;
            }
            return;
        }

        for (int i = 0; i < n; i++) {
            if (!visited[i]) { // 如果城市没有被访问
                visited[i] = true;
                path[depth] = i;
                tsp(start, depth+1, curDistance+distance[path[depth-1]][i]);
                visited[i] = false; // 回溯
            }
        }
    }

    public int getMinDistance() {
        return minDistance;
    }

    public static void main(String[] args) {
        int[][] distance = new int[][] {
            {0, 2, 9, 10},
            {1, 0, 6, 4},
            {15, 7, 0, 8},
            {6, 3, 12, 0}
        };

        TSPBacktracking tsp = new TSPBacktracking(distance);
        tsp.visited[0] = true; // 从第一个城市开始
        tsp.path[0] = 0;
        tsp.tsp(0, 1, 0);
        System.out.println("最短距离为：" + tsp.getMinDistance());
    }
}

这里使用邻接矩阵存储城市之间的距离，然后通过递归实现回溯法搜索所有可能的路径，计算出最短距离。需要注意的是，在搜索过程中需要记录已经访问过的城市和当前路径的长度，以便进行回溯和更新最优解。