秒懂算法 | 排列树模型——旅行商问题的分支限界法
介绍旅行商问题的队列式分支限界法、优先队列式分支限界法及其改进、改进算法的Python编程实战。
01
旅行商问题
旅行商问题的解空间和解空间组织结构已在5.5节中详细分析过。在此基础上，讨论如何用分支限界法进行搜索。
图6-7无向连通图
考虑n=4的实例，如图6-7所示，城市1为售货员所在的住地城市。
对于该实例，简单做如下分析：
(1) 问题的解空间(x 1 ,x 2 ,x 3 ,x 4 )，其中令S={1,2,3,4}，x 1 =1，x 2 ∈S-{x1}，x 3 ∈S-{x 1 ,x 2 }，x 4 ∈S-{x 1 ,x 2 ,x 3 }。
(2) 解空间的组织结构是一棵深度为4的排列树。
(3) 搜索：设置约束条件g［i］［j］!=∞，其中1≤i≤4，1≤j≤4，g是该图的邻接矩阵；设置限界条件：cl 1 ● 队列式分支限界法 (1) 算法设计。 用先进先出的队列存储活节点，当活节点表不空，循环做：从活节点表中取出一个活节点，一次性扩展它的所有孩子节点，判断约束条件和限界条件，若满足约束条件和限界条件，则将该孩子节点插入到活节点表中；否则，舍弃该孩子节点；直到活节点表为空或找到了所需要的解。 2 ● 优先队列式分支限界法 (1) 算法设计。 用堆结构存储活节点，算法的优先级定义为当前节点的路径长度cl，当前路径长度cl越短，优先级越高。当活节点表不空，循环做：从堆中取出一个活节点，一次性扩展它的所有孩子节点，判断约束条件和限界条件，若满足约束条件和限界条件，则将该孩子节点插入到活节点表中；否则，舍弃该孩子节点；直到活节点表为空或找到了所需要的解。 3 ● 算法优化 (1) 优化策略。 根据题意，每个城市各去一次销售商品。因此，可以估计路径长度的下界(用zl表示)，初始时，zl等于图中每个顶点权最小的出边权之和。随着搜索的深入，可以估计剩余路径长度的下界(用rl表示)。故可以考虑用zl(zl=当前路径长度cl+剩余路径长度的下界rl)作为活节点的优先级，同时将限界条件优化为zl=cl+rl 图6-14优化条件下的搜索树 (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］ 实例讲解 算法设计与分析（Python版） 精彩回顾 秒懂算法 算法设计的一般过程 递推方程求解方法 活动安排问题贪心算法 哈夫曼编码贪心算法 Prim算法 Kruskal算法 选第二大元素的分治算法 快速排序算法中的分治思想 动态规范算法的基本思想 矩阵连乘问题 0-1背包问题的动态规划改进算法——跳跃点算法 子集树模型——0-1背包问题的回溯算法 满m叉树模型——图的m可着色问题的回溯算法 下期预告 秒懂算法 最大网络流的增广路算法 蒙特卡罗算法 02 参考书籍 《算法设计与分析》 作者：王秋芬 定价：59.90元 03 精彩推荐 微信小程序游戏开发│猜数字小游戏（附源码+视频） Flink编程基础│Scala编程初级实践 Flink编程基础│FlinkCEP编程实践 Flink编程基础│DataStream API编程实践 Flink编程基础│DataSet API编程实践 数 据分析实战│客户价值分析 数据分析实战│价格预测挑战 数据分析实战│时间序列预测 数据分析实战│KaggleTitanic生存预测
上一篇：开源作者去世后，代码谁来继承？