本文章知识来自于微信公众号“数据魔术师”，侵删。

感谢“数据魔术师”团队。

上一篇文章介绍了TSP问题、分支定界法、one-tree算法，有兴趣可以返过去看一下。

分支定界法解TSP问题（one-tree算法定界）附java代码

还有一篇文章介绍了匈牙利算法，有java代码。本文代码在运用匈牙利算法分支定界时，会调用这其中的代码。

匈牙利算法解指派问题（Java代码）

TSP问题转化为匈牙利算法可解的形式

将TSP问题的图转化成距离矩阵，便于使用匈牙利算法求此问题，下图中最左边矩阵为转化后的匈牙利矩阵。（为便于观察生成的子回路，原问题中的B-A的距离为2，我将之改为M）

注意：【匈牙利算法求得的解，必定可以构成闭环】

定界

初始化上下界：将得到初始解的指作为下界，当前得到的可行解的最小值作为上界。

使用匈牙利算法求此矩阵，对得到的解分情况讨论。得到的解有三种情况：

（1）首先不区分此解是否可行，比较当前解的值与上界的大小，如果大于上界，直接剪支。

（2）理想的情况，得到了可行解，匈牙利算法的解可以构成TSP回路。并且将此解的值小于上界，就用当前解的值替换上界，以当前解作为当前最优解。

（3）如果得到不可行解，且此解的值小于上界，就在这个分支的基础上，继续分支定界操作。

 对例题中的TSP问题进行求解。左图为原图转化的匈牙利矩阵。中间图为求得得解。右图为此解结果在图中的显示。

求得的解为非可行解，属于情况（3）。下面进行分支操作。

分支

在求得得解中，有三个子闭环：（G-H-G）、（F-E-F）、（B-C-A-D-B）。

选取边数最少的子闭环，枚举其中的边进行分支。我选取（G-H-G）环，对边（G-H）和（H-G）进行分支。

（选取边数最少的子闭环是为了降低求解的计算量。假设当图中有两个闭环时，一个子闭环3条边，一个子闭环5条边，如果选取3条边的子闭环进行分支，只需分三个支，比分五个支降低了计算量。）

 再对分支后的边进行定界分支操作。

---

java代码

（1）所需变量

static int n; // 点的个数
static int[][] dis; // 点之间的距离矩阵
static ArrayList<Arc> arcs = new ArrayList<>(); // 存储图中所有的边
static ArrayList<Arc> best_tree = new ArrayList<>(); // 迄今为止找到最佳的解
static int up = Integer.MAX_VALUE, low = 0; // 上下界
static int front[]; // hungary算法中，front[i]表示i节点前面的节点
static boolean check[][]; // check[i][j]，避免在一条到底的分支定界中，重复定界几条边
static boolean vis[]; // 在匈牙利算法中使用的到，vis[i]标记此点i是否被访问过

（2）主函数

            // 先使用匈牙利算法求得一个解，以此作为下界
            ArrayList<HashMap<Integer, Integer>> sol = hungary.exeHungary(dis);
            // 因为会得到不止一个解，所以可以对得到的解进行分别处理
            for (int i = 0; i < sol.size(); i++) {
                // 1.将hungary算法求得的解，转化成 front数组，并将当前解的值计算为下界
                Set<Integer> keys = sol.get(i).keySet();
                for (Integer k : keys) {
                    front[k - 1] = sol.get(i).get(k) - 1;
                }
                int now = 0;
                for (int j = 0; j < front.length; j++) {
                    now += dis[front[j]][j];
                }
                if (now > low) {
                    low = now;
                }

                // 2.开始进行分支操作，找到解中最小的闭环，进行分支操作
                ArrayList<Arc> arc_circle = get_circle();

                // 3.如果找的最小闭环中有所有的点，就说明此时已经找到了最优解，直接返回
                if (arc_circle.size() == n) {
                    System.out.println("最优解：");
                    feasibleTSP(arc_circle);
                    up = now;
                    return;
                }

                // 4.分支定界（以最小闭环中的边为分支条件）
                for (int j = 0; j < arc_circle.size(); j++) {
                    initX();
                    branch_and_bound_hungary(arc_circle.get(j));
                    // 这里为什么还要（我感觉这个意思就是说，一个闭环中，剪除一个边就行了，最好是让现成的两个边集合到一起）
                    check[arc_circle.get(j).getFrom()][arc_circle.get(j).getTo()] = true;
                }
                // 5.输出最优解
                System.out.println("最优解：");
                feasibleTSP(best_tree);
            }

（3）hungary.exeHungary(dis)

这个函数写在了hungary类中，也就是匈牙利算法的代码中。

首先将距离矩阵 dis 转换成匈牙利算法可以处理的问题，再通过匈牙利算法求解之，返回可行解。

    public static ArrayList<HashMap<Integer, Integer>> exeHungary(int[][] dis) throws InterruptedException {
        // 转化为求解的问题对象
        int[][] newDis = new int[dis.length + 1][dis.length + 1];
        for (int i = 0; i <= dis.length; i++) {
            newDis[i][0] = 0;
            newDis[0][i] = 0;
        }
        for (int i = 1; i <= dis.length; i++) {
            for (int j = 1; j <= dis.length; j++) {
                newDis[i][j] = dis[i - 1][j - 1];
            }
        }
        Problem p = new Problem(newDis);

        // 执行匈牙利算法
        solution.clear();
        zeroOut(p);
        circle_zero(p);

        return solution;
    }

 （4）get_circle()

返回匈牙利算法得到的解中，最小的闭环的边的集合。

    public static ArrayList<Arc> get_circle() {
        // 假设：将匈牙利算法求得的所有匹配连接到一起，必定得到闭环。一个或多个闭环。
        ArrayList<Arc> tmp = new ArrayList<>();
        ArrayList<Arc> ans = new ArrayList<>();
        // 起初所有点都未被放问过
        for (int i = 0; i < vis.length; i++) {
            vis[i] = false;
        }
        // 遍历每个节点，将所有边都加入进去
        for (int i = 0; i < n; i++) {
            if (vis[i]) continue; // 如果已经访问过了，就跳过
            tmp.clear();
            int t = i;
            // 闭环
            while (!vis[t]) {
                vis[t] = true;
                tmp.add(new Arc(front[t], t, dis[front[t]][t]));
                t = front[t];
            }
            // vis[t] = true; // 这个可能是非必要的
            // 返回最小的一个闭环。这样既可以将最小的闭环融入到大闭环中，减少计算量。（如果是打破大闭环，会比打破大闭环计算量大）
            if (tmp.size() < ans.size() || ans.size() == 0) ans = (ArrayList<Arc>) tmp.clone();
        }
        return ans;
    }

（5）branch_and_bound_hungary(Arc a)

对边a进行禁忌分支，也就是在匈牙利算法的求解矩阵中，将这条边的成本设置为无穷大。

    public static void branch_and_bound_hungary(Arc a) throws InterruptedException {
        // 1.先分支禁忌这条边
        x[a.getFrom()][a.getTo()] = true;
        // System.out.println("分支禁忌边：<" + a.getFrom() + "," + a.getTo() + ">");

        // 2.重新生成匈牙利成本矩阵 newDis
        int[][] newDis = new int[n][n];
        for (int i = 0; i < n; i++) {
            front[i] = i;
            for (int j = 0; j < n; j++) {
                // 1.如果这条边检查过
                // 不明白为什么这里需要让距离等于0呢
                if (check[i][j]) {
                    newDis[i][j] = 0;
                    continue;
                }
                // 2.如果这条边被分支禁忌了
                if (x[i][j]) {
                    newDis[i][j] = Integer.MAX_VALUE;
                }
                // 3.这条边没有他特殊的操作
                else {
                    newDis[i][j] = dis[i][j];
                }
            }
        }
        System.out.println("新生成的矩阵：");
        show(newDis);

        // 3.hungary算法计算
        ArrayList<HashMap<Integer, Integer>> sols = hungary.exeHungary(newDis);
        // System.out.println("完成一次运算");
        for (int i = 0; i < sols.size(); i++) {
            // 3.1 HashMap类型的解转化成front[]数组类型
            Set<Integer> keys = sols.get(i).keySet();
            for (Integer k : keys) {
                front[sols.get(i).get(k) - 1] = k - 1;
            }

            // 3.2 计算求解的值，用于定界
            int now = 0;
            for (int j = 0; j < front.length; j++) {
                now += dis[front[j]][j];
            }
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    if (check[j][k]) {
                        now += dis[j][k];
                    }
                }
            }
            // 3.3 继续分支处理
            ArrayList<Arc> aaa = get_circle();
            // 3.3.1 如果大于上界，剪支
            if (now > up) {
                System.out.println("此解大于上界");
                x[a.getFrom()][a.getTo()] = false;
                return;
            }
            // 3.3.2 如果找到了一个完整的闭环，停止计算，到此为止
            if (aaa.size() == n) {
                // show1(aaa);
                System.out.println("此解为当前最优");
                if (feasibleTSP(aaa)) {
                    best_tree = (ArrayList<Arc>) aaa.clone();
                }
                x[a.getFrom()][a.getTo()] = false;
                up = now;
                return;
            }
            // 3.3.3 如果还有子环存在，继续分支定界
            else {
                for (int j = 0; j < aaa.size(); j++) {
                    System.out.println("禁忌了边：" + "<" + a.getFrom() + "," + a.getTo() + ">，后，继续禁忌" + "<" + aaa.get(j).getFrom() + "," + aaa.get(j).getTo() + ">");
                    branch_and_bound_hungary(aaa.get(j));
                    check[aaa.get(j).getFrom()][aaa.get(j).getTo()] = true;
                }
                for (int j = 0; j < aaa.size(); j++) {
                    check[aaa.get(j).getFrom()][aaa.get(j).getTo()] = false;
                }
            }
        }
    }

---

---

至此，对于分支定界法解TSP问题的两种定界方法：one-tree与hungary。就已经讨论完了。

需要java代码可以发私信，无偿。

感谢“数据魔术师”团队。