摘要
提出一种基于分支限界思想来求解实际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.
出处
《计算机工程与设计》
CSCD
北大核心
2009年第10期2431-2434,共4页
Computer Engineering and Design
关键词
旅行商问题
三角不等式
上界
下界
解空间树
TSP
triangle inequality
upper bound
lower bound
tree of solution space
