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

• 作者: 张思发 陈涛
• 来源期刊: 计算机工程与设计
• 学科: 工学
• 关键词: 旅行商问题 三角不等式 上界 下界 解空间树
• 年，卷（期）: 2009,（10）
• 所属期刊栏目: 人工智能
• 页码范围: 2431-2434
• 页数: 4页
• 分类号: TP301.6
• 字数: 3411字
• 语种: 中文

摘要

提出一种基于分支限界思想来求解实际TSP问题的算法,并着重介绍上下界的计算.下界值是根据当前路径来计算的,简单易行且占用空间少.上界只计算一个全局的上界值,计算过程中用到实际TSP问题的一个特点——三角不等式性质,求得的值不超过最优值的1.5倍.实际TSP问题另一个特点是对称性,对称性可使解空间树缩小一半,进一步加速搜索过程.提出的求上界和求下界的算法是独立,完全可以分割开来,但是通过例子可以看出将这两种方法用分支限界的思想结合起来是行之有效的,可大大加速解空间树的搜索.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张思发	中国地质大学计算机学院	15	65	5.0	7.0
2	陈涛	中国地质大学计算机学院	54	205	9.0	11.0