7.1 题目描述

实现旅行销售商问题的分支限界算法。

7.2 程序使用说明

  1. 输入城市数n；
    2. 输入各城市间的距离map[1…n, 1…n]。

    7.3 分析和设计

  2. 思路
    使用分支限界问题解决旅行商问题重点就是限界条件。从一个城市进入下一个城市有多种走法，而不同的选择会产生不同的下界，为了找到最短路径，需要在所有选择中找到下界最小的方案进行下一步的处理，这里可以用优先队列快速确定最小下界的方案。最短路径的下界可以通过计算每一个城市i(1<=i<=n)到最近的两个城市的距离之和si(最快经过城市i)，然后把这n个数字求和除以2(同一条路径即作为了出城的路，又作为了入城的路)得到，当然，如果已经走过一些城市，那么对应的一些路径就被固定，此时Si中就必须包含已确定路径。
    2. 伪代码
    1. FindPath(map[1...n][1...n])
    2. // 输入：各城市的距离map
    3. // 输出：最短路径
    4. // 结点记录的是已走过的城市、下界、未走过的城市
    5. bestNode <- {[1], sum(map), [2,...,n]}
    6. // 根据下界建立的小顶堆
    7. queue
    8. top <- {[1], sum(map), [2,...,n]}
    9. // 计算下界
    10. top.lb <- getLb(map, top)
    11. while top != null and top.lb < bestNode.lb
    12.  if top.leave.length = 0 
    13.      // 所有城市都走过，回到起点
    14.      top.path.add(1)
    15.      top.lb <- getLb(map, top)
    16.      if top.lb < bestNode.lb
    17.          bestNode <- top
    18.  else
    19.      for i <- 0 to top.leave.length do
    20.          path <- top.path
    21.          path.add(top.leave[i])
    22.          leave <- top.leave
    23.          leave.remove(top.leave[i])
    24.          node <- {path, top.lb, leave}
    25.          node.lb <- getLb(map, node)
    26.          queue.add(node)
    27.  top = queue.poll()
    28. return bestNode
  3. 时间复杂度
    在分支限界的解空间树中，一个结点需要从它未走过的城市选择下一个城市，有多少个剩余城市就会生成多少个结点，所以它的空间树的最大结点数为(n-1)(n-2)…*1，所以时间复杂度为O(nn)。

    7.4 测试用例

    | | | | | | | —- | —- | —- | —- | —- | | 1 | n = 2
    Goods = [[0, 1, 1],
    [1, 0, 2],
    [1, 2, 0]] | 路径：a b c a
    最短路径：4 | 路径：a b c a
    最短路径：4 | 通过 | | 2 | n = 5
    Goods = [[0, 3, 1, 5, 8],
    [3, 0, 6, 7, 9],
    [1, 6, 0, 4, 2],
    [5, 7, 4, 0, 3],
    [8, 9, 2, 3, 0]] | 路径：a c e d b a
    总路径：16 | 路径：a c e d b a
    总路径：16 | 通过 |

7.5 源代码（含注释）

  1. import java.util.*;
  2. public class Travel {
  3.     public static void main(String[] args) {
  4.         int[][] map = {{0, 3, 1, 5, 8},
  5.                 {3, 0, 6, 7, 9},
  6.                 {1, 6, 0, 4, 2},
  7.                 {5, 7, 4, 0, 3},
  8.                 {8, 9, 2, 3, 0}};
  9.         System.out.println("各城市距离如下：");
  10.         for (int[] paths : map) {
  11.             for (int path : paths) {
  12.                 System.out.print(path + "\t");
  13.             }
  14.             System.out.println();
  15.         }
  16.         Node bestNode = findPath(map);
  17.         System.out.print("路径：");
  18.         for (Integer location : bestNode.path) {
  19.             System.out.print((char) (location + 'a') + " ");
  20.         }
  21.         System.out.println("\n总路径：" + bestNode.lb);
  22.         System.out.print("请输入城市数：");
  23.         Scanner scanner = new Scanner(System.in);
  24.         int n = scanner.nextInt();
  25.         System.out.println("请输入城市间的距离（n*n的二维数组）：");
  26.         map = new int[n][n];
  27.         for (int i = 0; i < n; i++) {
  28.             for (int j = 0; j < n; j++) {
  29.                 map[i][j] = scanner.nextInt();
  30.             }
  31.         }
  32.         bestNode = findPath(map);
  33.         System.out.print("路径：");
  34.         for (Integer location : bestNode.path) {
  35.             System.out.print((char) (location + 'a') + " ");
  36.         }
  37.         System.out.println("\n总路径：" + bestNode.lb);
  38.     }
  39.     /**
  40.      * 通过分支限界找最短路径，每到一个城市就对应生成一个结点，
  41.      * 在已生成的结点中选择lb(=s/2上取整)最小的结点进行下一步的决策（限界条件），
  42.      * s_i为从城市i经过已确定路径或者最短路径到达的两个城市的路径之和，s=s_1+s_2+...+s_n
  43.      * 所有城市都走过时就得到了一条可行的路径
  44.      *
  45.      * @param map int[0...n-1][0...n-1]各城市间的距离
  46.      * @return
  47.      */
  48.     public static Node findPath(int[][] map) {
  49.         Node bestNode = new Node(new ArrayList<>(), Integer.MAX_VALUE, null);
  50.         // 小顶堆，始终先处理下界最小的结点
  51.         PriorityQueue<Node> queue = new PriorityQueue<>(1, ((o1, o2) -> o1.lb - o2.lb));
  52.         // 生成最初的结点
  53.         List<Integer> path = new ArrayList<>();
  54.         path.add(0);
  55.         List<Integer> leaveLocation = new ArrayList<>();
  56.         for (int i = 1; i < map.length; i++) {
  57.             leaveLocation.add(i);
  58.         }
  59.         Node top = new Node(path, Integer.MAX_VALUE, leaveLocation);
  60.         top.lb = getLb(map, top);
  61.         // 保证优先队列的顶部结点不为空，并且下界小于当前最优，这才有处理的价值
  62.         while (top != null && top.lb < bestNode.lb) {
  63.             if (top.leave.size() == 0) {
  64.                 // 所有城市都走过了，回到起点
  65.                 top.path.add(0);
  66.                 top.lb = getLb(map, top);
  67.                 if (top.lb < bestNode.lb) {
  68.                     bestNode = top;
  69.                 }
  70.             } else {
  71.                 // 把当前结点的所有下一步决策加入优先队列中
  72.                 for (Integer location : top.leave) {
  73.                     path = new ArrayList<>(top.path);
  74.                     path.add(location);
  75.                     leaveLocation = new ArrayList<>(top.leave);
  76.                     leaveLocation.remove(new Integer(location));
  77.                     Node node = new Node(path, Integer.MAX_VALUE, leaveLocation);
  78.                     node.lb = getLb(map, node);
  79.                     queue.add(node);
  80.                 }
  81.             }
  82.             top = queue.poll();
  83.         }
  84.         return bestNode;
  85.     }
  86.     /**
  87.      * 计算当前结点的lb,即最优的进城和出城路径，对于已经过的路径不可避免，剩余的需要是最短路径
  88.      *
  89.      * @param map  int[1...n][1...n]各城市间的距离
  90.      * @param node 当前结点状态
  91.      * @return
  92.      */
  93.     public static int getLb(int[][] map, Node node) {
  94.         int[][] tempMap = new int[map.length][map[0].length];
  95.         // 深度拷贝
  96.         for (int i = 0; i < map.length; i++) {
  97.             tempMap[i] = Arrays.copyOf(map[i], map[i].length);
  98.         }
  99.         // 标记已经过的路径
  100.         int[][] flag = new int[tempMap.length][tempMap[0].length];
  101.         for (int i = 0; i < node.path.size() - 1; i++) {
  102.             // 标记a->b和b->a
  103.             flag[node.path.get(i)][node.path.get(i + 1)] = 1;
  104.             flag[node.path.get(i + 1)][node.path.get(i)] = 1;
  105.         }
  106.         int s = 0;
  107.         // 依次查找两个合适路径，表示进城与出城，如果城市数小于等于2这个循环就有问题
  108.         for (int last = 0; last < 2; last++) {
  109.             for (int i = 0; i < tempMap.length; i++) {
  110.                 // 记录第i个城市到第j个城市的最短路径
  111.                 int min = Integer.MAX_VALUE;
  112.                 int index = -1;
  113.                 // 记录本次查找的是否是已经过的路径
  114.                 boolean isPass = false;
  115.                 for (int j = 0; j < tempMap.length; j++) {
  116.                     if (i == j) {
  117.                         continue;
  118.                     }
  119.                     if (flag[i][j] == 1) {
  120.                         // 如果此路径已经过
  121.                         s += tempMap[i][j];
  122.                         // 下次查找需要排除
  123.                         flag[i][j] = 0;
  124.                         tempMap[i][j] = Integer.MAX_VALUE;
  125.                         isPass = true;
  126.                         break;
  127.                     } else if (min > tempMap[i][j]) {
  128.                         min = tempMap[i][j];
  129.                         index = j;
  130.                     }
  131.                 }
  132.                 if (!isPass) {
  133.                     s += tempMap[i][index];
  134.                     // 下次查找可排除
  135.                     tempMap[i][index] = Integer.MAX_VALUE;
  136.                 }
  137.             }
  138.         }
  139.         return (int) Math.ceil(s * 0.5);
  140.     }
  141. }
  143. import java.util.ArrayList;
  144. import java.util.List;
  145. public class Node {
  146.     // 已经走过的城市
  147.     List<Integer> path;
  148.     // 计算下界
  149.     int lb;
  150.     // 剩余城市
  151.     List<Integer> leave;
  152.     public Node() {
  153.         path = new ArrayList<>();
  154.         lb = Integer.MAX_VALUE;
  155.         leave = new ArrayList<>();
  156.     }
  157.     public Node(List<Integer> path, int lb, List<Integer> leave) {
  158.         this.path = path;
  159.         this.lb = lb;
  160.         this.leave = leave;
  161.     }
  162. }