| 分支限界法求解实际TSP问题 |
| |
| 引用本文： | 陈涛,张思发.分支限界法求解实际TSP问题[J].计算机工程与设计,2009,30(10). |
| |
| 作者姓名： | 陈涛 张思发 |
| |
| 作者单位： | 中国地质大学计算机学院,湖北,武汉,430074 |
| |
| 摘 要： | 提出一种基于分支限界思想来求解实际TSP问题的算法,并着重介绍上下界的计算.下界值是根据当前路径来计算的,简单易行且占用空间少.上界只计算一个全局的上界值,计算过程中用到实际TSP问题的一个特点——三角不等式性质,求得的值不超过最优值的1.5倍.实际TSP问题另一个特点是对称性,对称性可使解空间树缩小一半,进一步加速搜索过程.提出的求上界和求下界的算法是独立,完全可以分割开来,但是通过例子可以看出将这两种方法用分支限界的思想结合起来是行之有效的,可大大加速解空间树的搜索.
|
| 关 键 词： | 旅行商问题 三角不等式 上界 下界 解空间树 |
Using a branch and bound method to solve realistic TSP |
| |
| CHEN Tao,ZHANG Si-fa.Using a branch and bound method to solve realistic TSP[J].Computer Engineering and Design,2009,30(10). |
| |
| Authors: | CHEN Tao ZHANG Si-fa |
| |
| Abstract: | |
| |
| Keywords: | |
| 本文献已被 维普 万方数据 等数据库收录！ |
|
