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

2021/6/9 12:21:28

本文主要是介绍干货 | 10分钟教你用branch and bound(分支定界)算法求解TSP旅行商问题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

 

OUTLINE

 


- 前言

- 程序说明

- branch and bound过程

- 运行说明

前言

00

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

 

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

 

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

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

 

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

 

程序说明

01

 

整个程序如下所示:

 

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

 

 

其中各个模块说明如下:

 

- 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):

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

 

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

 

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

 

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

 

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

 

  •  
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 。

 

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

 

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

 

运行说明

03

 

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

 

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

 

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

 

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

 

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

 

END



这篇关于干货 | 10分钟教你用branch and bound(分支定界)算法求解TSP旅行商问题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程