| 关于旅行商问题的若干启发式算法的性能比分析 |
| |
| 引用本文： | 刘剑平.关于旅行商问题的若干启发式算法的性能比分析[J].华东理工大学学报(自然科学版),2005,31(6):801-803. |
| |
| 作者姓名： | 刘剑平 |
| |
| 作者单位： | 华东理工大学数学系,上海,200237 |
| |
| 基金项目： | 华东理工大学科研基金资助项目 |
| |
| 摘 要： | 旅行商问题的增量最小插入法、最近插入法、最近加入法的性能比已经被证明有一个上界2，本文在欧几里德平面上给出了这些方法性能比接近于2的例子。另外，我们证明了凸包选边插入法的性能比有一个关于点数的对数函数上界。
|
| 关 键 词： | 旅行商问题 启发式算法 凸包 性能比 |
| 文章编号： | 1006-3080(2005)06-0801-03 |
| 收稿时间： | 2004-12-08 |
| 修稿时间： | 2004年12月8日 |
Performance Ratio Analysis of Several Heuristics Algorithm for the TSP |
| |
| LIU Jian-ping.Performance Ratio Analysis of Several Heuristics Algorithm for the TSP[J].Journal of East China University of Science and Technology,2005,31(6):801-803. |
| |
| Authors: | LIU Jian-ping |
| |
| Institution: | Department of Mathematics, East China University of Science and Technology, Shanghai 200237, China |
| |
| Abstract: | The performance ratios of the cheapest insertion method, nearest insertion method, nearest addition method of traveling salesman problem have been shown to have an upper bound 2, we show the ratios have lower bound approximate to 2. In addition, we prove the performance ratio of the convex hull insertion for the traveling salesman problem in Euclidean plane has the upper bound about a logarithmic function of the number of nodes. |
| |
| Keywords: | traveling salesman problem(TSP) heuristics algorithm convex hull performance ratio |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
