| 旅行商问题的近似求解算法 |
| |
| 引用本文： | 陈培军,王欣洁.旅行商问题的近似求解算法[J].太原科技大学学报,2010,31(3):230-234. |
| |
| 作者姓名： | 陈培军 王欣洁 |
| |
| 作者单位： | 太原科技大学,太原,030024 |
| |
| 基金项目： | 太原科技大学青年基金 |
| |
| 摘 要： | 在最近邻法、k-变换策略和贪心算法的基础上,尝试设计效率较高的产生旅行商问题较优可行解的方法。将3变换邻域分成两种结构(称为3_1和3_2变换邻域)考虑,设计以下算法:利用最近邻法产生初始当前最优解;然后依次在当前最优解的3_2、3_1、2变换邻域中寻找更优的局部最优解成为当前最优解,直到结果没有改进。利用算法对一些经典的实例进行实验,依次将每个城市作为出发地,在多项式时间O(n4)得到的最优解与给定的最优解相对误差在1%内。
|
| 关 键 词： | 旅行商问题 k变换策略 最近邻法 贪心算法 |
An Approximate Algorithm for Solving Traveling Salesman Problem |
| |
| CHEN Pei-jun,WANG Xin-jie.An Approximate Algorithm for Solving Traveling Salesman Problem[J].Journal of Taiyuan University of Science and Technology,2010,31(3):230-234. |
| |
| Authors: | CHEN Pei-jun WANG Xin-jie |
| |
| Abstract: | |
| |
| Keywords: | |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
