回溯法和分支定界法可以帮你轻松解决旅行商问题（TSP）

问题描述一个销售员想去几个城市卖货，城市之间的路线（或路费）是已知。需要选择一条从车站出发，经过各个城市，最后回到车站的路线，使总距离（或总旅行费用）最小。本文只考虑4个城市的情况，下面的加权图是问题的转化。由于只有4个城市，如果规定业务员总是从1号城市出发，那么按照排列组合可以得到6种不同的旅行计划，如12341、13241等。在这些排列组合的基础上，很容易画出排列树，也就是问题的解空间树。置换树如下：根据解空间树，可以得到一些有用的信息：树的深度在两个节点之间为5路径上的标识数组表示返回城市1的路径没有体现在城市树，但其实这个距离应该在计算的时候考虑进去。下面分别使用回溯法和分支定界法求解问题，回溯法会给出相应的分支定界法的Python实现代码，将使用优先队列法介绍寻找最优的步骤问题的解决方案。回溯回溯法有点类似于暴力枚举的查找过程。回溯法的基本思想是按照深度优先搜索策略从根节点开始深入搜索解空间树。查找一个节点时，如果该节点可能包含问题，则继续向下查找；否则，返回其祖先节点并尝试其他路径搜索。如果问题只需要找到一个可行的解，那么对问题的解的搜索就可以结束；如果问题是最优解，则需要搜索整个解空间树，得到所有解后，选择最优解作为问题的解。或者在搜索叶节点之前确定该路径不是最优解时，可以对其进行剪枝以节省搜索时间，那么本文的旅行商问题就属于后者。解空间树中除叶节点外的每个节点都可能有多个子节点，而回溯法一次只能搜索一条路径，这也是与分支定界法的区别，这可以更好地帮助理解下面图片解释。下图中的F和L与原来的解空间树略有不同，但对步骤和结果没有影响。首先，已知销售人员从城市1开始。在第一步中，可以不受任何限制地得出任何可行的解决方案。上图路径为12341，F->A距离之和为59，也是当前最优解。由于L只有F的一个子节点，所以只能追溯到C节点，因为C还有另一条路径要查找。可以看出此时搜索到的路径为12431，M->A距离之和为66，此时距离之和大于最优解，所以最优解还是59，至此，节点C的所有子节点的查找结束。然后需要回溯到C的祖先节点B。此时的路径为13241，总距离为25，当前解远小于之前得到的最优解，所以需要更新最优解为25，然后再回到节点D。原理同上。可以看出这张图中的路径比前面几张图多了一个X（叉）。这一步也实现了对数剪枝。依据是什么？因为1号城市到3号城市再到4号城市的距离之和是26，无论怎么走，都不会比当前最优解好，所以Duck不需要继续往下找，直接回溯即可直接地。解空间树剩下的两条路径可以按照上面的方法继续搜索。遍历完所有可行路径后，最终的最优解best_length就是问题的全局最优解，对应的路径就是全局最优路径。下面介绍如何使用代码实现回溯法来搜索问题的最优解。这里省略了定义变量等一些简单的代码，只介绍关键部分。完整代码会在文末给出。首先要做的一定是改造地图。对于这张图，我们可以得到对应的邻接矩阵如下：$$\begin{pmatrix}-1&30&6&4\\30&-1&5&10\\6&5&-1&20\\4&10&20&-1\\\end{pmatrix}$$City_Graph=[[0,0,0,0,0],[0,-1,30,6,4],[0,30,-1,5,10],[0,6,5,-1,20],[0,4,10,20,-1]]path_num=len(City_Graph)isin=[0]*(path_num)#用于检测节点是否加入路径path=[0]*(path_num)#用于存储路径best_path=[0]*(path_num)#用于存储最优路径best_length=100000#初始化求和的最优路径的距离，那么就可以将地图存储在一个二维数组中，可以看到这和图对应的邻接矩阵有些不同，数组的第一行和第一列都是0，为什么要这样做？例如，城市1到城市2的距离为30，对应邻接矩阵中的（1,2）。此时二维数组对应的索引也是(1,2)。填0是为了统一索引。而城市本身的位置在这里填-1，表示没有路径。整个程序可以被一个条件分成两部分，是向下搜索还是向上回溯。如果不先计算剪枝操作，则搜索到的解空间树的叶子节点就是回溯的标志，中间节点通常用于向下搜索操作。.现在的问题是这个条件是什么？对于一个由1,2,3...n组成的解空间树，它是由[1:n]的所有排列组成的。如果我们暂且假设搜索树的深度为t的话，就会出现下面两种情况。当t<=n时，即当前扩展节点位于t-1层：若t-1层扩展节点与t层扩展节点之间存在路径，且[1:t]对应到路径的距离如果和小于最优解，继续向下搜索，否则进行剪枝。当t>n，即当前节点为叶子节点：整条路径只需要回到1号城市即可。此时需要判断是否存在这个环路。如果存在并且得到的距离之和优于当前最优解，则需要更新当前最优解。优秀的解决方案。这两种情况只是说可能有一些抽象，可以结合上面的解空间树来理解。可以看出，t>n是判断是否需要回溯的条件，即本文条件下的t>path_num-1。ift>path_num-1:#搜索到叶子节点foriinrange(1,path_num):#输出当前路径ThePath+=str(path[i])ThePath+='->'temp=int(ThePath.split('->')[3])ifCity_Graph[temp][1]>0:#判断是否存在循环ThePath+='1'#将循环添加到路径中，返回城市1print("Currentpath:%s"%ThePath)back_length=now_length+City_Graph[temp][1]#电路距离也需要加上print("Currentpathsum:%d"%back_length)ifback_lengthpath_num-1的条件为真，则表示即解空间树中的其中一条路径已经搜索完毕，因此需要输出该路径与对应距离的和。但是在输出之前，需要判断地图中这条路径上是否有回1号城的路径。如果有循环，则输出当前搜索路径和对应距离之和。如果当前距离之和优于当前最优解，则需要更新最优解和最优路径。else:forjinrange(1,path_num):ifCity_Graph[path[t-1]][j]!=-1and(notisin[j]):#两个城市之间有路径，还没有gonethroughisin[j]=1#表示城市已经到过这里path[t]=j#将城市保存到路径中now_length=now_length+City_Graph[path[t-1]][j]#添加对应的路径到距离和TSP(t+1)isin[j]=0path[t]=0now_length=now_length-City_Graph[path[t-1]][j]如果条件不成立，则正在搜索树。对于每条正在搜索的路径，如果两个城市之间有一条路径，且该路径没有走过，则需要在路径path中填入，需要在当前距离和上加上这条路径对应的权重now_length，然后继续往下找。这部分代码最后三行的作用是在执行回溯操作时恢复对应节点的数据。比如对于路径12341，回溯查找对应的是12431，在回溯之前，需要恢复3和4对应的数据，方便追加4和3对应的数据。可以看出，在循环中上面的代码都是从1开始的，也是为了对应上面二维数组中的地图索引。最后，运行程序得到每条可行路径的总和及其对应的距离。程序中设置了最优解和最优路径参数，所以可以直接调用并输出：分支定界法分支定界法采用广度优先搜索策略，或者以如下的方式搜索问题的解空间最小成本（最大收益）优先级树，对于解空间树中的一个活节点，只有一次机会成为扩展节点。一旦活节点成为扩展节点，它的所有子节点将一次性生成。对于优先队列分支定界法，在这些子节点中，不可行或一定不能成为最优解的子节点将被丢弃，剩余的子节点将根据优先事项。之后，将选择活动节点列表中优先级最高的节点作为下一个扩展节点，不断重复这一过程，直到找到问题的最优解。下面说明一下，图中会出现两个新的缩写变量。首先声明对应的含义：nl:now_length，当前行驶距离的长度。Lb：下界，所有可行解的下界，即每个节点的出边之和。左上角是图的邻接矩阵，右上角是活动节点表。当扩展节点为B时，需要一次性生成其所有子节点。可以看到B的Lb是18，这个18是怎么得来的？是除-1以外的每一行或每一列的最小权值相加，即4+5+5+4=18。下界通常不是可行解，但它为可行解提供了一个界限，便于寻找代价最小的路径（最优解）。对于B的子节点，一共有3条路径。可以看到C、D、E对应的Lbs都是14，这是因为1号城市到其他3座城市的路径已经确定了，所以下界也要减去4。这就像初始下界是我们猜测的4条最短路径相加，但是现在第一条路径的实际值已经确定，那么下界应该是第一条路径的猜测值减去，下界在这个时间是后者三个路径猜测的总和。此时，C、D、E三个节点应该按照优先级存储在活跃节点表中。总距离越小，优先级越高。当前总距离=nl+Lb。根据计算节点E的优先级最高，所以E也是下一个扩展节点。对于扩展节点E，路径1和4的值已经确定，所以子节点的Lb=18-4-4=10，计算两个子节点当前距离之和，插入根据优先级进入活动节点表，D成为下一个时间扩展节点。对于扩展节点D，路径1和3的值已经确定，所以子节点的Lb=18-4-5=9，按照上面的方法更新活跃节点表，H就会变成下一个扩展节点。因为H是叶子节点的父节点，所以需要判断map中是否存在从4到1的环路。如果存在环路，那么整个路径组合就是问题的可行解，也是当前最优解，但不一定是全局最优解。由于节点K对应的距离之和为24，优于当前最优解25，因此需要将节点N插入到活动节点表中。按照上面的方法，让K成为扩展节点，继续向下搜索。最终距离之和也是25，并不比当前最优解好。然后，根据活跃节点列表的顺序，节点N再次成为扩展节点，如下图所示：此后，活跃节点列表中没有节点的优先级高于N，所以13241对应的路径节点N成为最优路径，对应的总距离25成为问题的最优解。总结回溯法和分支定界法都是在问题解空间的树上搜索问题解的算法。回溯法主要采用深度优先搜索策略，通常的目标是找到问题的所有可行解；分支定界法主要采用广度优先搜索策略，通常的目标是尽快找到满足问题约束的解，所以对于TSP等最优求解问题，分支定界法比回溯法更合适。公众号【奶糖猫】后台回复“TSP”获取文中提到的源码，供参考