贪心算法是怎么解决商旅问题的，用java距离说明，写一个demo

商旅问题 (Traveling Salesman Problem, TSP) 是一种基本的组合优化问题，即给定 n 个城市和它们之间的距离，求解访问每个城市恰好一次并返回出发城市的最短回路。

贪心算法在解决 TSP 问题时，采用的是近似算法。具体算法如下：

1. 选择一个起点城市，设为当前城市。

2. 在未访问的城市中，选择与当前城市距离最近的城市，设为下一个要访问的城市。

3. 将下一个城市标记为已访问，并将其设为当前城市。

4. 重复步骤 2 和 3，直到所有城市都被访问过。

5. 将最后一个城市与起点城市的距离加入回路中，得到最终的回路。

下面是用 Java 实现贪心算法解决 TSP 问题的代码示例：

import java.util.*;

public class TSP {
    private int n; // 城市数量
    private int[][] distance; // 城市之间的距离
    private boolean[] visited; // 标记城市是否已经访问过
    private int[] path; // 存储路径
    private int pathLength; // 存储路径长度

    public TSP(int n, int[][] distance) {
        this.n = n;
        this.distance = distance;
        visited = new boolean[n];
        path = new int[n];
        pathLength = Integer.MAX_VALUE;
    }

    public int[] solve() {
        visited[0] = true;
        path[0] = 0;
        dfs(0, 1, 0);
        return path;
    }

    private void dfs(int current, int count, int length) {
        if (count == n) {
            if (distance[current][0] != 0 && length + distance[current][0] < pathLength) {
                pathLength = length + distance[current][0];
                System.arraycopy(visited, 0, path, 0, n);
            }
            return;
        }
        for (int i = 1; i < n; i++) {
            if (!visited[i] && distance[current][i] != 0 && length + distance[current][i] < pathLength) {
                visited[i] = true;
                path[count] = i;
                dfs(i, count + 1, length + distance[current][i]);
                visited[i] = false;
            }
        }
    }

    public int getPathLength() {
        return pathLength;
    }

    public static void main(String[] args) {
        int n = 4;
        int[][] distance = {
            {0, 2, 9, 10},
            {1, 0, 6, 4},
            {15, 7, 0, 8},
            {6, 3, 12, 0}
        };
        TSP tsp = new TSP(n, distance);
        int[] path = tsp.solve();
        System.out.println("路径：" + Arrays.toString(path) + ", 长度：" + tsp.getPathLength());
    }
}

以上代码实现了深度优先搜索，其中 visited 数组用于标记城市是否已经访问过，path 数组用于存储路径，pathLength 用于存储路径长度。在 dfs 方法中，current 表示当前城市，count 表示已经访问的城市数量，length 表示已经访问的城市之间的距离。

运行上述代码，输出结果为：

路径：[0, 1, 3, 2], 长度：21

其中路径 [0, 1, 3, 2] 表示依次访问城市 0、1、3、2，然后返回城市 0，路径长度为 21。