01、旅行商问题

在旅行商问题的解空间和解空间组织结构基础上，讨论如何用分支限界法进行搜索。

图1无向连通图

考虑n=4的实例，如图1所示，城市1为售货员所在的住地城市。

对于该实例，简单做如下分析：

(1) 问题的解空间(x1,x2,x3,x4)，其中令S={1,2,3,4}，x1=1，x2∈S-{x1}，x3∈S-{x1,x2}，x4∈S-{x1,x2,x3}。

(2) 解空间的组织结构是一棵深度为4的排列树。

(3) 搜索：设置约束条件g［i］［j］!=∞，其中1≤i≤4，1≤j≤4，g是该图的邻接矩阵；设置限界条件：cl<bestl，其中cl表示当前已经走的路径长度，初始值为0；bestl表示当前最短路径长度，初始值为∞。

1●队列式分支限界法

(1) 算法设计。

用先进先出的队列存储活节点，当活节点表不空，循环做：从活节点表中取出一个活节点，一次性扩展它的所有孩子节点，判断约束条件和限界条件，若满足约束条件和限界条件，则将该孩子节点插入到活节点表中；否则，舍弃该孩子节点；直到活节点表为空或找到了所需要的解。

2●优先队列式分支限界法

(1) 算法设计。

用堆结构存储活节点，算法的优先级定义为当前节点的路径长度cl，当前路径长度cl越短，优先级越高。当活节点表不空，循环做：从堆中取出一个活节点，一次性扩展它的所有孩子节点，判断约束条件和限界条件，若满足约束条件和限界条件，则将该孩子节点插入到活节点表中；否则，舍弃该孩子节点；直到活节点表为空或找到了所需要的解。

3●算法优化

(1) 优化策略。

根据题意，每个城市各去一次销售商品。因此，可以估计路径长度的下界(用zl表示)，初始时，zl等于图中每个顶点权最小的出边权之和。随着搜索的深入，可以估计剩余路径长度的下界(用rl表示)。故可以考虑用zl(zl=当前路径长度cl+剩余路径长度的下界rl)作为活节点的优先级，同时将限界条件优化为zl=cl+rl<bestl，cl的初始值为0，rl初始值为每个顶点权最小的出边权之和。那么，依照该限界条件，队列式分支限界法和优先队列式分支限界法搜索过程形成的搜索树如图2所示。

图2 优化条件下的搜索树

(2) Python实战——优先队列式分支限界法。
首先导入程序需要的类包math和queue。

定义一个类Node，用于描述树节点。该类有4个字段，分别是当前路径长度cl，当前节点在解空间树中的层次level、路径长度下界bl和当前节点代表的部分解x。其中，路径长度下界bl为优先级，路径长度下界bl越小，优先级越高。类Node重载了小于__lt__()方法和等于__eq__()方法，定义参与比较的字段为bl。其代码如下：

定义一个lower_bound（）函数，用于计算无向连通带权图G中每个城市的最小出边Minout及所有路径长度下界rl。其代码如下：

定义一个traveling（）函数，用于搜索最优旅行路线，并记录最短路径长度。该函数接收图的邻接矩阵a，出发地start和城市数量g_n，输出最优旅行路线和最短路径长度。其代码如下：

定义Python入口——main()函数，在main()函数中，初始化旅行商问题的一个实例，给定图的邻接矩阵中，下标代表城市编号，从1开始，故Python二维列表a中的第0行第0列为无效数据。然后调用 traveling()函数得到问题的最优解bestx和最优值bestl，bestx中的0号存储单元中的数据为无效数据。最后打印输出，将结果显示在显示器上。其代码如下：

输出结果为

最短路径长度为：43

最优旅行路线为：［0, 1, 4, 3, 2, 5］