干货 | 10分钟教你用branch and bound(分支定界)算法求解TSP旅行商问题

简介: 干货 | 10分钟教你用branch and bound(分支定界)算法求解TSP旅行商问题

前言

00



前面我们讲了branch and bound算法的原理以及在整数规划模型上的应用代码。但代码都局限于整数规划模型和优化求解器。


我们也说了,branch and bound算法是一个比较通用的算法,可以脱离求解器去求解很多特定的问题的。


所以今天给大家带来一期用分支定界算法求解TSP问题的代码实现,完全脱离求解器,让大家看看该算法的魅力所在。

微信图片_20220421164619.gif


本文代码下载请移步留言区。


程序说明

01


整个程序如下所示:


微信图片_20220421164622.png


其中各个模块说明如下:


- Timer:计时用。

- TSPInstanceReader:TSPLIB标准算例读取用。

- PriorityQueue:优先队列。

- Node:搜索树的节点。

- City:保存城市的坐标,名字等。

- BranchBound_TSP:BB算法主程序。


该branch and bound的搜索树是以优先队列的搜索方式遍历的,结合上期所讲的内容,也可谓是把三种搜索方式的例子都给大家讲了一遍了。


branch and bound过程

02



在此之前,先给大家讲讲最重要的一个点,搜索树的节点定义,节点定义了原问题的solution和子问题的solution。Node节点定义如下:


public class Node {
    private ArrayList<Integer> path;
    private double bound;
    private int level;
    public double computeLength(double[][] distanceMatrix) {
        // TODO Auto-generated method stub
        double distance = 0;
        for(int i=0;i<this.getPath().size()-1;i++){
            distance = distance + distanceMatrix[this.getPath().get(i)][this.getPath().get(i+1)];
        }
        return distance;
    }


其余不重要的接口略过。如下:


- path:保存该节点目前已经走过的城市序列。

- bound:记录该节点目前所能达到的最低distance。

- level:记录节点处于搜索树的第几层。

- computeLength:记录当前城市序列的distance。


可能大家还没理解节点是如何分支的,看一张图大家就懂了。我们知道TSP问题的一个solution是能用一个序列表示城市的先后访问顺序,比如现在有4座城市(1,2,3,4):

微信图片_20220421164624.png

图中每个节点的数字序列就是path保存的。大家都看到了吧,其实分支就是一个穷枚举的过程。


相对于穷举,分支定界算法的优越之处就在于其加入了定界过程,在分支的过程中就砍掉了某些不可能的支,减少了枚举的次数,大大提高了算法的效率。如下:


微信图片_20220421164627.png


分支定界算法的主过程如下:

private static void solveTSP(double[][] distanceMatrix) {
        int totalCities = distanceMatrix.length;
        ArrayList<Integer> cities = new ArrayList<Integer>();
        for (int i = 0; i < totalCities; i++) {
            cities.add(i);
        }
        ArrayList<Integer> path;
        double initB = initbound(totalCities, distanceMatrix);
        Node v = new Node(new ArrayList<>(), 0, initB, 0);
        queue.add(v);
        queueCount++;
        while (!queue.isEmpty()) {
            v = queue.remove();
            if (v.getBound() < shortestDistance) {
                Node u = new Node();
                u.setLevel(v.getLevel() + 1);
                for (int i = 1; i < totalCities; i++) {
                    path = v.getPath();
                    if (!path.contains(i)) {
                        u.setPath(v.getPath());
                        path = u.getPath();
                        path.add(i);
                        u.setPath(path);
                        if (u.getLevel() == totalCities - 2) {
                            // put index of only vertex not in u.path at the end
                            // of u.path
                            for (int j = 1; j < cities.size(); j++) {
                                if (!u.getPath().contains(j)) {
                                    ArrayList<Integer> temp = new ArrayList<>();
                                    temp = u.getPath();
                                    temp.add(j);
                                    u.setPath(temp);
                                }
                            }
                            path = u.getPath();
                            path.add(0);
                            u.setPath(path);
                            if (u.computeLength(distanceMatrix) < shortestDistance) {
                                shortestDistance = u.computeLength(distanceMatrix);// implement
                                shortestPath = u.getPath();
                            }
                        } else {
                            u.setBound(computeBound(u, distanceMatrix, cities));
                            //u.getBound()获得的是不完整的解,如果一个不完整的解bound都大于当前最优解,那么完整的解肯定会更大,那就没法玩了。
                            //所以这里只要u.getBound() < shortestDistance的分支
                            if (u.getBound() < shortestDistance) {
                                queue.add(u);
                                queueCount++;
                            }
                            else {
                                System.out.println("currentBest = "+shortestDistance+" cut bound >>> "+u.getBound());
                            }
                        }
                    }
                }
            }
        }
    }

1. 首先initbound利用贪心的方式获得一个bound,作为初始解。


2. 而后利用优先队列遍历搜索树,进行branch and bound算法。对于队列里面的任意一个节点,只有(v.getBound() < shortestDistance)条件成立我们才有分支的必要。不然将该支砍掉。


3. 分支以后判断该支是否到达最底层,这样意味着我们获得了一个完整的解。那么此时就可以更新当前的最优解了。


4. 如果没有到达最底层,则对该支进行定界操作。如果该支的bound也比当前最优解还要大,那么也要砍掉的,就像林志炫的单身情歌里面唱的一样:每一个单身狗都得砍头。


然后讲讲定界过程,TSP问题是如何定界的呢?

private static double computeBound(Node u, double[][] distanceMatrix, ArrayList<Integer> cities) {
        double bound = 0;
        ArrayList<Integer> path = u.getPath();
        for (int i = 0; i < path.size() - 1; i++) {
            bound = bound + distanceMatrix[path.get(i)][path.get(i + 1)];
        }
        int last = path.get(path.size() - 1);
        List<Integer> subPath1 = path.subList(1, path.size());
        double min;
        //回来的
        for (int i = 0; i < cities.size(); i++) {
            min = Integer.MAX_VALUE;
            if (!path.contains(cities.get(i))) {
                for (int j = 0; j < cities.size(); j++) {
                    if (i != j && !subPath1.contains(cities.get(j))) {
                        if (min > distanceMatrix[i][j]) {
                            min = distanceMatrix[i][j];
                        }
                    }
                }
            }
            if (min != Integer.MAX_VALUE)
                bound = bound + min;
        }
        //出去的
        min = Integer.MAX_VALUE;
        for (int i = 0; i < cities.size(); i++) {
            if (/*cities.get(i) != last && */!path.contains(i) && min > distanceMatrix[last][i]) {
                min = distanceMatrix[last][i];
            }
        }
        bound = bound + min;
        //System.out.println("bound = "+bound);
        return bound;
    }

我们知道,每个节点保存的城市序列可能不是完整的解。bound的计算方式:bound = 当前节点path序列的路径距离 + 访问下一个城市的最短路径距离 + 从下一个城市到下下城市(有可能是起点)的最短路径距离。


比如城市节点5个{1,2,3,4,5}。当前path = {1,2},那么:


- 当前节点path序列的路径距离 = d12

- 访问下一个城市的最短路径距离 = min (d2i), i in {3,4,5}

- 从下一个城市到下下城市(有可能是起点)的最短路径距离=min (dij), i in {3,4,5} , j in {3,4,5,1}, i != j 。


注意这两个是可以不相等的。


微信图片_20220421164629.png

运行说明

03


目前分支定界算法解不了大规模的TSP问题,10个节点以内吧差不多。input里面有算例,可以更改里面的DIMENSION值告诉算法需要读入几个节点。


微信图片_20220421164633.png


更改算例在main函数下面,改名字就行,记得加上后缀。


微信图片_20220421164635.png


感兴趣的同学可以该一下heap大小跑一跑,不过按照上述的分支思路,很容易爆掉的。小编出差在外没有好的电脑就不跑了。


目录
打赏
0
0
0
0
7
分享
相关文章
基于SA模拟退火优化算法的TSP问题求解matlab仿真,并对比ACO蚁群优化算法
本项目基于MATLAB2022A,使用模拟退火(SA)和蚁群优化(ACO)算法求解旅行商问题(TSP),对比两者的仿真时间、收敛曲线及最短路径长度。SA源于金属退火过程,允许暂时接受较差解以跳出局部最优;ACO模仿蚂蚁信息素机制,通过正反馈发现最优路径。结果显示SA全局探索能力强,ACO在路径优化类问题中表现优异。
基于免疫算法的TSP问题求解matlab仿真
旅行商问题(TSP)是一个经典的组合优化问题,目标是寻找经过每个城市恰好一次并返回起点的最短回路。本文介绍了一种基于免疫算法(IA)的解决方案,该算法模拟生物免疫系统的运作机制,通过克隆选择、变异和免疫记忆等步骤,有效解决了TSP问题。程序使用MATLAB 2022a版本运行,展示了良好的优化效果。
基于遗传优化算法的TSP问题求解matlab仿真
本项目使用遗传算法解决旅行商问题(TSP),目标是在四个城市间找到最短路径。算法通过编码、选择、交叉、变异等步骤,在MATLAB2022A上实现路径优化,最终输出最优路径及距离。
基于GA-PSO遗传粒子群混合优化算法的TSP问题求解matlab仿真
本文介绍了基于GA-PSO遗传粒子群混合优化算法解决旅行商问题(TSP)的方法。TSP旨在寻找访问一系列城市并返回起点的最短路径,属于NP难问题。文中详细阐述了遗传算法(GA)和粒子群优化算法(PSO)的基本原理及其在TSP中的应用,展示了如何通过编码、选择、交叉、变异及速度和位置更新等操作优化路径。算法在MATLAB2022a上实现,实验结果表明该方法能有效提高求解效率和解的质量。
决策树算法大揭秘:Python让你秒懂分支逻辑,精准分类不再难
【9月更文挑战第12天】决策树算法作为机器学习领域的一颗明珠,凭借其直观易懂和强大的解释能力,在分类与回归任务中表现出色。相比传统统计方法,决策树通过简单的分支逻辑实现了数据的精准分类。本文将借助Python和scikit-learn库,以鸢尾花数据集为例,展示如何使用决策树进行分类,并探讨其优势与局限。通过构建一系列条件判断,决策树不仅模拟了人类决策过程,还确保了结果的可追溯性和可解释性。无论您是新手还是专家,都能轻松上手,享受机器学习的乐趣。
64 9
决策树算法大揭秘:Python让你秒懂分支逻辑,精准分类不再难
【8月更文挑战第2天】决策树算法以其直观性和解释性在机器学习领域中独具魅力,尤其擅长处理非线性关系。相较于复杂模型,决策树通过简单的分支逻辑实现数据分类,易于理解和应用。本示例通过Python的scikit-learn库演示了使用决策树对鸢尾花数据集进行分类的过程,并计算了预测准确性。虽然决策树优势明显,但也存在过拟合等问题。即便如此,无论是初学者还是专家都能借助决策树的力量提升数据分析能力。
59 4
基于禁忌搜索算法的TSP路径规划matlab仿真
**摘要:** 使用禁忌搜索算法解决旅行商问题(TSP),在MATLAB2022a中实现路径规划,显示优化曲线与路线图。TSP寻找最短城市访问路径,算法通过避免局部最优,利用禁忌列表不断调整顺序。关键步骤包括初始路径选择、邻域搜索、解评估、选择及禁忌列表更新。过程示意图展示搜索效果。
|
7月前
|
模拟退火算法求解TSP问题(python)
模拟退火算法求解TSP问题(python)
105 0
算法(分治、贪心、dp、回溯、分支限界)总结
算法(分治、贪心、dp、回溯、分支限界)总结
|
8月前
|
非启发式算法——旅行商问题(TSP)及其解决算法
非启发式算法——旅行商问题(TSP)及其解决算法
704 0

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等