| 分支定界法解TSP问题（one | 您所在的位置：网站首页 › 求解整数规划的方法是 › 分支定界法解TSP问题（one |
分支定界法解TSP问题（one
|
文章的知识来自于微信公众号“数据魔术师”，侵删。 感谢“数据魔术师”团队。 针对分支定界法解TSP问题，有两种常见的定界方法：one-tree算法和匈牙利算法。这篇文章介绍one-tree算法定界，求TSP问题。 首先简单说一下分支定界法的基本思想。 分支定界法假设有最小化的整数规划问题A，它相应的线性松弛(LP relaxation)规划问题为B。 若要求解问题A，先从解问题B开始，若其最优解不符合A的整数条件，那么B的最优目标函数值必是A的最优目标函数值 z* 的下界，记作 Z ；而 A 的任意可行解的目标函数值将是 z* 的一个上界 z 。分枝定界法就是将 A 的可行域分成子区域的方法，逐步增大 Z 和减小z ，最终求到最优解 z* 。 最小化整数规划问题中，下界初始化为最小的值，也就是B问题的函数值，上界初始化为最大的值。 通常，把全部可行解空间反复地分割为越来越小的子集，称为分枝；并且对每个子集内的解集计算一个目标下界（对于最小值问题），这称为定界。在每次分枝后，可能会得到三种情况：（1）剪支掉超出上界的子集。（2）剪支掉不满足整数条件的解的子集。（3）满足整数条件且优于当前上界，用当前解替换上界。 这就是分枝定界法的主要思路。 当使用分支定界法处理TSP问题时，会与处理普通的整数线性规划问题略有不同。本文介绍one-tree算法定界情况的求解思想，并附有java代码。 下面先介绍一下TSP问题，和例题。 TSP问题TSP问题中有ABCDEFG七个点，已知这七个点之间的距离，未联线的访问点表示无法到达。 目标为要找到一条最短路径，遍历这七个点，每个点只遍历一次。 访问点之间的关系图如下：
我们使用分支定界法求解此问题，使用分支定界法的核心在于分支和定界。 本文中介绍两种TSP常用的定界方法：Hunagry方法和one-tree方法。 one-tree算法 定界one-tree算法用于分支后的定界计算。在图中，除了one访问点外，对所有剩下的所有访问点通过Kruskal算法求最小生成树，最后再用两条边将one访问点和最小生成树进行联接（一条边为进入最小生成树，一条边走出最小生成树，构造one节点与最小生成树的回路），最终得到的one-tree作为一个解。 本问题是最小化整数规划问题，将下界初始化为最小值，将上界初始为无穷大的值。 通过one-tree算法得到的解有三种情况： （1）先不区分得到的解是否为TSP可行解，判断此解大小与上界的大小关系，如果大于上界则直接剪支。 （2）当前解为可行解，且小于上界，则用当前解替换当前最优解，将当前解的值作为上界的值。 （3）当前解为不可行解，且小于上界，在当前解分支的基础上继续进行分支定界操作。 分支当定界得到的解为情况（3）时，进行分支操作。 one-tree算法求得的解，会出现度大于等于3的点，显然当出现这种点的时候，此解必定是不可行解。 找到one-tree中所有度大于等于3的节点的边，枚举并将禁忌这些边作为分支条件，依次进行分支，继续进行定界。 【一棵one-tree是一个TSP的可行解的充要条件是：one-tree中所有节点的度(degree)均为对2。】 下面使用one-tree方法求TSP问题，对例题进行讲解 将A节点视为one节点，对节点【B、C、D、E、F、G、H】构造最小生成树，再使用两条线将A节点与最小生成树连接，构造A与最小生成树的回路，得到一个初始解one-tree。 将初始解的值作为下界，将上界初始为无穷大的值。 如下图中红色边为构造的最小生成树，蓝色边为A节点与此最小生成树联接的边。红色与蓝色的边共同构成one-tree。
得到的one-tree中，F点和C点为度大于等于3的边， 他们的边集合为：（F-G），（F-E），（F-C），（C-B），（C-D）。 在分支过程中，需要对这五条边进行分支操作。所谓对某条边分支，指的是在后续的求解过程中禁忌这条边。 下图中画出了对（F-G）、（F-E）、（F-C）这三条边分支后的结果，其中双斜杠划去的边表示对这条边禁忌分支。
对分支后的解进行判断，有三种情况： （1）如果找到了一个TSP回路可行解，将当前解的值与上界值进行比较，如果小于上界的值，就用当前解的值作为上界，如果大于上界的值，就将这个支剪掉。 （2）如果当前解不可行，但是大于上界，直接剪支。 （3）如果当前解不可行，但是小于上界，对这个解继续进行分支定界处理。 显然，上面列举的三种分支情况都为非可行解，且小于上界，应该在上述分支的基础上继续进行分支定界计算。 java代码 （1）用到的变量 static int n; // 点的个数 static int[][] dis; // 点之间的距离矩阵 static ArrayList arcs = new ArrayList(); // 存储图中所有的边 static ArrayList best_tree = new ArrayList(); // 迄今为止找到最佳的解 static int up = Integer.MAX_VALUE, low = 0; // 上下界 static int front[]; // Kruscal算法中，front[i]表示在图中i点的根节点 static boolean x[][]; // x[i][j]表示边[i->j]是否使用（true表示此边作为分支条件被禁忌了，false表示此边不被禁忌） static boolean check[][]; // check[i][j]，避免在一条到底的分支定界中，重复定界几条边 static boolean flag = false; // 标志，通过kruscal算法得到的one-tree是否可行 （2）主函数 // 0.读取算例数据 read(); // 1.初始化x矩阵，所有边都未被禁忌 initX(); // 2.计算边的集合，并排序 for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { addArc(i, j, dis[i][j]); } } Sort(arcs); // 根据边的长度，从小到大进行排序 // 3.通过Kruskal计算one-tree：deg ArrayList deg = kruskal(); low = calculate(deg); // 其值初始化为下界 // 4.找出度大于等于3的点的边的集合：deg_3 ArrayList deg_3 = degree(deg); // 5.进行分支定界操作（对所有度大于等于3的边） for (int i = 0; i < deg_3.size(); i++) { // 5.1初始化解 initX(); if (check[deg_3.get(i).getFrom()][deg_3.get(i).getTo()]) continue; // 5.2分支定界处理 branch_and_bound_tree(deg_3.get(i)); check[deg_3.get(i).getFrom()][deg_3.get(i).getTo()] = true; } // 6.输出最优解 System.out.println("*************** 得到的最优解：" + up + " ***************"); show1(best_tree); feasibleTSP(best_tree); （3）Kruskal：求得one-tree public static ArrayList kruskal() { flag = false; ArrayList tree = new ArrayList(); // 1.初始化所有点的根节点为其本身（起初每个点都是孤立的） for (int i = 0; i < front.length; i++) { front[i] = i; } // 2.构造不包含节点1的最小生成树 int cnt = 0; // 用于记录最小生成树中边的个数 for (int i = 0; i < arcs.size(); i++) { // 遍历边 // 2.1 如果这个边包含节点1了，pass掉 if (arcs.get(i).getFrom() == 0 || arcs.get(i).getTo() == 0) continue; // 2.2 如果此边已经作为剪支被禁忌了 if (x[arcs.get(i).getFrom()][arcs.get(i).getTo()]) continue; // 2.3 在最小生成树中添加边（要求将所有的点都包含在连通图中） int fx = getFront(arcs.get(i).getFrom()); int fy = getFront(arcs.get(i).getTo()); if (fx != fy) { front[fy] = fx; cnt++; tree.add(new Arc(arcs.get(i))); } } // 若满足以下条件，则说明无可行解（因为此时找到的边的个数不足以联接所有的点） if (cnt < n - 2) { flag = true; } // 3.添加与1相连的两条边（将one节点与第2步中的最小生成树联接，构建one-tree） int min_1 = Integer.MAX_VALUE, min_2 = Integer.MAX_VALUE; int id1 = -1, id2 = -1; // 表示与1相连的两个点的编号，id1为最优的点，id2为次优的点 boolean flag1 = false, flag2 = false; // true表示：1 -> 连通图 for (int i = 1; i < n; i++) { // 如果这个点与0相连的边被分支禁忌了 if (x[0][i] == true || x[i][0] == true) continue; // 先计算从0到i if (dis[0][i] < min_1) { min_2 = min_1; min_1 = dis[0][i]; id2 = id1; id1 = i; flag2 = flag1; flag1 = true; } else { if (dis[0][i] < min_2) { min_2 = dis[0][i]; id2 = i; flag2 = true; } else { // 再计算从i到0 if (dis[i][0] < min_1) { min_2 = min_1; min_1 = dis[i][0]; id2 = id1; id1 = i; flag2 = flag1; flag1 = false; } else if (dis[i][0] < min_2) { min_2 = dis[i][0]; id2 = i; flag2 = false; } } } } // 将找出的两条边添加进去（必定是从0指向id，所以第二个要加取反） tree.add(new Arc((flag1 ? 0 : id1), (flag1 ? id1 : 0), dis[(flag1 ? 0 : id1)][(flag1 ? id1 : 0)])); // 0指向 最小生成树 tree.add(new Arc((!flag2 ? 0 : id2), (!flag2 ? id2 : 0), dis[(!flag2 ? 0 : id2)][(!flag2 ? id2 : 0)])); // 最小生成树 指回0 return tree; } （4）calculate：计算one-tree的总路径成本 public static int calculate(ArrayList a) { int ans = 0; for (int i = 0; i < a.size(); i++) { ans += dis[a.get(i).getFrom()][a.get(i).getTo()]; } return ans; } （5）degree：返回度大于等于3的边的集合 public static ArrayList degree(ArrayList a_tree) { ArrayList a = new ArrayList(); // 1.计算每个节点的度 int du[] = new int[n]; for (int i = 0; i < n; i++) { du[i] = 0; } for (int i = 0; i < a_tree.size(); i++) { du[a_tree.get(i).getFrom()]++; du[a_tree.get(i).getTo()]++; } // 2.找出度大于等于3的边，放入到集合a中 for (int i = 0; i < n; i++) { if (du[i] >= 3) { for (int j = 0; j < a_tree.size(); j++) { if (a_tree.get(j).getFrom() == i || a_tree.get(j).getTo() == i) { if (!a.contains(a_tree.get(j))) { a.add(new Arc(a_tree.get(j))); // 这里可能会出现重复的边 } } } } } return a; } （6）分支定界处理（核心）对边 a 进行分支，也就是禁忌边 a，继续进行定界操作。 public static void branch_and_bound_tree(Arc a) { // 1.禁忌分支的边a，a后面的计算中就不能用了 x[a.getFrom()][a.getTo()] = true; // 2.计算one-tree ArrayList tmp1 = kruskal(); // 3.判断是否为可行解，如果是不可行解，就直接剪支（flag=true的时候表示非可行解） if (flag) { System.out.println("-----------------不可行解----------------"); x[a.getFrom()][a.getTo()] = false; show1(tmp1); return; } // 4.计算度大于等于3的点的边的集合 ArrayList tmp = degree(tmp1); // 5.定界操作 int now = calculate(tmp1); // 当前操作的值 // 5.1 如果当前值大于上界，那就直接剪支，不往下算了 if (now > up) { x[a.getFrom()][a.getTo()] = false; System.out.println("-----------------超出上界----------------"); show1(tmp1); return; } // 5.2 如果此时已经得到了TSP回路，则可以将此TSP回路的值作为上界 if (tmp.size() == 0) { if (up > now && feasibleTSP(tmp1)) { up = now; copy(tmp1); System.out.println("----------------TSP可行解-----------------"); } else { System.out.println("---------------TSP非可行解----------------"); } show1(tmp1); feasibleTSP(tmp1); x[a.getFrom()][a.getTo()] = false; return; } // 5.3 其余情况下继续分支操作 for (int i = 0; i < tmp.size(); i++) { if (check[tmp.get(i).getFrom()][tmp.get(i).getTo()]) continue; branch_and_bound_tree(tmp.get(i)); check[tmp.get(i).getFrom()][tmp.get(i).getTo()] = true; } // 6.当分支操作到底后，需要将分支的边都解除禁忌 for (int i = 0; i < tmp.size(); i++) { check[tmp.get(i).getFrom()][tmp.get(i).getTo()] = false; } x[a.getFrom()][a.getTo()] = false; }上面就是全部讨论内容了，代码根据c++代码改写而来。因为篇幅问题，没有将所有代码都粘贴上来，有需要的可以联系我，无偿。 后面还会有一篇使用匈牙利算法的分支定界法，解TSP问题，有需要的朋友可以看一看那篇。 欢迎批评指正。 |
【本文地址】