旅行售货员问题

问题描述

• 给定一组城市和每对城市之间的距离，访问每个城市一次，然后返回起点，求最短的可能路线。

算法设计

• 将城市 0（假设为第 0 个节点）作为起点和终点，由于路线是循环的，所以我们可以把任何一点作为起点。
• 以广度优先的原则开始从源到相邻节点的遍历。
• 计算每次遍历的距离，并通过优先队列将距离小的可扩展节点排在前面，而距离大的节点则不会再被访问变为不可扩展节点，不断更新最小距离存储值，最终以最低距离返回结果。

代码实现

public class test {

    // 优先队列。
    private static final Queue<Node> queue = new PriorityQueue<>((Comparator.comparingInt(o -> o.distance)));
    // 最大值。
//    private static final int MAX = Integer.MAX_VALUE / 2;
    // 邻接矩阵。
    private static final int[][] matrix = {
            {0, 10, 15, 20},
            {10, 0, 35, 25},
            {15, 35, 0, 30},
            {20, 25, 30, 0}
    };

    public static void main(String[] args) {
        System.out.println(TSP());
    }

    private static int TSP() {
        // 初始化list，将所有要去的节点存入list中。
        List<Integer> list = new LinkedList<>();
        for (int i = 1; i < matrix.length; i++) {
            list.add(i);
        }
        Node node = new Node(list, false, 0, 0);
        // 存入初始化节点。
        queue.offer(node);

        while (!queue.isEmpty()) {
            node = queue.poll();
            // 如果队列弹出了一个已经到达终点的节点，那么它的距离就是最短距离。
            if (node.solution) {
                return node.distance;
            }

            list = node.list;
            // 如果已经走完所有的点了，则加上回去0号点的距离，再次载入到优先队列。
            if (list.size() == 0) {
                node.distance = node.distance + matrix[node.begin][0];
                node.solution = true;
                queue.offer(node);
                continue;
            }

            int temp = node.distance;
            // 如果队列中已经更优的节点则抛弃本节点，即分支定界。
            if (queue.stream().anyMatch(node1 -> node1.distance <= temp)) {
                continue;
            }
            // 对于没有走完的节点，对每个节点创建一个新的子节点并放入优先队列。
            for (int end : list) {
                List<Integer> list1 = clone(list, end);
                int distance = node.distance + matrix[node.begin][end];
                Node node1 = new Node(list1, false, end, distance);
                queue.offer(node1);
            }
        }
        return -1;
    }

    private static class Node {
        // 还没有去过的结点。
        List<Integer> list;
        // 是否已经完成了。
        boolean solution;
        // 结点出发位置。
        int begin;
        // 已经走过的距离。
        int distance;

        public Node(List<Integer> list, boolean solution, int begin, int distance) {
            this.list = list;
            this.solution = solution;
            this.begin = begin;
            this.distance = distance;
        }
    }

    private static List<Integer> clone(List<Integer> list, int current) {
        List<Integer> list1 = new LinkedList<>();
        for (Integer temp : list) {
            if (temp != current) {
                list1.add(temp);
            }
        }
        return list1;
    }

}

• TSP()：通过分支限界法计算 TSP 问题。
• static List<Integer> clone(List<Integer> list, int current) ：以 list 为基础，创建不包括本身位置的新 list
  • List<Integer> list：源 list
  • int current：需要排除的节点，即本身的位置。