分支定界算法与TSP

1）分支定界算法：

估价函数：用于确定决策分支的取值界限分支：每一步决策有多种决策方案，每一个方案都构成一个决策分支。定界： 在当前决策情况下，估计当前分支完成全部决策时的最优取值在某个分支完成了全部决策步骤时，更新最优解 剪枝：若某一分支的估计最优取值劣于当前已知的最优解，则该分支没有继续决策的必要

2）TSP：寻找路径权值和最小的哈密顿环路

决策：分n步进行，每步决策选择下一个节点的标号。（理由是哈密顿环路可以写成一个全排列）

估价函数：当前已行进的路径长度，加上回到原点的最短距离（事先由DIJ算出）根据遍历全排列树的方式，有DFS搜索，BFS搜索，以及最优搜索（借助优先队列，每次都从估计最优值最好的分支开始继续计算）

3）应用：

结论在前：借助优先队列的最优搜索方式往往有最少的搜索节点数，但要么和DFS搜索相近，要么节省非常多。由于需要大量空间，该方法非常占内存（30节点的稠密网情况下1.5G还不够），而且速度非常慢，是DFS的数十倍 import org.jetbrains.annotations.NotNull; import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedList; import java.util.PriorityQueue; import java.util.Queue; import java.util.StringJoiner; public class Salesman { static final int M = 10000; // 不邻接 private static int[][] map; // 地图邻接矩阵 static int minest = M; static int nodes; static { // 初始化地图 map = new int[][] { {165, M, M, 779, 330, M}, {200, 499, 158, 437, 837, 672}, {M, 577, M, 780, 379, 611}, {263, M, 805, 877, M, 188}, {749, M, 844, 980, 261, 194}, {592, 847, M, 858, 638, 150} }; } // 回溯查找最优解 public static int[] back_trace() { int[] trace = new int[map.length]; int[] visited = new int[map.length]; int[] record = new int[map.length]; int[] distance = new int[map.length]; _dij(distance, 0); // start at step 0 minest = M; _back_trace(0, 0, 0, 0, trace, visited, record, distance); if (minest == M) { return null; } return record; } private static void _back_trace(int place, int step, int length, int source, int[] trace, int[] visited, int[] record, int[] distance) { ++nodes; // 抵达 visited[place] = 1; trace[step] = place; // 查找到哈密顿回路 if (step == map.length - 1) { // 更新最优解 if (map[place][source] != M) { if (length + map[place][source] < minest) { minest = length + map[place][source]; System.arraycopy(trace, 0, record, 0, map.length); visited[place] = 0; return; } } visited[place] = 0; return; } // 前往下一节点 for (int i = 0; i < map.length; ++i) { if (visited[i] == 0 && map[place][i] != M) { // 剪枝：如果路程超出当前已找到的解，不继续前进 if (length + distance[i] < minest) { _back_trace(i, step + 1, length + map[place][i], source, trace, visited, record, distance); } } } // 离开 visited[place] = 0; } // 分支定界TSP static class Path implements Comparable<Path>, Cloneable { private int current_length; private int step; private int estimate_length; private int[] path; private boolean[] visited; @Override public int compareTo(@NotNull Path o) { return this.estimate_length - o.estimate_length; } @Override protected Object clone() throws CloneNotSupportedException { Path copy; try { copy = (Path) super.clone(); copy.path = path.clone(); copy.visited = visited.clone(); } catch (OutOfMemoryError e) { System.gc(); copy = (Path) super.clone(); copy.path = path.clone(); copy.visited = visited.clone(); } return copy; } } // 优先队列 private static int[] priority_search() throws CloneNotSupportedException { int[] distance = new int[map.length]; _dij(distance, 0); PriorityQueue<Path> paths = new PriorityQueue<>(); // 首次决策，从顶点1出发 Path initial = new Path(); initial.estimate_length = 0; initial.step = 1; initial.path = new int[map.length]; initial.path[0] = 0; initial.visited = new boolean[map.length]; initial.visited[0] = true; paths.offer(initial); // 分支定界 int[] res = null; minest = M; while (!paths.isEmpty()) { ++nodes; Path current = paths.poll(); // 剪枝 if (current.estimate_length > minest) { continue; } // 若到达叶节点,更新最小值 if (current.step == map.length) { int length = current.current_length + map[current.path[current.step - 1]][0]; if (minest > length) { minest = length; res = current.path; } continue; } // 否则进行下一步决策 for (int i = 0; i < map.length; ++i) { if (!current.visited[i] && map[current.path[current.step - 1]][i] != M) { Path next = (Path) current.clone(); next.path[next.step] = i; next.visited[i] = true; next.current_length += map[next.path[next.step - 1]][i]; ++next.step; next.estimate_length = next.current_length + distance[i]; paths.offer(next); } } } return res; } // FIFO private static int[] board_branch() throws CloneNotSupportedException { int[] distance = new int[map.length]; _dij(distance, 0); Queue<Path> paths = new LinkedList<>(); // 首次决策，从顶点1出发 Path initial = new Path(); initial.estimate_length = 0; initial.step = 1; initial.path = new int[map.length]; initial.path[0] = 0; initial.visited = new boolean[map.length]; initial.visited[0] = true; paths.offer(initial); // 分支定界 int[] res = null; minest = M; while (!paths.isEmpty()) { ++nodes; Path current = paths.poll(); // 剪枝 if (current.estimate_length > minest) { continue; } // 若到达叶节点,更新最小值 if (current.step == map.length) { int length = current.current_length + map[current.path[current.step - 1]][0]; if (minest > length) { minest = length; res = current.path; } continue; } // 否则进行下一步决策 for (int i = 0; i < map.length; ++i) { if (!current.visited[i] && map[current.path[current.step - 1]][i] != M) { Path next = (Path) current.clone(); next.path[next.step] = i; next.visited[i] = true; next.current_length += map[next.path[next.step - 1]][i]; ++next.step; next.estimate_length = next.current_length + distance[i]; paths.offer(next); } } } return res; } private static void _dij(int[] distance, int target) { boolean[] visit = new boolean[map.length]; for (int i = 0; i < map.length; ++i) { distance[i] = M; } distance[target] = 0; Queue<Integer> queue = new LinkedList<>(); queue.offer(target); visit[target] = true; while (!queue.isEmpty()) { int v = queue.poll(); for (int j = 0; j < map.length; ++j) { int m = distance[v] + map[j][v]; if (m < distance[j]) { distance[j] = m; } if (!visit[j]) { queue.offer(j); visit[j] = true; } } } } public static void main(String[] args) throws Exception { for (int time = 0; time < 10; ++time) { map = MapFactory.random(10); show(); } for (int time = 0; time < 10; ++time) { map = MapFactory.random(15); show(); } for (int time = 0; time < 10; ++time) { map = MapFactory.random(20); show(); } } private static void show() throws Exception { System.out.println("The map is"); StringJoiner stringJoiner; for (int[] ints : map) { stringJoiner = new StringJoiner(","); for (int j = 0; j < map.length; ++j) { if (ints[j] == M) { stringJoiner.add(" M"); } else { stringJoiner.add(String.format("M", ints[j])); } } System.out.println("{" + stringJoiner + "},"); } long start; nodes = 1; start = System.currentTimeMillis(); int[] patha = back_trace(); System.out.println("回溯法解空间总节点数：" + nodes); System.out.println("耗时：" + (System.currentTimeMillis() - start)); nodes = 0; int a = minest; //int[] pathb = board_branch(); //System.out.println("FIFO分支定界法解空间总结点数：" + nodes); nodes = 0; int b = minest; start = System.currentTimeMillis(); int[] pathc = priority_search(); int c = minest; System.out.println("优先队列解空间总节点数：" + nodes); System.out.println("耗时：" + (System.currentTimeMillis() - start)); if (a == c) { System.out.println("已通过测试方式等价性校验"); } if (pathc != null) { System.out.println("最短哈密顿环路:"); StringJoiner s = new StringJoiner(" > "); for (int value : pathc) { s.add(String.valueOf(value + 1)); } System.out.println(s); System.out.println("最小权值和:" + minest); } else { System.out.println("无哈密顿环路!"); } } }

4）数据生成：

import java.util.Random; public class MapFactory { static final int M = 10000; // 不邻接 private static final Random rand = new Random(); // 随机数发生器 public static int[][] random(int nv) { // 初始化，均未邻接 int[][] map = new int[nv][nv]; for (int i = 0; i < map.length; ++i) { for (int j = 0; j < map.length; ++j) { map[i][j] = M; } } // 生成[4n,7n]内边数 int ne = rand.nextInt((nv << 2) - nv + 1) + (nv << 2); // 生成不重复的边 int i; int j; while (ne-- != 0) { do { i = rand.nextInt(nv); j = rand.nextInt(nv); } while (i == j || map[i][j] != M); map[i][j] = rand.nextInt(901) + 100; } return map; } }