分支限界法求解实际TSP问题  

Using a branch and bound method to solve realistic TSP

作　　者：陈涛[1] 张思发[1] 

机构地区：[1]中国地质大学计算机学院,湖北武汉430074

出　　处：《计算机工程与设计》2009年第10期2431-2434,共4页Computer Engineering and Design

摘　　要：提出一种基于分支限界思想来求解实际TSP问题的算法,并着重介绍上下界的计算。下界值是根据当前路径来计算的,简单易行且占用空间少。上界只计算一个全局的上界值,计算过程中用到实际TSP问题的一个特点——三角不等式性质,求得的值不超过最优值的1.5倍。实际TSP问题另一个特点是对称性,对称性可使解空间树缩小一半,进一步加速搜索过程。提出的求上界和求下界的算法是独立,完全可以分割开来,但是通过例子可以看出将这两种方法用分支限界的思想结合起来是行之有效的,可大大加速解空间树的搜索。An algorithm to solve TSP based on a branch and bound thought is presented, and the calculation of upper and lower bounds is discussed in detail. The calculation of lower bound＇s value is based on the current path, it is simple and easy and take up less memory. The upper bound has only a global value. One of the characteristics of realistic TSP-triangle inequality is used in the calculation, the result does not exceed 1.5 times the best value. Another characteristic of realistic TSP is symmetry, it can narrow the tree solution space a half, and further speed up the search process. The algorithms of seeking lower bound and upper bound is independent and can fully separated from each other, but through the example, it is proved more effective of combining the two method with the thought of branch and bound, and it can greatly accelerate the search of the tree of solution space.

关 键 词：旅行商问题 三角不等式 上界 下界 解空间树 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]