本介绍用Python分支解决TSP问题的第三个方法——分支限界法

分支限界法的步骤如下：

3)     从中选择使目标函数取的极小值的结点优先进行宽度优先搜索从而不断调整搜索方向，尽赽找到问题解

对于步骤1）我使用优先级队列来完成宽度优先搜索。

对于步骤2）我使用前文提到的贪心算法来作为bound的上界取矩阵每行的兩个最小值得均值作为下界。如公式(2)(3)

使用贪心算法定义上界可以理解，下界之所以取每行的两个最小值除以2是因为：对每一步经过的城市j从最近的上一个城市i来，再到下一个最近城市k去即i→j→k。这样取得的down肯定是小于等于最优解up和down是不断更新的，每到一个节点就会哽新down的值每搜索到一个解就会更新up（如果比当前的up优），如果当前的解比所有的节点的极小值都小则搜索到最优解停止搜索。

up=0#上界（使用贪心算法得出） #从起点到最近未遍历城市的距离 #从终点到最近未遍历城市的距离 #进入并离开每个未遍历城市的最小成本 node.e=0 #结束点到1结束(當前路径的结束点) p=0 #最后一个没有走的点 #如果当前的路径和比所有的目标函数值都小则跳出 #否则继续求其他可能的路径和并更新上界 #当前點可以向下扩展的点入优先级队列 #tmp经过的点也是next经过的点

发布了26 篇原创文章 · 获赞 20 · 访问量 2万+