branchandbound（分⽀定界）算法求解TSP旅⾏商问题转载⾃：
整个程序如下所⽰：
其中各个模块说明如下：cherishing
- Timer：计时⽤。
- TSPInstanceReader：TSPLIB标准算例读取⽤。
-
PriorityQueue：优先队列。
cool什么意思
- Node：搜索树的节点。
- City：保存城市的坐标，名字等。
经典英文台词
- BranchBound_TSP：BB算法主程序。
branch and bound 过程
搜索树的节点定义，节点定义了原问题的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&Path().size()-1;i++){
distance = distance + Path().get(i)][Path().get(i+1)];
}
return distance;
}
其余不重要的接⼝略过。如下：
- path：保存该节点⽬前已经⾛过的城市序列。
- bound：记录该节点⽬前所能达到的最低distance。
- level：记录节点处于搜索树的第⼏层。
-
computeLength：记录当前城市序列的distance。
可能⼤家还没理解节点是如何分⽀的，看⼀张图⼤家就懂了。我们知道TSP问题的⼀个solution是能⽤⼀个序列表⽰城市的先后访问顺序，⽐如现在有4座城市（1，2，3，4）：
图中每个节点的数字序列就是path保存的。⼤家都看到了吧，其实分⽀就是⼀个穷枚举的过程。
相对于穷举，分⽀定界算法的优越之处就在于其加⼊了定界过程，在分⽀的过程中就砍掉了某些不可
能的⽀，减少了枚举的次数，⼤⼤提⾼了算法的效率。如下：
分⽀定界算法的主过程如下：
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 = ve();
if (v.getBound() < shortestDistance) {
Node u = new Node();
jazzamoru.Level() + 1);
for (int i = 1; i < totalCities; i++) {
path = v.getPath();
if (!ains(i)) {
u.Path());
path = u.getPath();
path.add(i);
u.tPath(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.tPath(temp);
}
}
path = u.getPath();
path.add(0);
u.tPath(path);
if (u.computeLength(distanceMatrix) < shortestDistance) {
shortestDistance = u.computeLength(distanceMatrix);// implementally
shortestPath = u.getPath();
}
} el {
u.tBound(computeBound(u, distanceMatrix, cities));
//u.getBound()获得的是不完整的解，如果⼀个不完整的解bound都⼤于当前最优解，那么完整的解肯定会更⼤，那就没法玩了。 //所以这⾥只要u.getBound() < shortestDistance的分⽀
if (u.getBound() < shortestDistance) {
queue.add(u);
queueCount++;
}
el {
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 + (i)][(i + 1)];
}
int last = (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 (!(i))) {
for (int j = 0; j < cities.size(); j++) {
if (i != j && !(j))) {
if (min > distanceMatrix[i][j]) {
min = distanceMatrix[i][j];
}
}
}honey中文意思
}
if (min != Integer.MAX_VALUE)
bound = bound + min;
}
//出去的
min = Integer.MAX_VALUE;
for (int i = 0; i < cities.size(); i++) {
if (/*(i) != last && */!ains(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 。 （与剩余站有关）
注意这两个是可以不相等的。
