阿里在线编程测试题–派送货物，求最短路径

题目

如下图，某物流派送员p，需要给 a、b、c、d. 4个快递点派送包裹，请问派送员需要选择什么样的路线，才能完成最短路程的派送。假设如图派送员的起点坐标(0,0)，派送路线只能沿着图中的方格边行驶，每个小格都是正方形，且边长为1，如p到d的距离就是4。随机输入n个派送点坐标，求输出最短派送路线值（从起点开始完成n个点派送并回到起始点的距离）。

输入示例：
4
2,2
2,8
4,4
7,2
输出：
30

思考过程

我首先想到的是把所有的路径都尝试一次，并求出每条路径的总路程，从中选取最短的一条。核心思想就是全排列。后来想到了用回溯法解决：选择所有送货点中的任意一点作为第一个送货点，然后继续往下搜索下一个点，直到将所有点都走过一遍，到达最后一个点时求出总路程并返回。这里使用了递归，最难的地方在于回溯时要回到什么地方，为了解决这个问题，需要引入一个表示送货点状态的boolean数组，回溯之后靠这个数组进入别的未尝试过的路径。

代码如下

//路径中的点
    static class Point{
        private int x;
        private int y;
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public int getDistance(Point point) {
            return Math.abs(this.x - point.x) + Math.abs(this.y - point.y);
        }
    }

    public static void main(String[] args) {
        int pointNum = 0;
        Scanner sc = new Scanner(System.in);
        pointNum = Integer.parseInt(sc.nextLine().trim());
        Point[] points = new Point[pointNum];
        //设(0,0)点为起点
        start = new Point(0, 0);
        //输入送货点坐标x,y
        for(int i = 0; i < pointNum; i++) {
            String[] locations = sc.nextLine().trim().split(",");
            points[i] = new Point(Integer.parseInt(locations[0]), Integer.parseInt(locations[1]));
        }
        sc.close();
        System.out.println(getMinDistance(pointNum, points));
    }

    private static Point start;
    //将minDistance的初始值设为无穷大，即没找到最短路径
    private static int minDistance = Integer.MAX_VALUE;

    /**
     * @param pointNum:送货点数量
     * @param points:送货点数组
     */
    public static int getMinDistance(int pointNum, Point[] points) {
        int distance = 0;
        //flag数组用于标记该点是否已搜索
        boolean[] flag = new boolean[pointNum];
        //分别将各个点作为第一个送货点进行搜索
        for(int i = 0; i < pointNum; i++) {
            distance += start.getDistance(points[i]);
            DFSSearch(i, distance, flag, points, 1, pointNum);
        }
        return minDistance;
    }

    /**
     * 
     * @param index:当前点
     * @param distance:当前路径长度
     * @param flag:是否在该路径的标志，true为在，false为不在
     * @param points:送货点数组
     * @param level:搜索深度，即搜索到第几个点
     * @param allLevel:搜索总深度，一共要搜索几个点
     */
    private static void DFSSearch(int index, int distance, boolean[] flag, Point[] points, int level, int allLevel) {

        if(level == allLevel) {
            //搜索到最后一个点时计算其与起点的距离，求得整个送货过程的总路程
            distance += start.getDistance(points[index]);
            if(distance < minDistance) {
                minDistance = distance;
            }
            return;
        }

        //将当前路径标记为true,表示在当前路径上
        flag[index] = true;
        for(int i = 0; i < points.length; i++) {
            //前往下一条没有被搜索过得路径
            //条件为该路径的flag为false
            if(!flag[i]) {
                //先计算当前这个点与即将前往的下一个点之间的距离
                distance += points[index].getDistance(points[i]);
                //继续往下搜索
                //此时搜索深度+1
                DFSSearch(i, distance, flag, points, level+1, allLevel);
            }
        }

        //当前点已搜索完，退出当前路径，返回上一个点
        //将当前路径的flag设为false
        flag[index] = false;
    }