| 旅行推销员问题凸包方法的性能比分析 |
| |
| 引用本文： | 刘剑平.旅行推销员问题凸包方法的性能比分析[J].华东理工大学学报(自然科学版),2004,30(6):712-715. |
| |
| 作者姓名： | 刘剑平 |
| |
| 作者单位： | 华东理工大学数学系,上海,200237 |
| |
| 基金项目： | 华东理工大学科研基金资助项目 |
| |
| 摘 要： | 在欧几里德平面上证明了旅行推销员问题的凸包方法的性能比上界为n／2，同时给出了凸包随意插入算法的性能比可以接近n／2的例子。另外，对凸包增量最小插入法、凸包最近插入法及凸包最近加入法给出了性能比不超过3的证明。
|
| 关 键 词： | 旅行推销员问题 性能比 凸包 增量最小插入法 最近插入法 最近加入法 |
| 文章编号： | 1006-3080(2004)06-0712-04 |
| 修稿时间： | 2003年11月5日 |
Performance Ratio Analysis of the Convex Hull Method for the Euclidean Traveling Salesman Problem |
| |
| LIU Jian-ping.Performance Ratio Analysis of the Convex Hull Method for the Euclidean Traveling Salesman Problem[J].Journal of East China University of Science and Technology,2004,30(6):712-715. |
| |
| Authors: | LIU Jian-ping |
| |
| Abstract: | In this paper, we show the performance ratio of the convex hull method for the Euclidean traveling salesman problem has the upper bound n/2. Meanwhile, we give an algorithm that its performance ratio has lower bound approximate to n/2. In addition, we prove the performance ratios of the convex hull cheapest insertion method, convex hull nearest insertion method and convex hull nearest addition method for the Euclidean traveling salesman problem have the upper bound 3. |
| |
| Keywords: | traveling salesman problem performance ratio convex hull cheapest insertion method nearest insertion method nearest addition method |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
